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

\begin{document}
\maketitle

Vi b\"orjar med n\aa gra r\"akningsprinciper.

\vspace{.2in}

Antag att vi ska v\"alja mellan tv{\aa} objekt, $A$ och $B$, d\"ar $A$ f\"orekommer i $n$ varianter och $B$ f\"orekommer i $m$ varianter. Det betyder att vi har tv{\aa} m\"angder, $A$ med kardinaliteten $n$ och $B$ med kardinaliteten $m$ och vi ska v\"alja ett element i $A$ {\bf eller} ett element i $B$.

  S{\aa} vi ska v\"alja bland elementen i $A\cup B$.
D{\aa} vi kan anta att m\"angder \"ar disjunkta har vi att
$$| A\cup B|=|A|+|B|=n+m$$

S{\aa} det finns $n+m$ varianter att v\"alja ett objekt som f\"orekommer i $n$ varianter eller ett objekt  som f\"orekommer i $m$ varianter. Detta kallas {\it additionsprincipen}.

\vspace{.2in}

Antag att vi har $n$ m\"ojlighet att v\"alja ett objekt i $A$ och $m$ m\"ojlighet att v\"alja ett objekt i $B$ ( samma som tidigare), men antag nu att vi vill v\"alja {\it f\"orst} ett objekt i $A$ och {\it d\"arefter} ett objekt i $B$.

Hur m{\aa}nga alternativ har vi totalt?

H\"ar ska vi ber\"akna antal par $(a,b)$, d\"ar $a\in A$ och $b\in B$, s{\aa}
$|A\times B|=|A|\cdot |B|$. S{\aa} antalet s\"att att v\"alja  f\"orst en av $n$ varianter och  d\"arefter en av $m$ varianter \"ar $n\cdot m$. Det kallas {\it multiplicationsprincipen}.

\vspace{.2in}

\noindent {\it Exempel.} L\aa t $A$ vara en m\"angd. Vi har redan definerat
$$P(A)=\{B\subseteq A\}.$$ Antag $|A|=k$ d{\aa} \"ar
$$|P(A)|=2^k.$$

Man kan faktiskt  bilda en delm\"angd $B\subseteq A$ genom att man g\aa r genom alla element i $A$ och beslutar om de ing{\aa}r i $B$ eller inte.
Eftersom  det finns tv{\aa} alternativ f\"or varje elemnt i $|A|$ kan man t\"anka p{\aa} $B$ som $(Ja, Nej,Nej,...)$, en sekvens med  $|A|$ antal platser, som best{\aa}r av Ja och Nej.
 
 En sekvensen p{\aa} formen $(Ya, Nej,Nej,...)$ kan betraktas som ett elemnet i
