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

\begin{document}
\maketitle


Id{\aa}g g{\aa}r vi genom de s{\aa} kallade {\bf icke ordnade urval}

Vi b\"orjar med lite terminologi:
\begin{definition}
En {\it kombination} av $k$ objekt utvald fr\aa n $n$ olika objekt \"ar ett urval, utan h\"ansyn till ordning och utan uprrepning, av $k$ objekt  fr\aa n $n$ olika objekt.
\end{definition}

Notera att n\"ar man ska v\"alja 2 element bland $A,B,C$ finns det tv{\aa} alternativ:
\begin{itemize}
\item med h\"ansyn till ordning, i.e val $(A,B)$ \"ar inte samma val som $(B,A)$.
\item  med ingen h\"ansyn till ordning, i.e val $(A,B)$ och $(B,A)$ t\"ankas som samma val.
\end{itemize}

Symbolen $K(n,k)$ betecknar antalet kombination av $k$ objekt utvald fr\aa n $n$ olika objekt.

Det \"ar klart att man skulle tro att  $K(n,r)< P(n,r)$.

Till exempel: 
$$P(3,2)=|\{AB,BA,AC,CA,BC,CB\}|=6$$
$$K(3,2)=|\{AB,AC,BC\}|=3  $$

Notera att om vi multiplicera med antalet s\"att att ordna upp tv{\aa} element f\aa r vi:
$$3\cdot 2!=6$$

S{\aa} vi ska multiplicera varje kombination av $k$ element bland $n$ element med antal permutationer av $k$ element f\"or att f{\aa} $P(n,k)$:
$$K(n,k)\cdot k!=P(n,k)= \frac{n!}{(n-k)!}$$
Vi ser att:
$$K(n,k)= \frac{n!}{k!\cdot(n-k)!}$$

$K(n,k)$ kallas {\it binomial koefficienten} och beteknas med $n\choose k$

\vspace{.1in}

\noindent{\it Exempel}
\begin{itemize}
\item Antalet kombinationer av $0$ element ur $n$ element \"ar:
$${n\choose 0}=1$$
\item Antalet kombinationer av $1$ element ur $n$ element \"ar:
$${n\choose 1}=n$$
\item Antalet kombinationer av $n$ element ur $n$ element \"ar:
$${n\choose n}=1$$
\item Antalet kombinationer av $n-1$ element ur $n$ element \"ar:
$${n\choose {n-1}} =n$$
\end{itemize}

\vspace{.1in}

\noindent{\it Exempel}. 
\begin{itemize}
\item En student skall basvara $7$ av $10$ givna fr\aa gor , vid en tantamen. P{\aa} hur m\aa nga s\"att kan hun v\"alja ut dessa?

Vi ser att studenten kan v\"alja utan ordning och s\"akert utan upprepning.
S{\aa} svaret \"ar:
$${10\choose 7}=\frac{10!}{3!\cdot 7!}=120$$
\item Antag att fr\aa gorna \"ar uppdelade i tv{\aa} grupper av fem. Exakt tre f\aa gor fr\aa n den f\"orsta gruppen skall besvaras, och d\"armed fyra fr\aa n den andra.

Studenten ska v\"alja f\"orst tre fr\aa n f\"orsta gruppen och sedan fyra fr\aa n andra. S{\aa} enligt multiplications principen det finns
$${5\choose 3}\cdot {5\choose 4}=50$$
m\aa nga s\"att man kan  v\"alja ut.
\item Antag nu att {\it minst} tre fr\aa gor fr\aa n den f\"orsta gruppen skall besvaras.

Man kan v\"alja exakt $3$ fr\aa gor fr\aa n den f\"orsta gruppen och d\"armed $4$ fr\aa n andra, {\it eller} exakt $4$ fr\aa gor fr\aa n den f\"orsta gruppen och d\"armed $3$ fr\aa n andra {\it eller} exakt $5$ fr\aa gor fr\aa n den f\"orsta gruppen och d\"armed $2$ fr\aa n andra.

Enligt additions principen det finns
$${5\choose 3}\cdot {5\choose 4}+{5\choose 4}\cdot {5\choose 3}+{5\choose 5}\cdot {5\choose 2}=50+50+10=110$$
m\aa nga s\"att man kan  v\"alja ut.
\end{itemize}

\vspace{.1in}

\noindent{\it Exempel}. Best\"am antalet delm\"angder med $k$ element till en m\"angd med $n$ element.

