\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-19}

\begin{document}
\maketitle
Vi b\"orjar med n\aa gra  exempler:

\vspace{.2in}

\noindent{\it Exempel}. Hur m\aa nga arrangemang av bokst\"averna i ANTANANARIVE finns det?

Vi har $12$ bokst\"aver. Hade de varit olika skulle det funnit $12!$ stycken arrangemang, men nu finns det $4$ stycken $A$ och $3$ stycken $E$. S{\aa} svaret \"ar:
$$ \frac{12!}{3!\cdot 4!}$$
\noindent Hur m\aa nga arrengemang finns det om vi ville ha alla $A$ st\aa r till varandra?

Vi ska behandla alla $A$ som ett element: $AAAA=\Box$. S{\aa} vi har nu $9$ stycken  element med $3$ likadana $N$. Svaret \"ar $\frac{9!}{3!}$.
\vspace{.2in}

\noindent{\it Exempel}. P{\aa} hur m\aa nga s\"att kan bokst\"averna i UNDERBAR arrangeras med exakt tv{\aa} konsekutiva vokaler?

Man kan konstruera ett arrangemang p{\aa} f\"oljande s\"att:

f\"orst ska man v\"alja tv{\aa} vokaler och s\"atta den lika med ett elemnt, $\Box$. Sedan ska man ber\"akna antal arrangemang av element $\Box$, N, D, R, B,R.
Och sedan ska man placera den annan vokal mellan tv{\aa} element $\neq\Box$\\
Vi ser att man kan v\"alja tv{\aa} vokaler ur tre (h\"ar vi ska v\"alja MED ordning och utan upprepning) p{\aa} $\frac{3!}{1!}=6$ s\"att.
Dessutom  finns det $\frac{6!}{2!}$ antal  arrangemang av element $\Box$, N, D, R, B,R.\\
Ocks{\aa} man kan placera den annan vokal mellan tv{\aa} element $\neq\Box$ p{\aa} $5$ ulika s\"att.\\
Enligt multiplikationsprincipen svaret \"ar 
$$6\cdot \frac{6!}{2!}\cdot 5=10800$$


\vspace{.3in}

Vi ska nu inf\"ora En generalisering av binomialkoefficienterna.

Antag att $n_1,..,n_k$ \"ar icke-negativa heltal och att $n_1+...+n_k=n$. D{\aa} defineras den {\it multinomialkoefficient} som talet:
$${n\choose n_1,n_2,...,n_k}=\frac{n!}{n_1!\cdot n_2!\cdot ... \cdot n_k!}$$

Vi observerade tidigare att:

