---
kurs:
  - S0008M
tags:
  - matematik
  - kombinatorik
  - formel
förkunskaper:
  - "[[Multiplikationsprincipen]]"
status: utkast
aliases:
  - Binomialkoefficienten
  - n över k
  - Kombinationer
  - Val utan ordning
---

> **Kurs:** S0008M
> **Förkunskaper:** [[Multiplikationsprincipen]]

---

Binomialkoefficienten $\binom{n}{k}$ ä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|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

$$
\boxed{\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!} = \dfrac{\overbrace{n(n-1)\cdots(n-k+1)}^{k \text{ faktorer}}}{\underbrace{k(k-1)\cdots 2\cdot 1}_{k \text{ faktorer}}}}
$$

med $k! = k(k-1)\cdots 2\cdot 1$ och konventionerna $0! = 1$ och $\binom{n}{0} = 1$. Beteckningen $\binom{n}{k}$ 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)\cdots(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)\cdots(n-k+1) = x\cdot k! \quad\Longrightarrow\quad x = \dfrac{n(n-1)\cdots(n-k+1)}{k!} = \binom{n}{k}
$$

---

## 3. Räkna för hand

> [!tip] Bråket i mitten är det som räknas för hand
> $\binom{20}{5}$ blir $\dfrac{20\cdot19\cdot18\cdot17\cdot16}{5\cdot4\cdot3\cdot2\cdot1}$ — 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:

$$
\binom{n}{k} = \binom{n}{n-k}, \qquad \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}
$$

Den första säger att välja ut $k$ är samma sak som att välja bort $n - k$, så $\binom{35}{33} = \binom{35}{2} = 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:

![[pascals-triangel.png|420]]

Rad $n$ innehåller $\binom{n}{0}, \dots, \binom{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 $15\,504$.

---

## 4. Lösta lektionsuppgifter

> [!example]- 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?
>
> > [!note]- Lösning
> > **Med hänsyn till ordning.** Första numret kan väljas på 35 sätt, andra på 34 och så vidare: $35\cdot34\cdot33\cdot32\cdot31\cdot30\cdot29$ 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:
> > $$
> > \binom{35}{7} = \dfrac{35\cdot34\cdot33\cdot32\cdot31\cdot30\cdot29}{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1} = \boxed{6\,724\,520}
> > $$
> >
> > 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.*

> [!example]- 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 $\binom{n}{0} = 1$?
>
> > [!note]- Lösning
> > **Generalisering.** Med hänsyn till ordning kan $k$ nummer bland $n$ väljas på $n(n-1)\cdots(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
> > $$
> > \dfrac{n(n-1)\cdots(n-k+1)}{k!} = \binom{n}{k}
> > $$
> > 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 $\binom{n}{0} = 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: $\dfrac{n!}{0!\,n!} = 1$ med $0! = 1$.
> >
> > *Resonemangsuppgift — det finns inget facit att jämföra med.*

---

## Se även

- [[Multiplikationsprincipen]]
- [[Klassiska sannolikhetsdefinitionen]]
- [[Hypergeometrisk fördelning]]
- [[Binomialfördelning]]

## Resurser

- [Khan Academy: Counting, permutations, and combinations](https://www.khanacademy.org/math/statistics-probability/counting-permutations-and-combinations)
- [Wikipedia: Binomialkoefficient](https://sv.wikipedia.org/wiki/Binomialkoefficient)

---

← [[Multiplikationsprincipen]] · [[S0008M]] · [[Betingad sannolikhet]] →