SF1671 Matematik, baskurs, med diskret matematik 7,5 hp

Tillfälleskod	Termin(er)	Period(er)	Föreläsare
51354	HT2023	1	Petter Brändén

Föreläsning 11

Kardinalitet

Definition: $|X|=|Y|$ omm det finns en bijektion $f:X\rarr Y$.

"Att ha samma kardinalitet" är en ekvivalensrelation, där ekvivalensklasserna kallas för kardinaltal.

Bevis: $X\mathrel{R} Y \iff |X| = |Y|\iff$ Finns en bijektion sådan att $f:X\rarr Y$

Reflexiv ($X\mathrel{R}X$ för alla $X$): Vi söker en bijektion $f:X\rarr X$. En sådan är $f(x)=x$ (identitetsfunktionen).
$\therefore\space\mathrel{R}$ är reflexiv.
Symmetrisk ($X\mathrel{R}Y\implies Y\mathrel{R}X$): Antag VL sant, då finns en bijektion $f:X\rarr Y$. Inversen av denna är $f^{-1}:Y\rarr X$, vilket också är en bijektion, och därmed $Y\mathrel{R} X$.
$\therefore\space\mathrel{R}$ är symmetrisk. Transitiv ($X\mathrel{R}Y\text{ och }Y\mathrel{R}Z\iff X\mathrel{R}Z$): Visas lättas med en figur. Vi får att HL är sant omm VL.

Med detta kan vi visa att alla öppna intervall av reella tal har samma kardinalitet:

$|(0,1)| = |(1,\infin)|$, eftersom $f(x)=\frac{1}x$ är en bijektion
Om $a\in\mathbb{R}$ så är $|(0,\infin)|=|(a,\infin)|$, eftersom $f(x)=x+a$ är en bijektion.
Om $a\lt b$ så är $|(0,1)|=|(a,b)|$, eftersom $f(x)=a+(b-a)x$ är en bijektion.
$\mathbb{R}=|(0,\infin)|$ eftersom $f(x)=e^{x}$ är en bijektion.

Hilberts hotell

Hilberts hotell har oändligt många rum $\{0,1,2,3,...\}$. När du ska checka in meddelar de att alla rum är upptagna. Hur kan det lösas?

Lösning: Vi flyttar varje gäst ett steg, så att rum 0 blir ledigt: $f:\{0,1,2,3,...\}\rarr\{1,2,3,4,...\}$
$f(x)=x+1$ är en bijektion, vilket ger:
$|\{0,1,2,3,...\}|=|\mathbb{N}|=|\mathbb{Z_+}|=|\{1,2,3,...\}|=\aleph_0$
$\aleph_0$ ("alef-noll") och är kardinaltalet för alla uppräkneligt oändliga mängder.

Vi visar att $|(0,1)|=|[0,1)|$:

Bevis: Tag en följd $a_0,a_1,a_2,a_3,...\in[0,1)$
Antag en funktion $f:[0,1)\rarr(0,1)$ och att $f(a_i)=a_{i+1}$ om $x=a_i$, i övriga fall $f(x)=x$.
Inversen blir $f^{-1}(a_i)=a_{i-1}$ om $x=a_i$, i övriga fall $f^{-1}(x)=x$.
Funktionen är alltså en bijektion.

Med samma princip får vi att *alla intervall, förutom $[a,a]$, har samma kardinalitet som $\mathbb{R}$.

En mängd $X$ är uppräkneligt oändlig om $|X|=|\mathbb{Z_+}|\iff$finns en bijektion $f:X\rarr\mathbb{Z_+}$.

Cantors diagonalargument

Sats: Om $A_1,A_2,...$ är ändliga eller uppräkneligt oändliga, så är $A=A_1\cup A_2\cup ...$ också ändlig eller uppräkneligt oändlig.

