Poziom zaawansowany

Kombinatoryka

Sztuka liczenia bez wypisywania. Reguła mnożenia, silnia, permutacje, wariacje i kombinacje odpowiadają na jedno pytanie — na ile sposobów da się to zrobić — a cała trudność sprowadza się do dwóch decyzji: czy kolejność ma znaczenie i czy elementy mogą się powtarzać.

Zanim zaczniesz

Ten temat opiera się na wcześniejszych zagadnieniach. Zanim zaczniesz, warto przerobić poniższe lekcje — dzięki nim wszystko pójdzie gładko:

Wszystkie wzory

  • Reguła mnożenia

    N=k1⋅k2⋅…⋅kmN = k_1 \cdot k_2 \cdot \ldots \cdot k_m

    wybór w kilku niezależnych krokach — liczby możliwości mnożymy

  • Silnia

    n!=1⋅2⋅3⋅…⋅n,0!=1n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n, \qquad 0! = 1

    iloczyn kolejnych liczb naturalnych; 0! z definicji równa się 1

  • Permutacje

    Pn=n!P_n = n!

    liczba ustawień wszystkich n elementów w kolejności

  • Wariacje bez powtórzeń

    Vnk=n!(n−k)!=n(n−1)…(n−k+1)V_n^k = \frac{n!}{(n-k)!} = n(n-1)\ldots(n-k+1)

    wybór k z n, kolejność ma znaczenie, bez powtórzeń

  • Wariacje z powtórzeniami

    V‾nk=nk\overline{V}_n^k = n^k

    k razy wybieramy spośród tych samych n możliwości

  • Kombinacje

    Cnk=(nk)=n!k! (n−k)!C_n^k = \binom{n}{k} = \frac{n!}{k! \, (n-k)!}

    wybór k z n, kolejność NIE ma znaczenia

  • Symetria kombinacji

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

    wybranie k elementów to to samo, co odrzucenie pozostałych n − k

Kombinatoryka odpowiada na pytanie „na ile sposobów?", zanim ktokolwiek zdąży zacząć wypisywać przypadki. Jest też warunkiem wstępnym prawdopodobieństwa klasycznego: żeby podzielić liczbę zdarzeń sprzyjających przez liczbę wszystkich, trzeba najpierw umieć obie policzyć.

Reguła mnożenia

Cała kombinatoryka wyrasta z jednej obserwacji. Jeśli wybór składa się z kilku niezależnych kroków, a kolejne kroki dają k1,k2,…,kmk_1, k_2, \ldots, k_m możliwości, to wszystkich wyników jest:

N=k1⋅k2⋅…⋅kmN = k_1 \cdot k_2 \cdot \ldots \cdot k_m

Możliwości mnożymy, a nie dodajemy — bo każdą decyzję z pierwszego kroku da się połączyć z każdą decyzją z drugiego.

W restauracji są 4 zupy, 6 dań głównych i 3 desery. Ile jest różnych trzydaniowych obiadów?

Silnia

Iloczyn kolejnych liczb naturalnych pojawia się w kombinatoryce tak często, że dostał własny symbol:

n!=1⋅2⋅3⋅…⋅nn! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n

Czyta się to „n silnia". Kilka pierwszych wartości warto znać na pamięć:

nn01234567
n!n!1126241207205040

Uwaga na pierwszą kolumnę: 0!=10! = 1, z definicji. Pusty ciąg można ustawić dokładnie na jeden sposób — nie robiąc nic — a poza tym bez tej umowy wzory na kombinacje dzieliłyby przez zero.

012345670200400600800nn!12624120720n!
Trzy pierwsze słupki są w tej skali prawie niewidoczne. Silnia rośnie szybciej niż jakakolwiek potęga — 10! to już ponad trzy i pół miliona.

Ten wzrost jest praktyczną wskazówką: skoro dziesięć osób da się ustawić na 3 628 8003\,628\,800 sposobów, nie ma mowy o rozwiązywaniu zadań przez wypisywanie przypadków.

