Binomialkoefficient

Kurs: S0008M Förkunskaper: Multiplikationsprincipen

Binomialkoefficienten $(k n)$ är antalet sätt att välja $k$ element bland $n$ utan återläggning och utan hänsyn till ordningen. Den följer ur multiplikationsprincipen genom att vi delar bort de inbördes ordningarna.

1. Sats 2.1

Antalet sätt att välja ut $k$ element bland $n$ utan återläggning och utan hänsyn till ordningen bland de utvalda är

(k n) = \frac{n !}{k ! ( n - k )!} = \frac{n ( n - 1 ) \dots ( n - k + 1 ) k faktorer}{k faktorer k ( k - 1 ) \dots 2 \cdot 1}

med $k! = k (k - 1) \dots 2 \cdot 1$ och konventionerna $0! = 1$ och $(0 n) = 1$ . Beteckningen $(k n)$ läses ” $n$ över $k$ ” och är bara ett kortare sätt att skriva bråket.

2. Varför

Anta att det går att välja $k$ element bland $n$ utan hänsyn till ordning på $x$ sätt. Vi räknar de ordnade valen på två olika sätt:

Direkt med multiplikationsprincipen: $n (n - 1) \dots (n - k + 1)$ sätt.
Först välja de $k$ elementen på $x$ sätt och sedan ordna dem inbördes på $k!$ sätt: $x \cdot k!$ .

Båda räknar samma sak, så

n (n - 1) \dots (n - k + 1) = x \cdot k! ⟹ x = \frac{n ( n - 1 ) \dots ( n - k + 1 )}{k !} = (k n)

3. Räkna för hand

Bråket i mitten är det som räknas för hand

$(5 20)$ blir $\frac{20 \cdot 19 \cdot 18 \cdot 17 \cdot 16}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}$ — fem faktorer uppe, fem nere, och det mesta förkortas bort innan vi multiplicerar. Fakultetsformen är bra för bevis, men ingen räknar ut $20!$ .

Två egenskaper sparar räknearbete:

(k n) = (n - k n), (k n) = (k - 1 n - 1) + (k n - 1)

Den första säger att välja ut $k$ är samma sak som att välja bort $n - k$ , så $(33 35) = (2 35) = 595$ . Den andra säger att ett visst element antingen är med (då ska $k - 1$ till väljas bland de andra $n - 1$ ) eller inte (då ska alla $k$ väljas bland de $n - 1$ ). Den bygger upp Pascals triangel, där varje tal är summan av de två ovanför:

Rad $n$ innehåller $(0 n), \dots, (n n)$ och summerar till $2^{n}$ , antalet delmängder av en mängd med $n$ element.

På räknaren heter funktionen nCr (menu → Probability → Combinations): nCr(20,5) ger $15504$ .

4. Lösta lektionsuppgifter

Lektion 1, övning 4 — Lottorader

På hur många sätt kan vi välja 7 nummer bland 35 utan återläggning och utan hänsyn till ordningen bland de utvalda? Resonera utifrån multiplikationsprincipen: hur blir det om vi tar hänsyn till ordningen?

Lösning

Med hänsyn till ordning. Första numret kan väljas på 35 sätt, andra på 34 och så vidare: $35 \cdot 34 \cdot 33 \cdot 32 \cdot 31 \cdot 30 \cdot 29$ ordnade rader.

Utan hänsyn till ordning. Varje uppsättning av 7 nummer har räknats $7!$ gånger ovan, en gång per inbördes ordning. Dela bort det:

$(7 35) = \frac{35 \cdot 34 \cdot 33 \cdot 32 \cdot 31 \cdot 30 \cdot 29}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 6724520$

Samma resonemang för $k$ nummer bland $n$ ger Sats 2.1, se avsnitt 1 och 2 ovan.

På räknaren. nCr(35,7).

Facit: 6 724 520.

Lektion 1, övning 5 — Från lottoraden till Sats 2.1

Generalisera resonemanget i övning 4 så att det gäller för urval av $k$ nummer bland $n$ . Vad är viktigt i Sats 2.1? Varför definierar vi $(0 n) = 1$ ?

Lösning

Generalisering. Med hänsyn till ordning kan $k$ nummer bland $n$ väljas på $n (n - 1) \dots (n - k + 1)$ sätt — $k$ faktorer, en per val, och varje val har ett alternativ färre än det förra eftersom vi inte lägger tillbaka. Varje oordnad uppsättning förekommer där $k!$ gånger, en gång per inbördes ordning. Alltså är antalet oordnade urval

$\frac{n ( n - 1 ) \dots ( n - k + 1 )}{k !} = (k n)$

vilket är Sats 2.1 (avsnitt 2 ovan).

Det viktiga i satsen är förutsättningarna: urvalet görs utan återläggning (annars blir det inte $n - 1$ alternativ i andra valet) och utan hänsyn till ordningen (annars ska vi inte dela med $k!$ ).

Varför $(0 n) = 1$ . Att välja noll element kan göras på precis ett sätt — att inte välja något. Definitionen gör också att fakultetsformen fungerar utan undantag: $\frac{n !}{0 ! n !} = 1$ med $0! = 1$ .

Resonemangsuppgift — det finns inget facit att jämföra med.

Se även

Resurser

← Multiplikationsprincipen · S0008M · Betingad sannolikhet →

Pelles Moln

Utforskare

1. Sats 2.1

2. Varför

3. Räkna för hand

4. Lösta lektionsuppgifter

Se även

Resurser

Innehåll

Grafvy

Bakåtlänkar