Bevis: Vi vill hitta en bijektion $f:\mathbb{Z_+}\rarr A$
Vi kan rita upp en tabell så att elementen i $A_i$ hamnar på rad $i$.
Det går nu att koppla samman "samtliga" element genom att dra en pil från övre vänstra hörnet till elementet till höger, och därefter diagonalt nedåt och uppåt, om vartannat.
Obs! Vi måste hoppa över tal som redan har räknats --- annars ej bijektion!

Med hjälp av detta kan vi visa att $\mathbb{Q}$ är uppräkneligt oändlig, dvs. att $|\mathbb{Q}|=\aleph_0$:

$A_i=\{\frac{x}{i}|x\in\mathbb{Z}\}=\text{"alla rationella tal med nämnare \it{i}"}$
$\mathbb{Q}=A_1\cup A_2\cup ...$
Enligt Cantors diagonalargument är $|\mathbb{Q}|=\aleph_0$.

Mer om kardinalitet

Schröder-Bernsteins sats
Antag två injektioner $f:X\rarr Y$ och $g:Y\rarr X$. Då är $|X|=|Y|$.

Följdsats A: Om $A\subseteq B\subseteq C$ och $|A|=|C|$, så är $|A|=|B|=|C|$.
Följdsats B: Varje intervall (förutom $[a,a]$) har samma kardinalitet som $\mathbb{R}$.

Sats: $|\mathcal{P}(\mathbb{Z_+})|=|\mathbb{R}|$

$|\mathbb{R}|$ kallas för kontinuumet (eng. continuum)

Bevis:
VL ger att $\mathcal{P}(\mathbb{Z_+})=\{A|A\subseteq Z_+\}$
Vi använder Schröder-Bernsteins sats, dvs. vi vill hitta injektioner:
$f:[0,1)\rarr\mathcal{P}(\mathbb{Z_+})$ och $g:\mathcal{P}(\mathbb{Z_+})\rarr[0,1)$

Alla $x\in[0,1)$ kan skrivas på binär form: $x=0,a_1a_2a_3a_4...$ där $a_i=0\text{ eller }1$ T.ex. $x=0,0010000111001...$

Obs! För att få unikhet så skippar vi tal som slutar på oändlig följd av 1:or. Jämför: $0,999...=1$

Steg 1: Vi definierar $f(x)=\{i|a_i=1\}$, vilket ger $f(0,11010001000...)=\{1,2,4,8\}$.
Detta är en injektion eftersom "olika går på olika".

Steg 2: Vi definierar $g(A)=0,a_1a_2a_3a_4...$ där $a_i=\{1\text{ om }i\in A\text{ eller }0\text{ om }i\notin A\}$
Detta är också en injektion.

V.S.B.

Föreläsning 15

Satslogik

Definition: En sats är ett påstående som kan vara sann eller falsk.

Nya satser bildas med operationer:

$p\lor q$ är sann om minst en av $p$ och $q$ är sanna.
$p\land q$ är sann om både $p$ och $q$ är sanna.
$p\rarr q$ "om $p$ är sann, så måste $q$ också vara sann".
$p\lrarr q$ är sann om $p = q$.
$\lnot p$ är sann om $p$ är falsk.

En satsoperation kan visas med en sanningstabell:

$p$	$q$	$p\rarr q$
0	0	1
0	1	1
1	0	0
1	1	1

En sats är sammansatt om den är uppbyggd av andra satser genom $\lor$, $\land$, $\rarr$, $\lrarr$, $\lnot$. Icke-sammansatta satser kallas för atomära satser.

En sammansatt sats kan ses som en funktion $f: \{0,1\}^n\rarr\{0,1\}$.
En sammansatt sats $S$ kan beskrivas med hjälp av atomära satser $p_1,\dots,p_n$: $S(p_1,p_2,\dots,p_n)=0\text{ eller }1$

Sats: Varje funktion $f:\{0,1\}^n\rarr \{0,1\}$ kan representeras av en sammansatt sats som endast använder $\land$, $\lor$ och $\lnot$.

Bevis:
Vi har $\{0,1\}^n=\{0,1\}\times\dots\times\{0,1\}=\{(p_1,\dots,p_n)|p_i=0,1\text{ för alla }i\}$
Detta ger t.ex.
$\{0,1\}^2=\{(0,0),(0,1),(1,0),(1,1)\}$

