Kombinacje

🎯 Po co Ci to?

Lotto: skreślasz $6$ liczb z $49$. Czy kolejność skreślania ma znaczenie? Nie: kupon z liczbami ${3, 17, 25, 31, 40, 44}$ to ten sam kupon niezależnie od tego, co skreśliłeś najpierw. Wybór bez kolejności to kombinacja: ostatni i najczęściej potrzebny model. Jego symbol $\binom{n}{k}$ policzy też współczynniki $1, 3, 3, 1$ z §4.3: to wiersz trójkąta Pascala, który zobaczysz na końcu tej jednostki.

✅ Czego się nauczysz

  • liczyć kombinacje: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$;
  • rozumieć wzór jako „wariacje podzielone przez nadmiar kolejności";
  • używać symetrii $\binom{n}{k} = \binom{n}{n-k}$ i liczyć szanse Lotto;
  • budować trójkąt Pascala, dowodzić jego reguły i stosować wzór dwumianowy Newtona.

📘 Wyjaśnienie

📐 DEFINICJA (kombinacja $k$-elementowa zbioru $n$-elementowego): podzbiór $k$ elementów wybrany z $n$ (sam skład, bez kolejności). Ich liczba to symbol Newtona: $$\binom{n}{k} = \frac{n!}{k!,(n-k)!}.$$

Skąd ten wzór? Z korekty nadmiaru: obejrzyj to na trójce z dziesięciu. Wariacji (z kolejnością) jest $V_{10}^3 = 720$. Ale każdą trójkę-skład policzyliśmy wielokrotnie: jej elementy dają się ustawić na $3! = 6$ sposobów, a każde ustawienie to była osobna wariacja. Składów jest więc $\frac{720}{6} = 120$:

$$\binom{n}{k} = \frac{V_n^k}{k!} \qquad \text{(wybory z kolejnością... podzielone przez kolejność).}$$

To „podziel przez nadmiar" jest ważniejsze od samego wzoru: wróci w każdym zadaniu, gdzie coś liczysz wielokrotnie. Rachunkowo zaś działaj skrótem: $\binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{3!} = \frac{720}{6} = 120$ ($k$ czynników na górze, $k!$ na dole, bez pełnych silni).

Przydatne własności, obie „widać":

  • Symetria $\binom{n}{k} = \binom{n}{n-k}$: wybrać $47$ liczb z $49$ to to samo, co wskazać $2$ odrzucone, dlatego $\binom{49}{47} = \binom{49}{2} = 1176$ (licz zawsze mniejszą stronę!).
  • Brzegi: $\binom{n}{0} = \binom{n}{n} = 1$ (jeden pusty wybór, jeden pełny, tu pracuje $0! = 1$ z §17.2), a $\binom{n}{1} = \binom{n}{n-1} = n$ (jeden wybrany albo jeden odrzucony).

Trójkąt Pascala. Ustaw symbole Newtona w wiersze: w wierszu $n$ stoją $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$.

n = 0:            1
n = 1:          1   1
n = 2:        1   2   1
n = 3:      1   3   3   1
n = 4:    1   4   6   4   1
n = 5:  1   5  10  10   5   1

Każda liczba wewnątrz jest sumą dwóch stojących nad nią. To nie przypadek, tylko twierdzenie:

📐 TWIERDZENIE: dla $0 \le k < n$: $$\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}.$$

Dowód kombinatoryczny. Prawa strona liczy sposoby wybrania $k+1$ osób z grupy $n+1$ osób. Wyróżnij jedną osobę, np. Anię. Każdy wybór albo zawiera Anię, albo nie, i te przypadki są rozłączne (§17.1). Wybory z Anią: brakuje jeszcze $k$ osób spośród pozostałych $n$, czyli $\binom{n}{k}$ sposobów. Wybory bez Ani: wszystkie $k+1$ osób spośród $n$ pozostałych, czyli $\binom{n}{k+1}$ sposobów. Suma przypadków to wszystkie wybory. $\blacksquare$ Zamiast przekształcać silnie, policzyliśmy te same obiekty na dwa sposoby; to typowy chwyt kombinatoryki.

Wzór dwumianowy Newtona. Skąd współczynniki $1, 3, 3, 1$ w $(a+b)^3$ z §4.3? Wymnażając $(a+b)(a+b)(a+b)$, z każdego nawiasu bierzesz $a$ albo $b$. Wyraz $a^2b$ powstaje, gdy $b$ weźmiesz z dokładnie jednego nawiasu z trzech, a to da się zrobić na $\binom{3}{1} = 3$ sposoby. Ogólnie:

📐 WZÓR DWUMIANOWY NEWTONA: $$(a+b)^n = \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \binom{n}{2}a^{n-2}b^2 + \dots + \binom{n}{n}b^n.$$