$$T\times T\times...\times T\;\;\; |A|\text{ g\aa nger, d\"at }T=\{ Ya, Nej\}$$
Och $|T\times T\times...\times T|=|T|\cdot |T|\cdot...\cdot |T|=2^{|A|}$.

\vspace{.2in}

\noindent {\it Exempel.} Ett vanligt svensk bilnummer best{\aa}r av tre bokst�ver mellan $A$ och $Z$, inklusive $W$, men utan $I$, $Q$ och $V$, f\"oljt av tre siffror.
Hur m\aa nga bilnummer kan man konstruera enligt denna specifikation?

En bilnummer kan skrivas som
$$(Bokstav, Bokstav, Bokstav, Siffra,Siffra, Siffra)$$
L\aa t $B=\{$ bokst\"aver mellan $A$ och $Z$, inklusive $W$, men utan $I$, $Q$ och $V\}$ och $A=\{n\in\nat|  n\leq 9\}$. S{\aa} \"ar $|A|=10$ och $|B|=26-3=23$.
En bilnummer \"ar ett element i $B\times B\times B\times A\times A\times A$.
S{\aa} det finns $10^3\cdot 23^3$ m\aa nga bilnummer som man kan  konstruera enligt denna specifikation.

\section{Permutationer}

Betrakta  m\"angden $A=\{1,2,3,4,5\}$. Om vi vill v\"alja $3$ element i $A$ ``med uppprepning'', dvs att varje elemnt kan v\"aljas mer \"an en g\aa ng har vi $5\cdot 5\cdot 5$ alternativ.

Om vi vill v\"alja $3$ element ``utan upprepning'', dvs att f\"orst vi v\"aljer ett element, sedan v\"aljer vi ett element some \"ar skillt fr\aa n f\"oreg\aa ende element och s{\aa} vidare, d{\aa} har vi bara $5\cdot 4\cdot 3$ alternativ.

Notera att val $(123)$ och $(321)$ \"ar olika. Det betyder att tv{\aa} olika ordning ger tv{\aa} olika val. Vi s\"ager att vi v\"aljar ``med h\"ansyn till ordning''.

S{\aa} man kan v\"alja med eller utan upprepring och med eller utan h\"ansyn till ordning!

Vi ska f\"orst prata om {\bf ordnade urval}.

P{\aa} samma s\"att som tidigare ser vi att:
\begin{itemize}
\item Det finns $n\cdot ...\cdot n$ ($r$ g\aa nger) m\aa nga alternativ att v\"alja $r$ element fr\aa n $n$ element, med uppprepning.
\item Det finns $n(n-1)(n-2)\cdot ... \cdot ( n-r+1)$  m\aa nga alternativ att v\"alja $r$ element fr\aa n $n$ element, utan uppprepning.
\end{itemize}

F\"or att kunna forts\"atta diskussionen beh\"over vi lite mer terminologi.

F\"orst ska vi prata lite om ``ordningen''.

\begin{definition}
Varje uppst\"allning av ett antal olika objekt i n\aa gon ordning kallas {\it permutation} av dessa objekt.
\end{definition}

Hur kan man ``konstruera'' en permutation? Om vi har $n$ objekt kan vi f\"orst best\"amma objekt som ska st{\aa} p{\aa} plats 1, sedan objekt p{\aa} plats $2$ , och s{\aa} vidare.
Vi ser allts{\aa} att antalet permutationer \"ar lika med antalet alternativ att v\"alja, utan upprepning och med h\"ansyn till ordning $n$ element av $n$ element s{\aa}:
$$n(n-1)(n-2)(n-3)...2\cdot 1$$
Detta heltal betecknas med $n!$ (n fakultet).

\vspace{.1in}

\noindent{\it Exempel.} Antalet  permutationer mellan $A,B,C$ \"ar $3!=6$

De \"ar: $ABC, ACB, BAC, BCA, CAB, ABA$.

Notera att:
\begin{itemize}
\item vi s\"att $0!=1$.
\item $n!=n\cdot (n-1)!.$
\end{itemize}

Genom att anv\"anda ``fakultetsbeteckningen'' kan man skriva:
$$n(n-1)\cdot (n-r+1)=\frac{[n(n-1)\cdot (n-r+1)](n-r)!}{(n-r)!}=\frac{   n(n-1)(n-2)(n-3)...2\cdot 1}{(n-r)!}=\frac{n!}{(n-r)!}$$

Vi ska anv\"anda symbolen $P(n,r)$ f\"or antalet s\"att att v\"alja $r$ objekt mellan $n$ olika objekt med h\"ansyn till ordning och utan upprepning. S{\aa}:
$$P(n,r)=\frac{n!}{(n-r)!}.$$

\vspace{.1in}

\noindent{\it Exempel.} Best\"am antalet $6$ siffriga j\"amna heltal  om ingen siffra f\"orekommer mer \"an en g\aa ng.

J\"amna heltal slutar med en j\"amn siffra, $0,2,4,6,8$.
Vi ska ber\"akna antal s\"att att v\"alja $6$ siffror, utan upprepning n\"ar 
\begin{itemize}
\item f\"orsta siffra kan v\"aljas bland $1,...,9$
\item f\"oljande $4$  kan v\"aljas bland  $0$ och $9$  
\item sista kan v\"aljas bland $0,2,4,6,8$.
\end{itemize}
Det \"ar l\"attare att dela upp alternativ i tvaa grupper:
\begin{enumerate}
\item heltal som slutar  med $0$
\item heltal d\"ar sista siffran \"ar skild fr\aa n $0$.
\end{enumerate}
 Enligt multiplikations principen  finns det
$9\cdot 8\cdot 7\cdot 6\cdot 5=15120$ element i f\"orsta gruppen.

F\"or att ber\"akna antal element i andra gruppen b\"orjar vi p{\aa} sista siffran (d\"ar vi har 4 olika alternativ) och sedan forts\"atter vi fr\aa n f\"orsta siffran. S{\aa} det finns
$4\cdot 8\cdot 8\cdot 7\cdot 6\cdot 5= 53760$ m\aa nga alternativ.

Totalt har vi $53760+15120$

\vspace{.1in}

\noindent{\it Exempel.}
\begin{itemize}
\item Antalet permutationer av bokst\"averna i BL{\AA}GR\"ON \"ar
$$7!=7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1=5040.$$
\item Om vi vill bara v\"alja $4$  bokst\"aver kan vi 
g\"ora s{\aa} det $P(7,4)$ olika s\"att:
$$P(7,4)=\frac{7!}{(7-4)!}=7\cdot 6\cdot 5\cdot 4=840   $$
\item Om vi vill v\"alja $4$  bokst\"aver med uppr\"apning har vi
$$7^4= 2401$$
m\aa nga alternativ.
\end{itemize}

Idag har vi visat att:
\begin{itemize}
\item Det finns $n!$ s\"att att ordna upp $n$ ebjekt.
\item Antal s\"att att v\"alja $k$ element bland totalt $n$, med h\"ansyn till ordning och med upprepning \"ar $n^k$.
\item Antal s\"att att  v\"alja $k$ element bland totalt $n$, med h\"ansyn till ordning och utan upprepning \"ar $\frac{n!}{(n-k)!}$.
\end{itemize}
\end{document}