Bevis med induktion
Basfall: $n=1$, $f:\{0,1\}\rarr\{0,1\}$
Fyra möjligheter ($f_1,f_2,f_3,f_4$): Alla kan skrivas med operatorerna $\land$, $\lor$ och $\lnot$.

$p_1$ $f_1(p_1)\\=p_1\land(\lnot p_1)$ $f_2(p_1)\\=p_1\lor p_1$ $f_3(p_1)\\=\lnot p_1$ $f_4(p_1)\\=p_1\lor(\lnot p_1)$

0 0 0 1 1

1 0 1 0 1

Induktionsantagande: Antar att påståendet är sant för $n$, det vill säga att det finns en sats $S(p_1,\dots,p_n)=f(p_1,\dots,p_n)$

Induktionssteg: Visa att påståendet då även är sant för $n+1$.
Vi tar en godtycklig funktion $f:\{0,1\}^{n+1}\rarr\{0,1\}$.
Vi bildar sedan två funktioner $g$ och $h$:
$g(p_1,\dots,p_n\}=f(p_1,\dots,p_n,1)$ och
$h(p_1,\dots,p_n\}=f(p_1,\dots,p_n,0)$

Enligt induktionsantagandet kan $g$ och $h$ även beskrivas av satser:
$g(p_1,\dots,p_n)=S_1(p_1,\dots,p_n)$
$h(p_1,\dots,p_n)=S_2(p_1,\dots,p_n)$

Då är
$f(p_1,\dots,p_n,p_{n+1})=(p_{n+1}\land S_1(p_1,\dots,p_n))\cup((\lnot p_{n+1})\land S_2(p_1,\dots,p_n))$

Tautologi: En sammansatt sats som alltid är sann.

Bevis av satser

