Kombinatorik och sannolikhet¶

Att räkna låter som det lättaste i matematiken, och det är precis fällan. Formlerna här är korta; svårigheten är att det är farligt lätt att räkna samma sak två gånger, eller att räkna något man inte menade. Den professionella vanan som förhindrar detta är enkel: innan du skriver ett enda tal, säg högt vad ett av tingen du räknar faktiskt är. "Jag räknar strängar av 5 siffror där…" — få den meningen rätt så väljer formeln oftast sig själv.

Att välja rätt modell¶

Nästan varje räkneproblem är en av fyra standardformer. För att hitta vilken, ställ två frågor om tinget du bygger:

Spelar ordningen på valen roll? (Är \(ab\) olikt \(ba\)?)
Får ett val upprepas? (Kan du välja samma element två gånger?)

Ordning?	Upprepning?	Antal	Namn
Ja	Ja	\(n^k\)	Följder / ord
Ja	Nej	\(\dfrac{n!}{(n-k)!}\)	Permutationer av \(k\) ur \(n\)
Nej	Nej	\(\dbinom{n}{k}\)	Kombinationer / delmängder
Nej	Ja	\(\dbinom{n+k-1}{k}\)	Multimängder (stjärnor och streck)

Skaffa vanan att besvara de två frågorna först, och läs sedan av raden. De flesta felsvar kommer av att gripa en formel innan man fastställt dessa två fakta.

Binomialkoefficienter¶

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

Detta räknar antalet sätt att välja en oordnad mängd av \(k\) ting ur \(n\).

Var formeln kommer ifrån. Ställ först upp \(k\) val i ordning: \(n\) sätt för det första, \(n-1\) för det andra, ner till \(n-k+1\) — det är \(\frac{n!}{(n-k)!}\). Men vi ville inte ha ordning, och varje oordnad mängd av \(k\) räknades en gång för var och en av sina \(k!\) ordningar. Så dividera med \(k!\) för att ta bort dubbelräkningen. (Att ordna alla \(n\) objekt i en rad är förresten bara \(n!\).)

Multinomialkoefficienter¶

När du ordnar en multimängd — en samling med upprepade, oskiljbara kopior — använder du multinomialkoefficienten. Med \(m\) sorters objekt, \(k_i\) kopior av sort \(i\), och \(k_1 + \cdots + k_m = n\) totalt:

\[ \frac{n!}{k_1!\,k_2!\cdots k_m!} \]

Samma logik som förut. Låtsas att alla \(n\) objekt är distinkta och ställ dem på rad: \(n!\) sätt. Men de \(k_1\) kopiorna av första sorten är egentligen identiska, så varje arrangemang räknades \(k_1!\) gånger för mycket (en gång per omkastning av de kopiorna) — dividera bort det. Upprepa för varje sort. Det klassiska fallet är att räkna de distinkta omkastningarna av ett ord som MISSISSIPPI.

Stjärnor och streck¶

Detta är modellen för att fördela identiska objekt i distinkta lådor — den man glömmer finns.

\[ \binom{n + k - 1}{k - 1} \qquad (n \text{ identiska objekt}, \; k \text{ distinkta mottagare}) \]

Bilden som gör det uppenbart. Rita de \(n\) objekten som stjärnor i en rad: \(\star\star\star\dots\) Släpp nu ner \(k - 1\) streck bland dem för att skiva raden i \(k\) segment; antalet stjärnor i segment \(i\) är hur många objekt mottagare \(i\) får (ett segment kan vara tomt). Varje fördelning motsvarar ett arrangemang av stjärnor och streck, och tvärtom. Du har \(n + k - 1\) symboler totalt och behöver bara välja vilka \(k - 1\) av positionerna som är streck — därav \(\binom{n+k-1}{k-1}\).

Frågan som väljer modellen: identiska eller distinkta?

Denna enda distinktion avgör allt, och det är det vanligaste stället att gå fel:

Identiska objekt → distinkta lådor: stjärnor och streck, \(\binom{n+k-1}{k-1}\).
Distinkta objekt → distinkta lådor: bara \(k^n\) — varje objekt väljer oberoende sin egen låda.
Distinkta objekt → omärkta grupper: Stirlingtal (nästa).

Fråga "om jag byter plats på två av objekten, får jag ett genuint annat utfall?" Om nej, är de identiska.

Stirlingtal¶

\(S(n, k)\) räknar sätten att dela \(n\) distinkta element i \(k\) icke-tomma omärkta grupper (grupperna har inga namn — bara vem som är med vem spelar roll).

\[ S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k) \]

Hur man läser rekursionen — tänk på vart det sista elementet, element \(n\), hamnar:

Antingen sitter det ensamt i sin egen grupp. Då måste de andra \(n-1\) elementen fylla de återstående \(k-1\) grupperna: \(S(n-1, k-1)\) sätt.
Eller så ansluter det till en befintlig grupp. Ordna först de andra \(n-1\) i \(k\) grupper (\(S(n-1, k)\) sätt), släpp sedan element \(n\) i vilken som helst av de \(k\) grupperna: \(k \cdot S(n-1, k)\).

Addera de två disjunkta fallen. Basfall: \(S(n, n) = 1\) (alla ensamma) och \(S(n, 1) = 1\) (alla tillsammans).

Varför "omärkta" spelar roll. Eftersom grupperna inte har namn är \(\{\{1,2\},\{3\}\}\) och \(\{\{3\},\{1,2\}\}\) samma partition — du räknar dem inte två gånger. Om grupperna vore märkta ("grupp A", "grupp B") skulle du multiplicera med \(k!\).