F\"or att bilda en delm\"angd med $k$ element ska man v\"alja $k$ element av $n$, utan upprepning och utan ordning. Faktisk har vi att:
$$\{a_1,a_2,...,a_k\}=\{a_3,a_2,a_1,...,a_k\}$$
S{\aa} det finns ${n\choose k}$ delm\"angder med $k$ element till en m\"angd med $n$ element.

Notera att n\"ar $k=0$ formulan s\"ager att det finns $n\choose 0=1$ delm\"angd med $0$ element, den tomma delm\"angden.


Vi ska nu bevisa tv{\aa} mycket viktiga identiteter:
\begin{enumerate}
\item ${n\choose k}={n\choose n-k}$.

\vspace{.1in}

\item ${n+1\choose k}={n\choose k}+{n\choose k-1}$
\end{enumerate}
\noindent {\it Bevis}.
\begin{enumerate}
\item Heltal ${n\choose k}$ ger hur m\aa nga delm\"angder med $k$ element finns till en m\"angd med $n$ element. Men varje g\aa ngen vi v\"aljer ut en delm\"angd med $k$ element  definerar vi ocks{\aa} en delm\"angd med $n-k$ element, n\"amlingen de som vi l\"amnar kvar. Det betyder att det finns lika m\aa nga delm\"angder med $k$ element som med $n-k$ element.