Współczynnik przy $a^{n-k}b^k$ to liczba sposobów wyboru $k$ nawiasów (z $n$), z których bierzesz $b$, czyli $\binom{n}{k}$. Współczynniki to więc wiersz trójkąta Pascala: $(a+b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$. Na deser: dla $a = b = 1$ wzór mówi, że suma wiersza $n$ wynosi $2^n$, bo tyle jest wszystkich podzbiorów zbioru $n$-elementowego.

I obiecane Lotto: $\binom{49}{6} = \frac{49 \cdot 48 \cdot 47 \cdot 46 \cdot 45 \cdot 44}{6!} = 13,983,816$. Prawie $14$ milionów kuponów, jeden trafia. Dla skali: wypełniając jeden kupon na sekundę, spędziłbyś przy tym ponad pięć miesięcy bez snu. Wrócimy do tej liczby w §18.2, z pytaniem, co dokładnie oznacza „szansa $1$ do $14$ milionów".

💭 Pomyśl: Na ile sposobów można wybrać $2$ dyżurnych z klasy $30$-osobowej? I czemu wynik jest połową $30 \cdot 29$?

Sprawdź odpowiedź

$\binom{30}{2} = \frac{30 \cdot 29}{2} = 435$. Połowa, bo licząc „pierwszy dyżurny, drugi dyżurny" ($30 \cdot 29$ wariacji), każdą parę łapiesz dwa razy (Kasia-Tomek i Tomek-Kasia to ta sama para). Dzielenie przez $2!$ zdejmuje duplikaty.

⚠️ Uwaga, pułapka

Symbol $\binom{n}{k}$ to nie ułamek $\frac{n}{k}$, to liczba podzbiorów (zawsze całkowita!). Jeśli w rachunku kombinacji wychodzi Ci niecałkowity wynik: gdzieś umknął czynnik. Druga pułapka to mieszanie modeli w zadaniach dwuczęściowych: „wybierz $3$ osoby z $10$ i ustaw je w kolejce" to $\binom{10}{3} \cdot 3!$… czyli po prostu $V_{10}^3$, dwa spojrzenia na to samo. Spójność tych rachunków to dobry test zrozumienia.

📌 Najważniejsze w pigułce

  • Kombinacja = sam skład: $\binom{n}{k} = \frac{V_n^k}{k!} = \frac{n!}{k!(n-k)!}$; „podziel przez nadmiar kolejności".
  • Licz skrótem: $k$ czynników malejących przez $k!$.
  • Symetria $\binom{n}{k} = \binom{n}{n-k}$ (wskaż odrzuconych); $\binom{n}{0} = 1$, $\binom{n}{1} = n$.
  • Trójkąt Pascala: $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$ (dowód: z Anią albo bez niej).
  • Newton: $(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$; suma wiersza $= 2^n$.
  • Lotto: $\binom{49}{6} \approx 14$ mln; kombinatoryka skal codziennych decyzji.

🎒 Zadania

  1. Oblicz: $\binom{8}{3}$, $;\binom{12}{10}$, $;\binom{7}{7}$.
  2. W klasie jest $16$ dziewcząt i $14$ chłopców. Na ile sposobów można wybrać czteroosobową delegację złożoną z $2$ dziewcząt i $2$ chłopców?
  3. Ile przekątnych ma dwunastokąt wypukły? (Wskazówka: pary wierzchołków minus boki.)
  4. Na ile sposobów można rozdać $5$ identycznych czekolad pięciorgu z $8$ uczniów (po jednej, nikt nie dostaje dwóch)?
  5. Rozwiń $(x - 2)^5$ wzorem Newtona.
  6. Wyznacz współczynnik przy $x^3$ w rozwinięciu $(2x + 1)^6$.
Rozwiązanie krok po kroku

1. $\binom{8}{3} = \frac{8 \cdot 7 \cdot 6}{6} = 56$; $;\binom{12}{10} = \binom{12}{2} = 66$; $;\binom{7}{7} = 1$.

2. Reguła mnożenia na dwóch kombinacjach: $\binom{16}{2} \cdot \binom{14}{2} = 120 \cdot 91 = 10,920$.

3. Pary wierzchołków: $\binom{12}{2} = 66$; z tego $12$ to boki: $66 - 12 = 54$ przekątne.

4. Czekolady identyczne: liczy się tylko kto dostał: $\binom{8}{5} = \binom{8}{3} = 56$.

5. Wiersz $n = 5$: $1, 5, 10, 10, 5, 1$; $b = -2$, więc znaki na przemian: $(x-2)^5 = x^5 - 10x^4 + 40x^3 - 80x^2 + 80x - 32$.

6. Wyraz z $x^3$ to $\binom{6}{3}(2x)^3 \cdot 1^3 = 20 \cdot 8x^3 = 160x^3$. Współczynnik: $160$.

🔍 Sprawdź, czy umiesz

  • policzyć $\binom{n}{k}$ skrótem i użyć symetrii;
  • łączyć kombinacje z regułą mnożenia (wybory z dwóch pul);
  • udowodnić regułę trójkąta Pascala i rozwinąć $(a+b)^n$ wzorem Newtona.

Ucz się tej jednostki z asystentem