Att räkna med komplement¶

Här är det mest givande knepet på hela denna tentamen. När ett problem ber om "minst en…", innebär att räkna det rakt på oftast att traska genom överlappande fall. Räkna i stället motsatsen och subtrahera från totalen:

\[ (\text{det du vill ha}) = (\text{allt}) - (\text{motsatsen till det du vill ha}) \]

"Minst en" vänds till "ingen", vilket ofta är en enda ren produkt.

Tentamen (maj 2024, uppgift 4): telefonnummer

Uppställning: 5-siffriga telefonnummer, och första siffran får inte vara \(0\).

(a) Hur många har en siffra som förekommer mer än en gång?

Rakt på delas "en siffra upprepas" i många överlappande fall (ett par, två par, en trippel, …) — plågsamt. Motsatsen är ren: alla fem siffror distinkta. Räkna den och subtrahera.

Totalt antal nummer: första siffran \(9\) sätt (inte \(0\)), de andra fyra \(10\) sätt var: \(9 \cdot 10^4\).
Alldistinkta nummer: första siffran \(9\) sätt; andra siffran får vara \(0\) men inte lika med den första, alltså \(9\) sätt; sedan \(8\), sedan \(7\), sedan \(6\): \(9 \cdot 9 \cdot 8 \cdot 7 \cdot 6\).

\[ \underbrace{9 \cdot 10^4}_{\text{alla}} - \underbrace{9 \cdot 9 \cdot 8 \cdot 7 \cdot 6}_{\text{alla distinkta}} = 62784 \]

(b) Hur många har en siffra som förekommer mer än två gånger?

Nu är motsatsen "varje siffra förekommer högst två gånger" — vilket fortfarande kräver fall, så komplementknepet har slutat löna sig. Här är det renare att räkna direkt, efter hur många gånger den frekventa siffran förekommer (den kan förekomma \(5\), \(4\) eller exakt \(3\) gånger):

\[ \underbrace{9}_{\text{5 gånger}} + \underbrace{5 \cdot 9 \cdot 9}_{\text{4 gånger}} + \underbrace{10 \cdot 9^3}_{\text{3 gånger}} = 7704 \]

Den verkliga lärdomen är inte aritmetiken — det är omdömesbedömningen. Komplementräkning är ett verktyg, inte en reflex. I (a) var komplementet en prydlig produkt; i (b) var komplementet stökigare än att räkna direkt. Skissa båda innan du binder dig vid en.

Lådprincipen¶

Lådprincipen (Dirichlets lådprincip)

Om du placerar \(n\) objekt i \(m\) lådor och \(n > m\), så innehåller någon låda mer än ett objekt. (Mer allmänt innehåller någon låda minst \(\lceil n/m \rceil\).)

Principen i sig är uppenbar — det är inte där svårigheten bor. Färdigheten är att välja vad "duvorna" och "lådorna" är. Draget är nästan alltid: hitta någon storhet som bara kan anta ett fåtal värden (rester mod \(n\), möjliga summor, färger, …) och sprid många objekt över de få värdena. Två objekt måste då kollidera, och den kollisionen är det du ville ha.

Diskret sannolikhet¶

När du väl kan räkna är diskret sannolikhet mestadels räkning med en division på slutet.

Likformiga utfall¶

När varje utfall i utfallsrummet \(\Omega\) är lika sannolikt är sannolikheten för en händelse \(A\) bara dess andel av utfallen:

\[ P(A) = \frac{\lvert A \rvert}{\lvert \Omega \rvert} \]

Så en sannolikhetsfråga blir två räknefrågor: hur många utfall totalt, och hur många är i \(A\). Allt från räkneavsnittet gäller direkt.

Reglerna¶

Regel	När den gäller	Formel
Addition	\(A\), \(B\) disjunkta (kan inte båda inträffa)	\(P(A \cup B) = P(A) + P(B)\)
Addition (allmän)	alltid	\(P(A \cup B) = P(A) + P(B) - P(A \cap B)\)
Multiplikation	\(A\), \(B\) oberoende (ingen påverkar den andra)	\(P(A \cap B) = P(A)P(B)\)
Komplement	alltid	\(P(A^c) = 1 - P(A)\)

Den sista raden är sannolikhetsversionen av komplementknepet ovan: "minst en" är oftast lättast som \(1 - P(\text{ingen})\).

Betingad sannolikhet¶

\[ P(A \mid B) = \frac{P(A \cap B)}{P(B)}, \qquad P(B) > 0 \]

Vad det betyder: du har fått veta att \(B\) definitivt inträffade, så du kastar bort varje utfall utanför \(B\) och frågar vilken andel av det som är kvar som också är i \(A\). Att betinga krymper utfallsrummet till \(B\) och normerar om — det är precis vad divisionen med \(P(B)\) gör.

Disjunkt är INTE detsamma som oberoende — de är nästan motsatser

En fälla värd att internalisera. Om \(A\) och \(B\) är disjunkta och båda har positiv sannolikhet, så säger vetskapen om att \(A\) inträffade att \(B\) definitivt inte gjorde det — så de är starkt beroende, inte oberoende. "Disjunkt" är ett påstående om att utfall inte överlappar; "oberoende" är ett påstående om att det ena inte påverkar det andra. Kontrollera vilket antagande du faktiskt har innan du griper efter additions- eller multiplikationsregeln.