\item Heltal ${n+1\choose k}$ ger hur m\aa nga delm\"angder med $k$ element finns till en m\"angd med $n+1$ element. L\aa t $A$ vara en m\"angd med $n+1$ element och $x\in A$. Vi kan t\"anka p{\aa} antal delm\"angder med $k$ element som:
$$\text{(Antal delm\"angder som inneh\aa ller }x) + (\text{ Antal delm\"angder som inte inneh\aa ller }x)$$
En delm\"angd som inneh\aa ller $x$ kan bildas genom att v\"alja $k-1$ element av $n$ element, s{\aa} p{\aa} $n\choose k-1$ m\aa nga s\"att.\\
En delm\"angd som inte inneh\aa ller $x$ kan bildas genom att v\"alja $k$ element av $n$ element, s{\aa} p{\aa} $n\choose k$ m\aa nga s\"att.

\end{enumerate}
\noindent
\vspace{.1in}

Som ett f\"oljd av (2) kan man ``gruppera'' binomial koeficienter i den s{\aa} kallade {\it Pascal triangle}. Se sidan 120 i boken.

\vspace{.2in}

\noindent{\it Example}. Visa att:
$${n\choose 0}+{n\choose 1}+...+{n\choose n}=2^n$$
Heltal $2^n$ ber\"aknar antal delm\"angder till en m\"angd men $n$ ellemnt.
Heltal $n\choose i$ ber\"aknar avtal delm\"angder med $i$ element till en m\"angd men $n$ ellemnt. Formulan \"ar allts{\aa} klar!

\vspace{.2in}

\noindent{\it Ovning.} Best\"am antal ord  av lengd $n$ i alfabetet $\{0,1\}$ med exakt $r$ nollor.


Vi anv\"anda ord binomial koefficienter p{\aa} grund av f\"oljande stas:\\
{\it SATS}. Det g\"aller att f\"or $n\geq 1$,
$$(x+y)^n=\sum_{k=0}^n{n\choose k}x^{n-k}y^k$$
{\it Bevis}. Det \"ar klart att $(x+y)^n$ best\aa r av antal termer p{\aa} formen $x^{n-k}y^k$, med $k$ varierande fr\aa n $0$ till $n$. Vi ska visa att f\"or ett fixt $k$ det finns precis ${n\choose k}$ termer  p{\aa} formen $x^{n-k}y^k$.
Vi f\aa r ett term  p{\aa} formen $x^{n-k}y^k$ n\"ar vi tar $y$ exakt $k$ g\aa nger (av $n$). Antal s\"att att v\"alja $k$ g\aa nger $y$ \"ar $n\choose k$.

\vspace{.1in}

\noindent{\it Exempel.} Best\"am den kostanta termen i
$$(2t^4+\frac{1}{t})^{10}$$
Enligt binomialsatsen \"ar:
$$(2t^4+\frac{1}{t})^{10}=\sum_{k=0}^{10} {10\choose k}(2t^4)^{10-k}\cdot\frac{1}{t^k}=\sum_{k=0}^{10} {10\choose k}2^{10-k}t^{40-5k}$$
Vi f\aa r termen inneh\aa llande $t^0$ d{\aa} $40-5k=0$, dvs d{\aa} $k=8$.

Det f\"oljer att kostanta termen \"ar ${10\choose 8}2^{2}=45\cdot 4=180$.


\vspace{.1in}

Nu ska  vi handla om problemet att v\"alja ut $k$ objekt fr\aa n $n$ objekt, UTAN hensyn till ordning och MED upprepning till\aa tet. Det h\"ar \"ar det sv\aa raste av de fyra fallen.

L\aa t,  f\"or varje $i=1,2,...,n$, talet $x_i$ beteckna antalet g\aa nger objekt num. $i$ v\"aljes. 
D{\aa} det m\aa ste vara:
$$x_1+x_2+...+x_n=k\text{ d\"ar }x_i\geq 0, i=1,...,n$$

S{\aa} vi ska best\"amma antalet icke-negativa heltal\"osning till ekvationen.

Svaret \"ar :
$$n+k-1\choose k$$

\noindent{\it Bevis}. Antag att vi har $r$ stycken identiska objekt och vill placera den i $n$ olika l\aa dor. P{\aa} hur m\aa nga s\"att kan man g\"ora det?
Om talet $x_i$ betecknar antalet objekt som l\"aggs i l\aa da nummer $i$ svaret \"ar igen antalet  icke-negativa heltal\"osning till ekvationen:
$$x_1+x_2+...+x_n=k.$$

En placering av $r$ stycken identiska objekt o i $n$ olika l\aa dor kan beskrivas som:
\[ \begin{tabular}{ccccc}
\bullet \bullet ... \bullet & \mid & \bullet \bullet ... \bullet & \mid & ...\\
l\aa da 1 && l\aa da 2 && ...
\end{tabular}\]

S{\aa} vi ska ber\"akna antal permutationer av $(n-1+k)$ objekt ($(n-1)$ stycken $\mid$ och $k$ stycker $\bullet$).
Men antal permutaioner mellam $r$ stycken $\bullet $ och antal permutationer mella $(n-1)$ stycken $\mid$ ger samma placeringen.

S{\aa} totalt har vi
$$\frac{(n-1+k)!}{(n-1)!k!}={n-1+k\choose k}$$.


Vi har ocks{\aa} bevisat att:
{\it Antalet s\"att att placera $r$ stycken identiska objekt  i $n$ olika l\aa dor \"ar}:
$$\frac{(n-1+k)!}{(n-1)!k!}={n-1+k\choose k}$$.

\vspace{.2in}

\noindent{\it Exempel} Best\"am antalet heltalsl\"osningar till:
$$x_1+x_2+x_3+x_4=32$$
s\aa dan att $x_1,x_1\geq 5$ och $x_3,x_4\geq 7$.\\

L\aa t $y_1=x_1-5,y_2=x_2-5,y_3=x_1-7,y_4=x_4-7$. Vi ser att
$$y_1+y_2+y_3+y_4=x_1+x_2+x_3+x_4-(10+14)=8$$
Vi ska hitta alla icke-negativa heltalsl\"osningar till
$$y_1+y_2+y_3+y_4=8$$
Svaret \"ar ${8+4-1\choose 8}=165$.

\vspace{.2in}

\noindent{\it Exempel}. Hur m\aa nga tal kan man bilda av siffrorna $1,2,...,9$ on varje siffra bara f\aa r anv\"andas en g\aa ng och siffrorna skall komma i stotleksording? Exempel p{\aa} till\aa tna tal \"ar $7, 235, 45789$.

Betrakta m\"angden $\{1,2,...,9\}$. Varje  icke-tomma delm\"angd definerar ett tal d\"ar  varje siffra bara  anv\"andas en g\aa ng och siffrorna skall komma i stotleksording. Till exempel: delm\"angden $\{1,4,6\}$ definerar $146$.

S{\aa} svaret \"ar $2^9-1$.


\vspace{.2in}

\noindent{\it Exempel}. Visa att $\frac{(2n)!}{2^n}$ \"ar ett heltal.

Heltal $(2n)!$ ber\"aknar antalet permutationer av $2n$ element.
Betrakta den $2n$ objekt
$$a_1 a_1 a_2 a_2 ... a_n a_n$$
Eftersom vi har tv{\aa} stycken $a_i$ f\"or varje $i=1,...,n$, ber\"aknar $\frac{(2n)!}{2^n}$ antal arrangemang av denna element. S{\aa} den \"ar svaren till ``hur m\aa nga arrangemang finns det av elementen  $a_1,a_1,a_2,a_2,..., a_n,a_n$''. Det f\"oljer att $\frac{(2n)!}{2^n}$ m\aa ste vara ett heltal.

\end{document}