Permutacje

Permutacja to ustawienie wszystkich nn elementów w kolejności. Pierwsze miejsce można obsadzić na nn sposobów, drugie na n−1n-1 (jeden element już zużyty), i tak dalej:

Pn=n⋅(n−1)⋅…⋅2⋅1=n!P_n = n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1 = n!
Na ile sposobów pięć osób może ustawić się w kolejce?

Wariacje bez powtórzeń

Gdy z nn elementów wybieramy tylko kk, ale kolejność ma znaczenie, mówimy o wariacjach bez powtórzeń:

Vnk=n!(n−k)!=n(n−1)…(n−k+1)V_n^k = \frac{n!}{(n-k)!} = n(n-1)\ldots(n-k+1)

Druga postać jest wygodniejsza w rachunku: to po prostu kk malejących czynników, zaczynając od nn.

W klubie jest 8 osób. Na ile sposobów można wybrać przewodniczącego, sekretarza i skarbnika?

Wariacje z powtórzeniami

Jeśli elementy wolno powtarzać, każdy z kk kroków ma pełne nn możliwości, więc reguła mnożenia daje wprost:

V‾nk=nk\overline{V}_n^k = n^k
Ile jest czterocyfrowych kodów PIN?

Kombinacje

Gdy wybieramy kk elementów z nn, a kolejność nie ma znaczenia, mamy kombinacje:

Cnk=(nk)=n!k! (n−k)!C_n^k = \binom{n}{k} = \frac{n!}{k! \, (n-k)!}

Skąd bierze się k!k! w mianowniku? Stąd, że każdy kk-elementowy zbiór został policzony we wariacjach k!k! razy — raz dla każdego ustawienia tych samych elementów. Dzielimy więc przez liczbę tych ustawień:

Cnk=Vnkk!C_n^k = \frac{V_n^k}{k!}
Na ile sposobów można wybrać trzyosobową delegację spośród 8 osób?

Symetria

Kombinacje mają własność, która oszczędza mnóstwo rachunku:

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

Wybranie kk elementów to przecież to samo, co wskazanie n−kn-k elementów, które zostawiamy. Dlatego (2018)\binom{20}{18} liczy się jak (202)=190\binom{20}{2} = 190, a nie przez rozpisywanie osiemnastu czynników.

−10123456704812162024kC(6, k)1615201561C(6, k)
Liczby wyborów z sześcioelementowego zbioru układają się symetrycznie: skrajne słupki to wybór niczego i wybór wszystkiego, a najwyższy stoi dokładnie w połowie.

Suma wszystkich słupków wynosi 64=2664 = 2^6 — tyle jest podzbiorów zbioru sześcioelementowego, bo o każdym elemencie decydujemy niezależnie: brać czy nie brać.

Który wzór wybrać

Cała trudność sprowadza się do dwóch pytań o treść zadania:

kolejność ma znaczenie?powtórzenia dozwolone?wzór
tak, bierzemy wszystkie—n!n!
tak, bierzemy kk z nnnien!(n−k)!\dfrac{n!}{(n-k)!}
tak, bierzemy kk z nntaknkn^k
nie, bierzemy kk z nnnie(nk)\dbinom{n}{k}

Praktyczny test na pierwsze pytanie: zamień miejscami dwa wybrane elementy. Jeśli powstała inna sytuacja — kolejność ma znaczenie.

Ćwiczenia

Pięć typów pytań odpowiada pięciu wzorom z tej lekcji. Prompt z wykrzyknikiem prosi wprost o silnię — pamiętaj o 0!=10! = 1. Permutacje dla danego nn to również n!n!, tylko zadane słowem. Wariacje bez powtórzeń i wariacje z powtórzeniami dostają oba parametry, nn i kk; różnią się tylko tym, czy elementy wolno brać wielokrotnie. Kombinacje pytają o wybór kk z nn bez znaczenia kolejności — i tu warto pamiętać o symetrii. Każda odpowiedź jest liczbą całkowitą.

