Hoppa till huvudinnehållet
Logga inSkapa konto
5. Kombinatorik och sannolikhet

Kombinatorik och sannolikhet

Välj en modell som skiljer på , repetition och likadana objekt.

Översikt

Identifiera vad som skiljer två utfall

Innan du räknar måste det vara tydligt när två utfall räknas som olika. Vid ett ordnat urval spelar placeringen roll; vid ett oordnat urval gör den inte det. Likadana objekt kan inte märkas och sedan räknas som olika utan kompensation. Multiplikationsprincipen används för följder av val; additionsprincipen används för disjunkta fall.

(nk)=n!k!(n−k)!\binom nk=\frac{n!}{k!(n-k)!}

Översikt

Olika objekt i omärkta respektive märkta grupper

Stirlingtalet S(n,k)S(n,k) räknar partitioner av nn olika objekt i kk icke-tomma, omärkta grupper. Om samma grupper ska ges till kk särskiljbara mottagare finns k!k! sätt att sätta etiketter på dem. Antalet surjektioner är därför k!S(n,k)k!S(n,k). Stjärnor och streck löser en annan modell: identiska objekt i märkta lådor. Kontrollera både objekten, gruppernas märkning och om tomma grupper tillåts innan du väljer formel.

Exempel

Exempel: identiska bollar i märkta lådor

Fördela sju identiska bollar i tre numrerade lådor. Skriv sju stjärnor och två streck; antalet stjärnor före, mellan och efter strecken ger lådornas innehåll. Därför väljer vi streckens två positioner bland nio. Om alla lådor måste få minst en boll lägger vi först en boll i varje låda och fördelar de fyra återstående på samma sätt.

#alla fo¨rdelningar=(92)=36,#utan tom la˚da=(62)=15\#\text{alla fördelningar}=\binom92=36,\qquad\#\text{utan tom låda}=\binom62=15

Exempel

Exempel: fyra olika uppgifter till två studenter

Utan krav finns 24=162^4=16 tilldelningar. Två tilldelningar ger allt till samma student, så när båda ska få något återstår 16−2=1416-2=14. Om mottagarna i stället tas bort återstår bara två omärkta högar; då räknas varje uppdelning två gånger av de märkta tilldelningarna. Därför är S(4,2)=14/2!=7S(4,2)=14/2!=7. Detta visar varför faktorn för mottagarnas märkning behövs.

Fördjupning

Komplementet kan vara lättare att räkna

Sannolikheten är gynnsamma utfall delat med möjliga utfall bara när de räknade utfallen är lika sannolika. Oordnade utfall vid tärningskast är i allmänhet inte lika sannolika. Vid krav av typen minst ett är komplementet ofta enklare. För överlappande förbjudna händelser måste överlapp räknas tillbaka med inklusion–exklusion; enbart subtraktion räknar bort dem flera gånger.

P(A∪B)=P(A)+P(B)−P(A∩B)P(A\cup B)=P(A)+P(B)-P(A\cap B)

Fördjupning

Härled Stirlingrekursionen med det sista objektet

I en av nn objekt i kk grupper kan det sista objektet bilda en egen grupp. Då partitioneras de andra på S(n−1,k−1)S(n-1,k-1) sätt. Annars går det in i en av kk redan befintliga grupper, vilket ger kS(n−1,k)kS(n-1,k) sätt. Fallen är disjunkta och uttömmande, så S(n,k)=S(n−1,k−1)+kS(n−1,k)S(n,k)=S(n-1,k-1)+kS(n-1,k). För märkta mottagare kan samma antal räknas genom att utesluta tomma mottagare: k!S(n,k)=∑j=0k(−1)j(kj)(k−j)nk!S(n,k)=\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n för positiva n,kn,k. Antalet uteslutna mottagare avgör både binomialkoefficienten och hur många val varje objekt har kvar.

Formler i området

Oordnat urval

(nk)=n!k!(n−k)!\binom nk=\frac{n!}{k!(n-k)!}
Vad gör formeln?
Räknar delmängder med en bestämd storlek.
När får den användas?
Välj ett helt antal objekt mellan noll och antalet tillgängliga olika objekt, utan repetition.

Permutationer med upprepade objekt

n!n1!⋯nr!,n1+⋯+nr=n\frac{n!}{n_1!\cdots n_r!},\qquad n_1+\cdots+n_r=n
Vad gör formeln?
Kompenserar för omordningar som ger samma resultat.
När får den användas?
Objekt inom samma typ är identiska; alla positioner är ordnade.

Stjärnor och streck

x1+⋯+xk=n, xi≥0⇒(n+k−1k−1) lo¨sningarx_1+\cdots+x_k=n,\ x_i\ge0\quad\Rightarrow\quad\binom{n+k-1}{k-1}\text{ lösningar}
Vad gör formeln?
Räknar fördelningar med tillåtna tomma lådor.
När får den användas?
Icke-negativa heltalsvariabler och minst en märkt låda; objekten är identiska.

Binomialsatsen

(a+b)n=∑k=0n(nk)an−kbk(a+b)^n=\sum_{k=0}^n\binom nk a^{n-k}b^k
Vad gör formeln?
Ger koefficienterna i en potensutveckling.
När får den användas?
Exponentens värde är ett icke-negativt heltal; faktorerna kommuterar.

Inklusion–exklusion för tre mängder

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|
Vad gör formeln?
Räknar unionen utan över- eller underräkning.
När får den användas?
Mängderna är ändliga och kan överlappa.

Komplementregeln

P(A)=1−P(Ac)P(A)=1-P(A^c)
Vad gör formeln?
Ersätter ett svårt fall med alla utfall där det inte inträffar.
När får den användas?
Händelsen och dess avser samma sannolikhetsrum.

S(n,k)=S(n−1,k−1)+kS(n−1,k)S(0,0)=1,S(n,0)=0 (n>0),S(n,k)=0 (k>n)\begin{gathered}S(n,k)=S(n-1,k-1)+kS(n-1,k)\\ S(0,0)=1,\quad S(n,0)=0\ (n>0),\quad S(n,k)=0\ (k>n)\end{gathered}
Vad gör formeln?
Räknar partitioner av olika objekt i ett bestämt antal icke-tomma, omärkta grupper.
När får den användas?
Rekursionssteget gäller positiva heltal för antalet objekt och antalet grupper. Tomma gränsfall hanteras med de angivna startvärdena.

Antalet surjektioner

k!S(n,k)=∑j=0k(−1)j(kj)(k−j)nk!S(n,k)=\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n
Vad gör formeln?
Räknar fördelningar där varje särskiljbar mottagare får minst ett objekt.
När får den användas?
Definitionsmängden har n olika element och målmängden k olika element, där n och k är positiva heltal. Varje målelement ska träffas.

Hänger ihop med

Kan du använda kombinatorik och sannolikhet?

Lös en riktig tentauppgift från SF1662 med ledtrådar och lösningsförslag. Inget konto behövs.

Prova en uppgift