{\it Antalet arrangemang av $n_1$ stycken identiska objekt, $n_2$ stycken identiska objekt,...,$n_k$ stycken identiska objekt, d\"ar $n_1+n_2+...+n_k=n$ \"ar}
$${n\choose n_1,n_2,...,n_k}=\frac{n!}{n_1!\cdot n_2!\cdot ... \cdot n_k!}$$

\vspace{.3in}

{\it Om man ska ligga $n+1$ brev i $n$ postfack m\aa ste n\aa got postfack f{\aa} minst tv{\aa} brev.}

Denna kallas den {\it Postfacksprincipen.}

Den generaliseras l\"att som

{\it Om $kn+1$ eller fler brev skall l\"aggas i $n$ postfack s{\aa} m\aa ste n\aa got postfack inneh\aa lla minst $n+1$ brev.}

\vspace{.2in}

\noindent{\it Exempler}.
\begin{itemize}
\item  Av 13 personer s{\aa} m\aa ste det finnas tv{\aa} som har f\"odelsedag samma m{\aa}nad.
\item I en liksidig triangel med sidan $1$ v\"aljes $5$ punkter. Visa att det finns tv{\aa} punkter vars avst\aa nd \"ar h\"ogst $\frac{1}{2}$.

Delar triangel i fyra delar. Enligt postfacksprincipen m\aa ste minst tv{\aa} punkter tillh\"ora samma deltriangel. S{\aa} dessa punkter har ett inb\"oedes avst{\aa}nd som \"ar mindre eller lika med $\frac{1}{2}$.
\item Finns det n\aa got s\"att att placera p{\aa} ett middasbjudning, tre par kring ett runt bord s{\aa} att alla bordsgrannar \"ar av olika k\"on och ingen sitter brevid sin partner?

Det finns $3$ kvinnor $K_1,K_2,K_3$ och deras partner $M_1,M_2,M_3$. Om vi b\"orjar med $K_1$ ser vi att placering:
$$K_1 M_2 K_3 M_1 K_2 M_3$$ g\aa r bra. Eftersom vi kan b\"orja med en bland $6$ personer och efter f\"orsta placering har vi bara tv{\aa} m\"ojlihet att placera andra pesonen, \"ar svatret:
$$6\cdot 2=12$$
\end{itemize}

\begin{definition}
En {\it partition} av en m\"angd $A$ \"ar en uppdelning i djunkta delm\"agder
\begin{itemize}
\item $A=A_1\cup A_2\cup ... \cup A_k$.
\item $A_i\cap A_j=\emptyset$ f\"or $i\neq j$
\end{itemize}
\end{definition}

Antalet aprtitioner av en m\"angd med $n$ element i $k$ delar betecknas med
$$S(n,k)$$
{\it Stirlingtalet}.

\vspace{.2in}

\noindent{\it Exempel}.\begin{itemize}
\item $S(n,0)=1$
\item $S(n,1)=1$
\item $S(n,n)=1$
\end{itemize}

Sterligtal kan ber\"aknas enligt en rekursiv formula:
$$ S(n,k)=S(n-1,k-1)+kS(n-1,k)$$

L\aa t $A$ vara en m\"angd med $n$ element och $x\in A$. M\"angden $A\setminus \{x\}$ har $n-1$ element och varje partition av $A\setminus \{x\}$ i $k-1$ delar ger en  partition av $A$ i $k$ delar genom att s\"atta $\{a\}=A_k$. Dessutom varje  partition av $A\setminus \{x\}$ i $k$ delar ger $k$ olika partitioner av $A$ i $k$ delar genom att placera $x$ i en av den $k$ delar.

P{\aa} hur m\aa nga s\"att kan vi dela en m\"angt med $n$ element i $k$ delar  s{\aa} att delarnas storlekar \"ar $n_i$? 

Vi vill ber\"akna partitioner p{\aa} formen:
\begin{itemize}
\item $A=A_1\cup A_2\cup A_3\cup ...\cup A_k$
\item $A_i\cap A_j=\emptyset$ f\"or varje $i\neq j$.
\item $|A_i|=n_i$
\end{itemize}

\vspace{.1in}

Svaret \"ar ${n\choose n_1,n_2,...,n_k}$.
\section*{Grafteori}

Euler var den f\"orste som anv\"ande grafteori n\"ar han l\"oste problemet med {\it K\"onigsbergs broar}.( Se sidan 149 i boken).

I k\"oningsberg fanns $7$ broar som band samman de olika stadsdelarna. Eulers fr\aa gan var:

Kan man g{\aa} en promenad s{\aa} att man g\aa r \"over varje bro precis en g\aa ng?

Euler inf\"orde en graf d\"ar:
\begin{itemize}
\item ett {\it h\"orn} eller {\it nod}, $\bullet$ motsvarar en stadsdel och
\item en {\it kant} | motsvarar en bro.
\end{itemize}
 \hspace{.2in}\setlength{\unitlength}{1.5cm}
\begin{picture}(3,2.2)
\put(0,1){\circle*{0.2}}
\put(1,0){\circle*{0.2}}
\put(3,1){\circle*{0.2}}
\put(1,2){\circle*{0.2}}
\qbezier(1,0),(0,0)(0,1)     
\qbezier(0,1),(0,2)(1,2)
\put(0,1){\line( 1,1){1}}
\put(1,0){\line(2,1 ){2}}
\put(1,2){\line(2 ,-1){2}}
\put(1,0){\line(-1,1){1}}
\put(0,1){\line( 1,0){3}}
\end{picture}

Euler observerade att varje g\aa ngen ett h\"orn passeras p{\aa} en promenad anv\"ands tv{\aa} kanter, utom vid f\"orsta och sista. Dessutom vi ska anv\"anda varje kant precis en g\aa ng. Det betyder att det bara finnas tv{\aa} h\"orn med udda antal kanter.

Men Grafen har alla odda h\"orn. S{\aa} det \"ar omjligt att g{\aa} en promenad s{\aa} att man g\aa r \"over varje bro precis en g\aa ng.

\vspace{.1in}


Den h\"ar graf kallas Eulers graf. Eulers graf \"ar en {\it multi-graf} efetersom den har parallela kanter.

En multi-graf kan ocks{\aa} ha {\it \"oglor}.

En graf utan parallela kanter eller \"oglar kallas en {\it Enkel Graf}.

Vi ska betrakta bara enkla grafer!
\begin{definition}
En enkel graf \"ar ett par $(V,E)$ av m\"angder d\"ar:
\begin{itemize}
\item $V=\{x_1,...,x_k\}$ \"ar en icke-tom och \"andlig. Den kallas m\"angden av h\"orn.
\item $E=\{e_1,...,e_n\}$ d\"ar varje element $e_i$ best\aa r av ett par av h\"orn, $e_i=x_jx_k$, $i\neq k$. Den kallas m\"angden av kantor.
\end{itemize}
\end{definition}

Varje enkel graf kan representeras geometriskt  med punkter och linjer.

\vspace{.2in}

\noindent{\it Exempel}.
\begin{itemize}
\item Betrakta grafen $W_n=(V,E)$, d\"ar \begin{itemize}
\item $V=\{0,1,2,...,n\}$ och 
\item $E=\{01,02,...,0n,12,23,34,...,(n-1)n,n1  \}$
\end{itemize}

$W_1: $ \hspace{.2in}\setlength{\unitlength}{1.5cm}
\begin{picture}(3,0)
\put(0,0){\circle*{0.1}}
\put(0,0){\line(1,0){2}}
\put(2,0){\circle*{0.1}}
\end{picture}

$W_2: $ \hspace{.2in}\setlength{\unitlength}{1.5cm}
\begin{picture}(3,1.2)
\put(0,0){\circle*{0.1}}
\put(0,0){\line(1,0){2}}
\put(0,0){\line(1,1){1}}
\put(1,1){\circle*{0.1}}
\put(2,0){\circle*{0.1}}
\put(1,1){\line(1,-1){1}}
\end{picture}
$W_4: $ \hspace{.2in}\setlength{\unitlength}{1.5cm}
\begin{picture}(3,2)
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(2,0){\circle*{0.1}}
\put(2,2){\circle*{0.1}}
\put(3,1){\circle*{0.1}}
\put(1,0){\line(1,0){1}}
\put(1,0){\line(-1,1){1}}
\put(1,0){\line(1,2){1}}
\put(2,0){\line(1,1){1}}
\put(2,0){\line(0,2){2}}
\put(0,1){\line(1,0){3}}
\put(0,1){\line(2,1){2}}
\put(2,2){\line(1,-1){1}}
\end{picture}
\item Vi definerar nu den {\it kompletta grafen} $K_n=(V,E)$:
\begin{itemize}
\item $V=\{1,2,3,...,n  \}$ och
\item $E=\{ ij| i\neq j\}$. alla par av noder \"ar f\"rbunda.
\end{itemize}
$K_4: $ \hspace{.2in}\setlength{\unitlength}{1.5cm}
\begin{picture}(3,2.2)
\put(2,0){\circle*{0.1}}
\put(0,2){\circle*{0.1}}
\put(0,0){\circle*{0.1}}
\put(2,2){\circle*{0.1}}
\put(0,0){\line(1,0){2}}
\put(0,0){\line(0,1){2}}
\put(0,0){\line(1,1){2}}
\put(2,0){\line(0,1){2}}
\put(2,0){\line(-1,1){2}}
\put(0,2){\line(1,0){2}}
\end{picture}
$K_5: $ \hspace{.2in}\setlength{\unitlength}{1.5cm}
\begin{picture}(3,2.2)
\put(1,0){\circle*{0.1}}
\put(0,1){\circle*{0.1}}
\put(2,0){\circle*{0.1}}
\put(2,2){\circle*{0.1}}
\put(3,1){\circle*{0.1}}
\put(1,0){\line(1,0){1}}
\put(1,0){\line(-1,1){1}}
\put(1,0){\line(1,2){1}}
\put(2,0){\line(1,1){1}}
\put(2,0){\line(0,2){2}}
\put(0,1){\line(1,0){3}}
\put(0,1){\line(2,1){2}}
\put(2,2){\line(1,-1){1}}
\put(2,0){\line(-2,1){2}}
\put(1,0){\line(2,1){2}}
\end{picture}

Hur m\aa nga kanter finns i $K_n$? Eftersom alla noder \"ar f\"orbunddam\aa ste  kardilateten av $E$  vara $n\choose 2$.
\end{itemize}
\end{document}