Ćwiczenia

Rozwiąż zestaw zadań — trudność rośnie z każdym kolejnym. Na końcu zobaczysz wynik i listę pomyłek do powtórki.

Zadanie 1 z 8Punkty: 0
3! =

Częste błędy

  • Dodawanie zamiast mnożenia — kolejne kroki wyboru mnożą liczby możliwości.
  • Mylenie wariacji z kombinacjami — jeśli kolejność nie ma znaczenia, wynik trzeba jeszcze podzielić przez k!k!.
  • Zapomniane 0!=10! = 1 — zwłaszcza w skrajnych przypadkach wzoru na kombinacje.
  • Skracanie silni „na oko" — 8!5!\tfrac{8!}{5!} to 8⋅7⋅68 \cdot 7 \cdot 6, a nie 85\tfrac{8}{5} ani 3!3!.
  • Powtórzenia wzięte z sufitu — o tym, czy elementy mogą się powtarzać, rozstrzyga treść zadania, a nie wygoda wzoru.
  • Wypisywanie przypadków — przy nn większym od pięciu jest ich zwykle za dużo, żeby zdążyć się nie pomylić.

Karta wzorów

Temat: Kombinatoryka

  • Reguła mnożenia

    N=k1⋅k2⋅…⋅kmN = k_1 \cdot k_2 \cdot \ldots \cdot k_m

    wybór w kilku niezależnych krokach — liczby możliwości mnożymy

  • Silnia

    n!=1⋅2⋅3⋅…⋅n,0!=1n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n, \qquad 0! = 1

    iloczyn kolejnych liczb naturalnych; 0! z definicji równa się 1

  • Permutacje

    Pn=n!P_n = n!

    liczba ustawień wszystkich n elementów w kolejności

  • Wariacje bez powtórzeń

    Vnk=n!(n−k)!=n(n−1)…(n−k+1)V_n^k = \frac{n!}{(n-k)!} = n(n-1)\ldots(n-k+1)

    wybór k z n, kolejność ma znaczenie, bez powtórzeń

  • Wariacje z powtórzeniami

    V‾nk=nk\overline{V}_n^k = n^k

    k razy wybieramy spośród tych samych n możliwości

  • Kombinacje

    Cnk=(nk)=n!k! (n−k)!C_n^k = \binom{n}{k} = \frac{n!}{k! \, (n-k)!}

    wybór k z n, kolejność NIE ma znaczenia

  • Symetria kombinacji

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

    wybranie k elementów to to samo, co odrzucenie pozostałych n − k

012345670200400600800nn!12624120720n!
Wartości silni dla n od 1 do 6. Pierwsze trzy słupki są przy tej skali praktycznie niewidoczne — 6! jest już sto dwadzieścia razy większe od 3!. Tak wygląda wzrost kombinatoryczny.
−10123456704812162024kC(6, k)1615201561C(6, k)
Liczba sposobów wyboru k elementów z sześciu. Rysunek jest symetryczny, bo wybranie k elementów to to samo, co odrzucenie pozostałych 6 − k; najwięcej możliwości daje wybór połowy zbioru.

Najczęstsze pytania

Powiązane artykuły

Świetliste słupki histogramu układające się w miękki dzwon rozkładu, jeden punkt odstający jaśniejszy od pozostałych, na tle kosmicznej mgławicy w fiolecie i magencie
Statystyka i prawdopodobieństwo

Człowiek średni nie istnieje

Cała statystyka opisowa opiera się na jednej transakcji: oddajesz informację o tłumie, dostajesz jedną liczbę. Transakcja bywa opłacalna, ale nigdy nie jest darmowa — i warto wiedzieć, co dokładnie w niej ginie. Od tablic śmiertelności z 1662 roku, przez „człowieka średniego" Queteleta, po samoloty, których nikt nie zobaczył.

15 min