Implikation: Vi vill visa $p\implies q$.
- Direkt: Anta $p$ och härled $q$
- Kontrapositivt: Anta $\lnot q$ och härled $\lnot p$
Disjunktioner: Vi vill visa $p\lor q$.
- Vi vet $(p\lor q)\lrarr((\lnot p)\rarr q)$. Anta att $p=0$ och visa att $q$ då måste vara sann.
- Motsägelsebevis: Anta $\lnot p\land\lnot q$ och härled något absurt.
Ekvivalens:
- Vi vet $(p\lrarr q)\iff((p\rarr q)\land(q\rarr p)$. Visa att båda implikationerna gäller.

Sannolikhetslära

$\Omega$ är utfallsrummet, en ändlig mängd med alla möjliga utfall.

Händelse: En delmängd $A$ till $\Omega$.
Sannolikhet: $P(A)=\frac{|A|}{|\Omega|}$

Additionsprincipen: Om två händelser $A$ och $B$ är disjunkta ($A\cap B=\empty$, dvs. inte kan inträffa samtidigt), så är $P(A\text{ eller }B)=P(A\cup B)=\frac{|A\cup B|}{|\Omega|}=\frac{|A|+|B|}{|\Omega|}=P(A)+P(B)$.

Betingad sannolikhet: $P(A\text{ givet }B)=P(A|B)=\frac{|A\cap B|}{|B|}$

Exempel: Anta att vi kastar två tärningar och ett orakel informerar att minst en tärning kommer att vara udda (händelse $B$). Vad är sannolikheten att vi får två ettor (händelse $A$)?
Vi vet att $B$ kommer att inträffa.
$|B|=|\{(a,b)|a\text{ och/eller }b\text{ är udda}\}|=6^2-|\{(a,b)|\text{båda är jämna}\}|=36-3^2=27$
$|A\cap B|=1$ (endast fallet $(1,1)$)
$P(A\cap B)=\frac{|A\cap B|}{|B|}=\frac{1}{27}$

Oberoende händelser: $A$ och $B$ är oberoende om sannolikheten för att den ena inträffar är oberoende av om den andra inträffar. Dvs. $P(A|B)=P(A|B^\complement)$

Multiplikationsprincipen: För oberoende händelser är $P(A\land B)=P(A)\cdot P(B)$

Föreläsning 16

Kombinatorik (med upprepning)

Antag att vi ska utföra två deluppgifter, $X$ och $Y$, och att $X$ kan göras på $x$ sätt, $Y$ på $y$ sätt. Den sammansatta uppgiften kan göras på $|X\times Y|=|X|\times |Y|=x\cdot y$ sätt.

Exempel: $A$ och $B$ är ändliga mängder. Hur många funktioner $f:A\rarr B$ finns det?
För varje $a\in A$ finns det $|B|$ möjliga värden $b\in B$.
Olika $a$ kan ge samma $b$ (dock inte tvärt om).
$\therefore$ Upprepning tillåts.
Svar: Det finns $|B|^{|A|}$ funktioner $f$.

Utan upprepning

En följd $a_1,a_2,\dots,a_n$ kallas för en permutation av mängden $\{a_1,a_2,\dots,a_n\}$.

Exempel: På hur många sätt kan $n$ personer bilda en kö?
Varje kö kan ses som en permutation $a_1,\dots,n$ av mängden av alla personer, $\{1,2,\dots,n\}$.
Vi kan välja $a_1$ på $n$ olika sätt.
Vi kan välja $a_2$ på $n-1$ olika sätt ($a_1$ är upptagen)
$\cdots$
Vi kan välja $a_n$ på $1$ sätt (alla andra är upptagna)
Svar: $n(n-1)\cdots3\cdot2\cdot1=n!$ ($n$-fakultet)

Hur många köer med $k$ personer kan vi bilda ur totalt $n$ personer?
Svar: Vi kan bilda $\frac{n!}{(n-k)!}$

På motsvarande sätt kan vi skapa injektiva funktioner
$f:\{1,2,3,4,5\}\rarr\{1,2,3,4,5,6,7,8,9\}$
på $\frac{9!}{(9-5)!}=9\cdot8\cdot7\cdot6\cdot5$ sätt.

Exempel: Vad är sannolikheten att jag i poker får Imperial Royal Straight Flush på given?
$A=\{\text{"hjärter 10, knekt, dam, kung och ess"}\}$
$\Omega=\{\text{alla möjliga givar med 5 kort}\}=\{T|T\subseteq\{1,2,\dots,52\}\land|T|=5\}$
$P=\frac1{|\Omega|}$

För att göra oordnade val utan upprepning använder vi binomialtal.

Binomialtal

Binomialtalet $\binom{n}{k}$ definieras som antalet delmängder av $\{1,2,\dots,n\}$ av storlek $k$.
Detta gäller för $0\leq k\leq n$, i andra fall $\binom{n}{k}=0$.

\[\binom{n}k=\frac{n!}{k!(n-k)!}\]

Bevis: En kö $a_1,a_2,\dots,a_k$ med element ur $n$ möjliga kan bildas på $\frac{n!}{(n-k)!}$ sätt.
Vi kan också räkna antalet köer på följande sätt:
(1) Vi väljer vilka som ska vara med i kön:$\binom{n}{k}$
(2) Vi bestämmer deras inbördes ordning: $k!$

$\frac{n!}{(n-k)!}=\binom{n}k\cdot k!$
$\therefore\binom{n}k=\frac{n!}{k!(n-k)!}$

Binomialtalens symmetri:

\[\binom nk=\binom n{n-k}$, där $0\leq k\leq n\]

Bevis:
Beteckningar:
$[n]=\{1,2,3,\dots,n\}$
$\binom{[n]}k$ är mängden av alla delmängder till $[n]$ av storlek $k$

$\therefore|\binom{[n]}k|=\binom nk$

För att visa $\binom nk=\binom n{n-k}$ så kan vi hitta en bijektion $f:\binom{[n]}k\rarr\binom{[n]}{n-k}$

Svar: Vi finner $f(S)=S^C=[n]\setminus S$

Pascals triangel:

$0$				$\binom00$
$1$			$\binom10$		$\binom11$
$2$		$\binom20$		$\binom21$		$\binom22$
$3$	$\binom30$		$\binom31$		$\binom32$		$3\choose3$

För heltal $0\leq k\leq n>0$ är $\binom nk=\binom{n-1}k+\binom{n-1}{k-1}$.

Bevis:
$\binom{[n]}k=\binom{[n-1]}k\cup\{S\cup\{n\}|S\in\binom{[n-1]}{k-1}\}$
Alla mängder t.h. innehåller $n$, medan inga t.h. gör det.
$\therefore$ Unionen är disjunkt.

Vi skriver om detta med kardinaliteter, enligt additionsprincipen:
$|\binom{[n]}k|=\binom{n-1}k+\binom{n-1}{k-1}$

Binomialsatsen

För alla heltal $n\geq 0$ är

\[(1+x)^n=\sum_{k=0}^n \binom nk x^k\]

Bevis (induktion):
Basfall: $n=0$
$\text{VL}_0=(1+x)^0=1\text{, HL}_0=\binom00 x^0=1$

Induktionsantagande: Anta sant för $n-1$.

Induktionssteg: Bevisa för $n$.
$\text{VL}_n=(1+x)^n=(1+x)(1+x)^{n-1}\\=\{\text{induktionsantagandet}\}\\=(1+x)(\sum_{k=0}^{n-1}\binom{n-1}k x^k)\\=\sum_{k=0}^{n-1}\binom{n-1}k x^k+\sum_{k=0}^{n-1}\binom{n-1}k x^{k+1}\\=\{\text{variabelsubstitution }j=k+1\}\\=\sum_{j=0}^{n-1}\binom{n-1}j x^j+\sum_{j=1}^n\binom{n-1}{j-1} x^j\\=\sum_{j=0}^{n}\binom{n-1}j x^j+\sum_{j=0}^n\binom{n-1}{j-1} x^j\\=\sum_{j=0}^{n}(\binom{n-1}j+\binom{n-1}{j-1}) x^j=\{\text{Pascal}\}\\=\sum_{j=0}^{n}\binom{n}{j} x^j=\sum_{k=0}^{n}\binom{n}{k} x^k$

$\therefore$ Sant enligt induktionsprincipen.

Föreläsning 17

Binomialtal

Vi sätter in $x=-1$ i binomialsatsen: $(x+1)^n=((-1)+1)^n=0^n=0$
Vi får då $0=\sum_{k=0}^n\binom nk (-1)^k=1-\binom n1+\binom n2-\binom n3+\dots=(1+\binom n2+\binom n4+\dots)-(\binom n1+\binom n3+\dots)=\text{"antal delmängder av jämn storlek"}-\text{"antal delmängder av udda storlek"}=0$

Vi kan visa detta:
$J_n=\{S|S\subseteq\{1,2,\dots,n\}\land|S|\text{ jämn}\}$
$U_n=\{S|S\subseteq\{1,2,\dots,n\}\land|S|\text{ udda}\}$

Hitta en bijektion $f:J_n\rarr U_n$:
$f(S)=\begin{cases}S\setminus\{1\}\text{, om }1\in S\\S\cup \{1\}\text{, om }1\notin S\end{cases}$

En bijektion eftersom $f(f(S))=S$ för alla S.

Oordnat, utan upprepning

Exempel: 186 studenter ska ha övningar i 4 olika salar med 36, 42, 45 och 63 platser vardera. På hur många olika sätt kan studenterna fördelas?

(1) Välj vilka som ska sitta i sal 1: $\binom{186}{36}$
(2) Välj vilka som ska sitta i sal 2: $\binom{186-36}{42}$
(3) Välj vilka som ska sitta i sal 3: $\binom{186-36-42}{45}$
(4) Välj vilka som ska sitta i sal 4: $\binom{63}{63}=1$

Valen är oberoende, multiplikationsprincipen gäller:
Svar: $\binom{186}{36}\binom{186-36}{42}\binom{186-36-42}{45}\binom{63}{63}$

Vi kan förenkla detta:
$\frac{186!}{36!(186-36)!}\frac{(186-36)!}{42!(186-36-42)!}\frac{(186-36-42)!}{45!(186-36-42-45)!}=\frac{186!}{36!\cdot42!\cdot45!\cdot63!}$

Multinomialtal: Anta $k_1+k_2+\cdots+k_m=n$.

Multinomialtalet $\binom{n}{k_1,k_2,\dots,k_m}$ antalet sätt att fördela talen $\{1,2,\dots,n\}$ i $m$ stycken lådor så att låda $x$ får $k_x$ element.
Sats:** $\binom{n}{k_1,k_2,\dots,k_m}=\frac{n!}{k_1!k_2!\cdots k_m!}$

Exempel: Hur många olika ord kan man bilda av bokstäverna $\text{MISSISSIPPI}$?
Vi antar positionerna $\{1,2,\dots,11\}$ och väljer vilka som ska varje bokstav.
Bokstaven $\text I$ finns t.ex. 4 ggr, och "rymmer" därför 4 av positionerna. Osv.
Svar: $\binom{11}{4,1,2,4}=\frac{11!}{4!\cdot1!\cdot2!\cdot4!}$

Ordnat val med upprepning:

Antalet sätt att ordna $n$ stycken objekt, där man har $k_m$ av $m$:e slaget, är:

\[\binom n{k_1,k_2,\dots,k_m}=\frac{n!}{k_1!\cdot k_2!\cdots k_m!}\]

Exempel: Hur många ord med 4 bokstäver kan man bilda ur $\text{"STOLLE"}$?

Två fall:
(1) Högst ett "L" förekommer. Vi väljer då 4 (utan upprepning): $5\cdot4\cdot3\cdot2$
(2) Exakt två "L" förekommer.
(2.1) Välj plats för båda "L": $\binom 42$ (ordning ej viktigt här)
(2.2) Välj 2 av $\text{"STOE"}$ (ordning viktigt): $4\cdot3$

Svar: $5\cdot4\cdot3\cdot2+\binom 42\cdot4\cdot3$

Exempel: Låt $\mathcal M$ vara mängden av alla ord som kan bildas ur $\text{"RAGGARGRANEN"}$.

(a) Bestäm $|\mathcal M|$.

Vi har 3 st "A", 1 st "E", 3 st "G", 2 st "N" och 3 st "R".

Svar: $\binom{12}{3,1,3,2,3}=\frac{12!}{3!\cdot1!\cdot3!\cdot2!\cdot3!}$

(b) Hur många ord i $\mathcal M$ innehåller $\text{"GRENAR"}$?

Vi har t.ex. "RAGGRENARGAN".
Ordet "GRENAR" kan finnas på 7 platser.
För var och en av dessa alternativ väljer vi bokstav (AAGGNR) åt återstående 6 teckenpositioner: $\binom{6}{2,2,1,1}=\frac{6!}{2\cdot2}=\frac{6!}4$

Svar: $7\cdot\frac{6!}4=\frac{7!}4$ ord

(c) Hur många ord i $\mathcal M$ innehåller varken $\text{GRENAR}$ eller $\text{NARRA}$?

Vi har t.ex. "GRENARRAGGNA".
$S=\{\text{ord som innehåller "GRENAR"}\}$
$T=\{\text{ord som innehåller "NARRA"}\}$

Vi söker:
$|\mathcal M\setminus(S\cup T)|=|\mathcal M|-|S\cup T|=|\mathcal M|-(|S|+|T|-|S\cap T|)=|\mathcal M|-|S|-|T|+|S\cap T|$
$|T|=8\binom{7}{3,1,1,1,1}=\frac{8\cdot7!}6$
$|S\cap T|$ stycken innehåller "GRENARRA" (enda sättet för skapa båda orden samtidigt med givna bokstäver)
$|S\cap T|=5\binom{4}{2,1,1}=\frac{5\cdot4!}2$

Svar: $|\mathcal M|-|S|-|T|+|S\cap T|=\frac{12!}{2\cdot6^3}-\frac{7!}4-\frac{8\cdot7!}6+\frac{5\cdot4!}2$ ord

Multinomialsatsen

\[(x_1+\dots+x_m)^n\\=\sum_{k_1+\dots+k_m=n}\binom n{k_1,k_2,\dots,k_m}x_1^{k_1}\cdots x_m^{k_m}\]

T.ex.

\[(x_1+x_2+x_3)^3\\=\binom 3{3,0,0}x_1^3+\binom 7{2,1,0}x_1^2x_2+\binom 3{1,1,1}x_1x_2x_3\\=x_1^3+\frac {3!}{2!}\cdot x_1^2x_2+3!\cdot x_1x_2x_3+\dots\\=x_1^3+3x_1^2x_2+6x_1x_2x_3+\dots\]

Exempel: Vad är koefficienten framför $x^3y^5z^{24}$ i $(x+y+z^2)^{20}$?

Vi gör variabelbyte $w=z^2$, vilket ger
$(x+y+z^2)^{20}=(x+y+w)^{20}=\sum_{k_1,k_2,k_3}\binom{20}{k_1,k_2,k_3}x^{k_1}y^{k_2}w^{k_3}$

Vi söker koefficienten framför $x^3y^5z^{24}=x^3y^5w^{12}$.
$\therefore k_1=3,k_2=5,k_3=12$

Svar: $\binom{20}{3,5,12}=\frac{20!}{3!\cdot5!\cdot12!}$

Kompositioner

Exempel: På hur många sätt kan man fördela $n$ identiska kulor i lådor $1,2,\dots,k$, så att ingen låda blir tom?

Vi har $n-1$ möjliga "mellanrum": $1|_{_1}2|_{_2}\cdots|_{_{n-1}}n$
Vi vill ha $k$ lådor och väljer därför $k-1$ mellanrum:
T.ex. $(1,2|_{_1}3,4,5|_{_2}\dots|_{_{k-1}}n)$
Detta kallas för en komposition av $n$ element i $k$ delar.
Svar: Vi kan fördela kulorna på $\binom{n-1}{k-1}$

Ekvationen $x_1+x_2+\cdots+x_k=n, x_i>0\text{ för alla }i$ har $\binom{n-1}{k-1}$ lösningar.

Om lådor får vara tomma?
Vi antar $y_i=\text{antalet kulor i låda }i$.
Det ger ekvationen $y_1+\cdots+y_k=n,\ y_i\geq0$.
Substitution: $x_i = y_i+1$
$x_1+x_2+\dots+x_k=(y_1+1)+\dots+(y_k+1)\\=y_1+\dots+y_k+k\\=n+k$
Svar: $\binom{n+k-1}{k-1}$

Man kan tänka att man räknar som tidigare, men att man tillför $k$ "tomma" element (ett för varje låda).

Föreläsning 18

Oordnade val med upprepning

En multimängd är en mängd där upprepade element tillåts.

$\{2,3,3,2,4,6,4\}\neq\{2,3,4,6\}$
$\{2,3,3,2,4,6,4\}$ har storleken $7$.
Ordning har ingen betydelse, endast antalet är viktigt!

Hur många multimängder av storlek $n$ med element från $\{1,2,\dots,k\}$ finns det?
Låt $y_i$ vara antalet element $i$ i en multimängd.
$y_1+y_2+\dots+y_k=n$

Lösningen ges av $\binom{n+k-1}{k-1}$.
Svar: Det finns $\binom{n+k-1}{k-1}$ stycken.

Exempel: Olga ska köpa lördagsgodis. I butiken finns 7 sorters godis och hon får välja exakt 15 godisar. På hur många sätt kan hon välja innehållet i godispåsen?

Godispåsen motsvarar en multimängd av storlek 15.
Vi räknar kompositioner: $n=15,\ k=7$

Svar: På $\binom{15+7-1}{7-1}=\binom{21}6$ sätt.

Exempel: Hur många heltalslösningar finns det till
$x_1+x_2+x_3+x_4\leq14$, där $\begin{cases}x_1\geq-3\\x_2\geq2\\x_3\geq-5\\x_4\geq3\end{cases}$?

Vi vill skriva om ekvationen på en form som vi känner igen. Vi sätter $x_5=\text{HL}-\text{VL}$. Detta ger:
$\iff x_1+x_2+x_3+x_4+x_5=14$

Variabelsubstitutionen så att alla termer $\geq0$:
$\begin{cases}y_1=x_1+3\\y_2=x_2-2\\y_3=x_3+5\\y_4=x_4-3\\y_5=x_5\end{cases}$
$\iff y_1+y_2+y_3+y_4+y_5=(x_1+3)+(x_2-2)+(x_3+5)+(x_4-3)+x_5\\=x_1+x_2+x_3+x_4+x_5+3=14+3=17$

Svar: Denna kan lösas på $\binom{17+5-1}{5-1}=\binom{21}4$ sätt!

Postfacksprincipen (Dirichlets lådprincip)

Om fler än $k$ objekt ska objekt i $k$ lådor, så måste minst en låda innehålla $\geq2$ element.
Alt: Om $X,Y$ är ändliga mängder och $|X|>|Y|$, så finns det ingen injektion $f:X\rarr Y$
(Injektioner måste ge unikt $y$ för unikt $x$).

Principen om inklusion/exklusion

Om $A-1,\dots,A_n$ är ändliga mängder så är

\[|A_1\cup A_2\cup\cdots\cup A_n|=|A_1|+|A_2|+\cdots+|A_n|\\-|A_1\cap A_2|-|A_1\cap A_3|-\cdots-|A_{n-1}\cap A_n|\\+|A_1\cap A_2\cap A_3|+\cdots+|A_{n-2}\cap A_{n-1}\cap A_n|\\\ddots\\+(-1)^{n+1}\ddots|A_1\cap A_2\cap A_3\cap\cdot\cap A_n|\]

Hur uttrycker vi $|u\setminus(A_1\cup A_2\cup\cdots\cup A_n)|$?

$u$ är universum, dvs. $A_i\subseteq u\text{ för alla }i$.
$|u\setminus(A_1\cup A_2\cup\cdots\cup A_n)|\\=|u|-(A_1\cup A_2\cup\cdots\cup A_n)|\\=|u|-(|A_1|+\cdots+|A_n|)$

Exempel: Utav 200 studenter deltog $|F|=172$ på föreläsningar, $|O|=130$ på övningar och $|S|=150$ på seminarier. $|F\cap S|=142,\ |F\cap O|=125,\ |S\cap O|=123,\ |F\cap S\cap O|=120$
Hur många deltog inte i något av momenten?

Vi söker $|u\setminus(F\cup O\cup S)|$, där $u=\text{studenterna}$.
$|u\setminus(F\cup O\cup S)|$=$|u| - |F|-|O|-|S|+|F\cap S|+|F\cap O|+|S\cap O|-|F\cap S\cap O|=200-172-130-150+142+125+123-120=18$ Svar: 18 elever.

\(p_1\)	\(f_1(p_1)\\=p_1\land(\lnot p_1)\)	\(f_2(p_1)\\=p_1\lor p_1\)	\(f_3(p_1)\\=\lnot p_1\)	\(f_4(p_1)\\=p_1\lor(\lnot p_1)\)
0	0	0	1	1
1	0	1	0	1

\(0\)				\(\binom00\)
\(1\)			\(\binom10\)		\(\binom11\)
\(2\)		\(\binom20\)		\(\binom21\)		\(\binom22\)
\(3\)	\(\binom30\)		\(\binom31\)		\(\binom32\)		\(3\choose3\)

\(p\)	\(q\)	\(p\rarr q\)
0	0	1
0	1	1
1	0	0
1	1	1