%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%    LEKTION 1   %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentclass[12pt]{amsart} 
\usepackage[dvips]{graphics, color}
\theoremstyle{plain}

\newtheorem{theorem}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{lemma}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{exempel}
\newtheorem{exempel}[theorem]{Exempel}
\theoremstyle{corollary}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{proposition}
\newtheorem{proposition}[theorem]{{Proposition}}
\theoremstyle{clam}
\newtheorem{clam}[theorem]{Claim}
\theoremstyle{conjecture}
\newtheorem{con}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{re}[theorem]{{Remark}}
\newtheorem{no}[theorem]{Notation}



\newtheorem{quest}[theorem]{Question}

\newtheorem{problem}[theorem]{Problem}





\newtheorem{worning}[theorem]{{\rm W\sc orning}}

\newtheorem{para}[theorem]{}

\newtheorem{examp}[theorem]{Example}

\newtheorem{exercise}[theorem]{Exercise}

\newcommand\pn[1]{{\mathbb P}^{#1}}
\newcommand\cal[1]{\mathcal {#1}}
\newcommand\cL{\mathcal L}
\newcommand\cZ{\mathcal Z}
\newcommand\cO[1]{\cal{O}_{\cal{{#1}}}}
\newcommand\X[1]{X^{[{#1}]}}
\newcommand\zed{{\mathbb Z}}
\newcommand\nat{{\mathbb N}}
\newcommand\rat{{\mathbb Q}}
\newcommand\real{{\mathbb R}}
%\newcommand\a{{\aa}}
\textwidth16cm
\textheight20cm
\oddsidemargin-0.3cm
\evensidemargin0.4cm
%\pagestyle{plain} 
\newtheorem{Definition}{\sf Definition}



 \title{Lektion 03-03}





\begin{document}
\maketitle
{\it ``Kombinatorik handlar om konsten att {\it r\"akna} antalet m\"ojliga h\"andelser.''}

Det kan k\"annas l\"att att s\"aga och g\"ora, men det kan acks{\aa} vara v\"anlig listig. Till exempel:
\begin{itemize}
\item P{\aa} hur mnga s\"att kan man v\"alja ett par $(a,b)$ om man kan v\"alja $a$ p{\aa} 100 olika s\"att  och $b$ p{\aa} 1000 olika s\"att?
\item Hur m{\aa}nga g{\aa}nger upptr\"ader m\"onstret $0101$ in en l{\aa}ng sekvens best\aa nde av $0$ och $1$?
\end{itemize}
 F\"orst ska vi inf\"ora  terminologin f\"or att formulera problemet.
Vi ska unders\"oka hur kan man ``gruppera saker'' och vilka matematiska operationer man kan  utf\"ora f\"or att finna resultatet.

\section*{M\"angdl\"aran}
H\"ojdpunkter \"ar:
\begin{itemize}
\item Vad \"ar en m\"angd;
\item hur kan man beskriva en m\"angd;
\item vilka operationer p{\aa}  m\"angder kan man utf\"ora.
\end{itemize}
\begin{definition} En m\"angd $A$ \"ar en samling av objekt som kallas element.

$a\in A$ betyder att $a$ \"ar en element i $A$ och $a\not\in A$ betyder att $a$  inte \"ar en element i $A$.
\end{definition}
\noindent {\it Exempel} 
\begin{itemize}
\item $\emptyset$ betecknar den tomma m\"angden, dvs m\"angden med inga element.\item universum ${\mathcal U}=\{ \text{alla objekt}\}$;
\item ${\Bbb Z}$ betecknar m\"angden av alla hela tal $...,-100,-99,...,-1,0,1,...,100,...$;\\ ${\Bbb Z}^+$ betecknar m\"angden av alla positiva hela tal $1,2,...,100,...$;
\item ${\Bbb N}$ betecknar m\"angden av alla naturliga tal $0,1,...,100,...$;
\item ${\Bbb Q}$ betecknar m\"angden av alla rationella tal $...,-100,...,\frac{-1}{2},...,\frac{1}{10},...$;\\ ${\Bbb Q}^+$ betecknar m\"angden av alla positiva rationella tal;
\item ${\Bbb R}$ betecknar m\"angden av alla reella tal $...,-100,...,\frac{-1}{2},...,\frac{1}{10},...,\sqrt{3},...$; \\${\Bbb R}^+$ betecknar m\"angden av alla positiva reella tal;
\end{itemize}
Det finns olika s\"att f\"or att beskriva en m\"angd:
\begin{enumerate}
\item Man kan r\"akna upp m\"angdens element inom de s{\aa} kallad {\it m\"angdklammer}. Exempelvis
$$ A=\{1,2 ,3 ,4 ,5 ,6 ,7 ,8\}$$
\item man kan ange egenskaperna hos m\"angdens element.
Exempelvis  kan m\"angden $A$ beskrivas som:
$$A=\{ n\in {\Bbb N} \text{ och } 1\leq n\leq 8\}$$
\item man kan {\it visualisera} m\"angden genom att anv\"anda ett s{\aa} kallat {\it venndiagram}. Omr{\aa}det inom en sluten kurva i planet representerar elementen i m\"angden.

%\includegraphics*[3,3]{set.pdf}
\end{enumerate}
\noindent{\it Exempel}: Beskriv m\"angden av alla heltal med absolut belopp mindre \"an eller lika med $4$.
\begin{itemize}
\item $\{-4,-3,-2,-1,0,1,2,3,4\};$
\item $\{ n\in {\Bbb Z}\text{ och } |n|\leq 4\}$;
\item diagram;
\end{itemize}
\noindent{\it Exempel}: Betrakta m\"angden:
$$A=\{ n\in{\Bbb N} \text{ och } n=k^2 \text { d\"ar }k\in{\Bbb N}\}.$$
\begin{itemize}
\item \"Ar det s{\aa} att $17\in A$? (Nej)
\item \"Ar det s{\aa} att $21\not\in A$? (Ja)
\item \"Ar det s{\aa} att $121\in A$? (Ja)
\end{itemize}
\vspace{.2in}
Storleken av en m\"angd kan vara mycket stor. Exempelvis \"ar $\nat,\zed,\rat,\real$  {\it o\"andliga} m\"angder. Om man kan r\"akna upp alla element och det finns ett \"andligt antal element  s\"ager man att m\"angden \"ar \"andlig. Symbolen $|A|$ betecknar antalet element i $A$. Den  kallas ofta f\"or {\it kardinaliteten} av $A$.

\noindent{\it Exempel}: Betrakta m\"angden
$$M=\{n\in\zed^+,n\text{ \"ar udd och }n\leq 15\}.$$
D{\aa} har vi $M=\{1,3,5,7,9,11,13,15\}$ och $|M|=8$.

Klart \"ar $|\emptyset|=0$.

Om man tar ``bara n{\aa}gra element av en m\"angd'' f{\aa}r man en {\it delm\"angd}.
\begin{definition}
$B$ \"ar en delm\"angd av $A$ ($B\subseteq A$) om varje element $b\in B$ \"ar ett element i $A$.

\end{definition}
\noindent{\it Exempel:}
\begin{itemize}
\item Den tomma m\"angden $\emptyset$ \"ar en delm\"angd av varje m\"angd. (Visa det!)
\item $A\subseteq A$;
\item $\{\text{ udda heltal }\}\subset\zed$;
\item $\rat^+\subset\rat$;
\end{itemize}

Nu kan vi bygga upp en ny m\"angd fr{\aa}n $A$, n\"amlingen m\"angden av alla delm\"angder av $A$:
$${\mathcal P(A)}=\{B\subseteq A\}$$
 L{\aa}t $A=\{n\in\nat,n\text{ j\"amn och }0<n\leq 6\}$. D{\aa} \"ar
$A=\{2,4,6\}$ och 
$${\mathcal P(A)}=\{\emptyset,\{2\}, \{4\},\{6\}, \{2,4\},\{2,6\},\{4,6\}, A\}$$ S{\aa}, $|A|=3$ och $|{\mathcal P(A)}|= 8$.

\vspace{.1in}

\noindent{\it Fr{\aa}ga}: Om $|A|=k$, vad \"ar $|{\mathcal P(A)}|$?
Vi ska senare svara p{\aa} detta!
\section*{Bin\"ara operationer p{\aa} m\"angder}
L{\aa}t $A,B$ vara tv{\aa} m\"angder. Det finns ett antal s\"att att bilda nya m\"angder fr{\aa}n dem, genom  s{\aa} kallade bin\"ara operationer:

\begin{itemize}
\item {\bf Unionen}: $A\cup B=\{x,\text{ d\"ar } x\in A\text{ eller } x\in B\}$;
\item {\bf snittet}: $A\cap B=\{x,\text{ d\"ar  } x\in A\text{ och } x\in B\}$; Om $A\cap B=\emptyset$ s\"ager vi att $A$ och $B$ \"ar disjunkta. 
\item {\bf differensen}: $A\setminus B=\{x,\text{ d\"ar  } x\in A\text{ och } x\not\in B\}$;
\item {\bf komplement}: $A^c=\{x,\text{ d\"ar } x\not\in A\}$; (visa att $A^c={\mathcal U}\setminus A$).
\end{itemize}
\noindent{\it Exempel:}
\begin{itemize}
\item $A\cap B=B$ och$A\cup B=A$   om $B\subseteq A$; 
\item $\nat\cap\zed=\nat$;
\item $\zed^+=\nat\setminus\{0\}$;
\item $\{ n\in\nat\text{ d\"ar } n\text{ \"ar udda}\}\cup\{ n\in\nat\text{ d\"ar  } n\text{ \"ar j\"amna}\}=\nat$.
Vi har ofta skrivit att tv{\aa} m\"angder \"ar lika, men vad betyder det? Vi s\"ager att $A=B$ om $A\subseteq B$ och $B\subseteq A$.
\end{itemize}
H\"ar finns en sammanst\"allning av r\"akneregler:
\begin{enumerate}
\item $A\cap A=A$, $A\cup A=A$, $(A^c)^c=A$;
\item $A\cap A^c=\emptyset$, $A\cup A^c={\mathcal U}$;
\item $A\cap\emptyset=\emptyset$, $A\cup\emptyset=A$, $A\cap{\mathcal U}=A$,$A\cup{\mathcal U}={\mathcal U}$ ;
\item $A\cup (A\cap B)= A$, $A\cap(A\cup B)=A$
\item Associativa lagar 
$$(A\cup B)\cup C=A\cup (B\cup C)\hspace{.3in}(A\cap B)\cup C=A\cap (B\cap C)$$
\item kommutativa lagar
$$A\cup B=B\cup A\hspace{.3in}A\cap B=B\cap A$$
\item distributiva lagar
$$A\cup(B\cap C)=(A\cup B)\cap (A\cup C)\hspace{.3in}A\cap(B\cup C)=(A\cap B)\cup (A\cap C)$$
\item de Morgans lagar
$$(A\cup B)^c=A^c\cap B^c \hspace{.3in}(A\cap B)^c=A^c\cup B^c$$
\end{enumerate}

\noindent {\it \"Ovning}: Visa dem.
\section*{Samband mellan delm\"angders storlek}
Det \"ar sj\"alvklart att om $B\subseteq A$ \"ar $|B|\leq |A|$ (visa det!).
Vad \"ar sambanden mellan $|A|,|B|, |A\cup B|$ och $|A\cap B|$?
L{\aa}t $A=\{1,2,3,...,25\}$ och $B=\{24,25,...,100\}$. Vi har:
$$A\cup B=\{1,...,100\},A\cap B=\{24,25\}$$
och $|A\cup B|=100\neq |A|+|B|=25+77$.

Faktiskt n\"ar r\"aknar vi elementen i $A$ och sedan elementen i $B$, s{\aa} r\"aknar vi elementen i $A\cap B$ tv{\aa} g{\aa}nger, d\"arf\"or m{\aa}ste:
$$|A\cup B|=|A|+|B|-|A\cap B|$$
 
Detta \"ar den {\it Inklusion-exklusion principen}.

S{\aa} g\"aller $|A\cup B|=|A|+|B|$ bara n\"ar $A$ och $ B$ \"ar disjunkta.

\vspace{.1in}

\noindent{\it Exampel:} Best\"am antalet  j\"amna heltal mellan $1$ och $2000$.

L{\aa}t $A=\{ \text{j\"amna heltal}\}$ och $B=\{ \text{udda  heltal}\}$. Efters\"om de j\"amna och udda heltalen alternerar \"ar $|A|=|B|$ och $|A\cap B|=\emptyset$, s{\aa} har vi
$$2000=|A\cup B|=|A|+|B|=2|A|$$
och $|A|=1000$.

\vspace{.2in}

Det finns ett ytterligare mycket viktigt s\"att  att bygga upp en m\"angd fr{\aa}n tv{\aa} m\"angder $A$ och $B$, den s{\aa} kallade {\it produktm\"angden}:
$$A\times B=\{ (a,b)\text{ d\"ar }a\in A, b\in B\}$$
Ett element av $(a,b)\in A\times B$ kallas ett {\it par} av objekt i $A$ och $B$.
L\"attast \"ar att beskriva  produktm\"angden som en tabell.
Till exempel t{\aa}t $A=\{a,b,c\}$ och $B=\{1,2,3,4\}$. F\"oljande tabellen ger alla element i $A\times B$:

\begin{tabular}{c|lcr}
&A&B&C\\ \hline
1&(a,1)&(b,1)&(c,1)\\ 
2&(a,2)&(b,2)&(c,2)\\
3&(a,3)&(b,3)&(c,3)\\
4&(a,4)&(b,4)&(c,4)
\end{tabular}

\vspace{.2in}

\noindent{\it \"Ovning}. Best\"am $|A\times B|$ om $|A|=k$ coh $|B|=h$.
\end{document}
