Kombinacje bez powtórzeń - wzór n po k, przykłady i różnica z wariacją

Q: Co to jest kombinacja w matematyce?

Kombinacja k-elementowa zbioru n-elementowego to dowolny k-elementowy podzbiór tego zbioru wybór k elementów, w którym kolejność nie ma znaczenia. Liczba kombinacji to binomnk.

Q: Jaki jest wzór na kombinacje?

C_n^k = binomnk = n!/k! (n-k)!. W praktyce liczymy go jako iloraz k czynników malejących od n przez k!, np. binom93 = 9 · 8 · 7/3 · 2 · 1 = 84.

Q: Jak obliczyć n po k?

Zapisz w liczniku k kolejnych liczb od n w dół, w mianowniku k!, i skróć. Dla dużego k skorzystaj z symetrii binomnk = binomnn-k, np. binom2018 = binom202 = 190.

Q: Ile wynosi n po 2?

binomn2 = n(n-1)/2 - tyle jest par w zbiorze n-elementowym. To liczba uścisków dłoni wśród n osób albo liczba odcinków o końcach w n punktach.

Q: Na ile sposobów można wybrać 2 osoby z 10?

binom102 = 10 · 9/2 = 45, jeśli osoby nie pełnią różnych funkcji. Jeśli pełnią (np. kapitan i zastępca), to 10 · 9 = 90.

Klasa 3 liceum i technikum

Kombinacje - wzory

Kombinacje ( $k$ -elementowe podzbiory zbioru $n$ -elementowego, $0 \le k \le n$ ):

$C_n^k = \binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}$

Związek z wariacjami (każdy podzbiór można uporządkować na $k!$ sposobów):

$C_n^k = \frac{V_n^k}{k!} = \frac{n \cdot (n-1) \cdot \ldots \cdot (n-k+1)}{k!}$

Symetria: $\binom{n}{k} = \binom{n}{n-k}$ - wybrać $k$ elementów to to samo co wybrać $n - k$ odrzuconych.

Kombinacja $k$ -elementowa zbioru $n$ -elementowego to każdy $k$ -elementowy podzbiór tego zbioru. Kolejność elementów nie ma znaczenia: $\{A, B, C\}$ i $\{C, A, B\}$ to ta sama kombinacja. Liczba kombinacji wynosi $\binom{n}{k} = \tfrac{n!}{k!\,(n-k)!}$ - to tak zwany symbol Newtona, czytany „en po ka”. Na przykład z $5$ osób trzyosobową grupę można wybrać na $\binom{5}{3} = 10$ sposobów.

Kombinacji używamy wszędzie tam, gdzie wybieramy grupę: delegację, drużynę bez funkcji, zestaw kart, liczby w losowaniu, punkty na wierzchołki trójkąta.

Od wariacji do kombinacji

Przykład 1. Z czterech osób $A, B, C, D$ wybieramy dwie na wycieczkę. Ile jest możliwości?

Gdyby wybór był z kolejnością (np. kierowca i pilot), mielibyśmy wariacje: $V_4^2 = 4 \cdot 3 = 12$ par uporządkowanych. Na wycieczce kolejność nie gra roli, a każda para osób pojawia się wśród tych $12$ dwa razy:

Wybrana para (kombinacja)	Odpowiadające jej pary uporządkowane (wariacje)
{A, B}	AB, BA
{A, C}	AC, CA
{A, D}	AD, DA
{B, C}	BC, CB
{B, D}	BD, DB
{C, D}	CD, DC

Par bez kolejności jest więc $\tfrac{12}{2} = 6$ .

Ogólnie: każdy $k$ -elementowy podzbiór da się ustawić w kolejności na $k!$ sposobów (permutacje). Wariacje liczą każdy podzbiór $k!$ razy, więc

$V_n^k = C_n^k \cdot k! \qquad \Longrightarrow \qquad C_n^k = \frac{V_n^k}{k!} = \frac{n!}{(n-k)! \cdot k!}.$

To jest całe wyprowadzenie wzoru: kombinacja = wariacja podzielona przez liczbę ustawień wybranych elementów.

Jak liczyć n po k bez kalkulatora

Nie liczymy silni w całości - w liczniku zostawiamy $k$ czynników malejących od $n$ , w mianowniku $k!$ , i skracamy przed mnożeniem.

Przykład 2. Oblicz $\binom{30}{3}$ .

$\binom{30}{3} = \frac{30 \cdot 29 \cdot 28}{3 \cdot 2 \cdot 1} = \frac{30}{3 \cdot 2} \cdot 29 \cdot 28 = 5 \cdot 29 \cdot 28 = 4060.$

Przykład 3. Oblicz $\binom{12}{10}$ .

Z symetrii $\binom{12}{10} = \binom{12}{2}$ - zamiast dziesięciu czynników liczymy dwa:

$\binom{12}{2} = \frac{12 \cdot 11}{2} = 66.$

Zasada: zawsze licz „krótszą stronę”, czyli $\binom{n}{k}$ dla mniejszej z liczb $k$ i $n - k$ . Warto pamiętać $\binom{n}{0} = 1$ , $\binom{n}{1} = n$ oraz $\binom{n}{2} = \tfrac{n(n-1)}{2}$ .

Kombinacje w zadaniach

Przykład 4 (losowanie). W grze Mini Lotto losuje się $5$ liczb spośród $42$ . Ile jest możliwych wyników losowania?

Liczy się tylko to, które liczby wypadły, a nie kolejność ich wylosowania - to kombinacja:

$\binom{42}{5} = \frac{42 \cdot 41 \cdot 40 \cdot 39 \cdot 38}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 850\,668.$

Szansa na trafienie „piątki” jednym zakładem to więc $\tfrac{1}{850\,668}$ .

Przykład 5 (wybór dwuetapowy). W kole naukowym jest $7$ matematyków i $5$ fizyków. Na ile sposobów można wybrać komisję złożoną z $3$ matematyków i $2$ fizyków?

Krok 1. Matematyków wybieramy na $\binom{7}{3} = \tfrac{7 \cdot 6 \cdot 5}{6} = 35$ sposobów.

Krok 2. Fizyków wybieramy na $\binom{5}{2} = \tfrac{5 \cdot 4}{2} = 10$ sposobów.

Krok 3. Wybory są niezależne, więc z reguły mnożenia: $35 \cdot 10 = 350$ .

Odpowiedź: $350$ sposobów. Uwaga: nie liczymy $\binom{12}{5}$ , bo to dopuszczałoby dowolny skład komisji, np. samych matematyków.

Przykład 6 (ciągi zero-jedynkowe). Ile jest ciągów długości $8$ złożonych z zer i jedynek, w których jest dokładnie $3$ jedynki?

Ciąg jest wyznaczony przez to, na których miejscach stoją jedynki. Wybieramy $3$ miejsca z $8$ (kolejność wyboru miejsc nie ma znaczenia), na pozostałych stawiamy zera:

$\binom{8}{3} = \frac{8 \cdot 7 \cdot 6}{6} = 56.$

Ten sam pomysł - kombinacja wybiera miejsca - pozwala liczyć słowa z dwóch liter, drogi w kratce (wybór, które kroki idą w prawo) i serie rzutów monetą z daną liczbą orłów.

Kombinacja czy wariacja?

Ten sam zbiór, różne pytania. W klasie jest $10$ osób.

Pytanie	Kolejność ma znaczenie?	Model	Wynik
Wybierz 3 osoby do sprzątania sali	nie	kombinacja C(10, 3)	120
Wybierz przewodniczącego, zastępcę i skarbnika	tak	wariacja bez powtórzeń V(10, 3)	720
Przydziel 3 różne nagrody, jedna osoba może dostać kilka	tak	wariacja z powtórzeniami 10³	1000

Test: zamień miejscami dwie wybrane osoby. Jeśli wynik się nie zmienia (ta sama grupa), to kombinacja. Jeśli się zmienia (inne funkcje, inna nagroda dla kogo innego), to wariacja. Wynik wariacji jest zawsze $k!$ razy większy: $720 = 120 \cdot 3!$ .

Typowe błędy

Wariacja tam, gdzie wybieramy grupę. „Wybierz $4$ osoby do delegacji” - funkcji brak, więc $\binom{n}{4}$ , a nie $n(n-1)(n-2)(n-3)$ .
Dodawanie zamiast mnożenia w wyborze dwuetapowym. $3$ matematyków i $2$ fizyków to $\binom{7}{3} \cdot \binom{5}{2}$ , a nie $\binom{7}{3} + \binom{5}{2}$ .
Liczenie pełnych silni. $\binom{30}{3}$ to trzy czynniki w liczniku, a nie $30!$ - im wcześniej skrócisz, tym mniejsze liczby.
Mylenie $\binom{n}{k}$ z ułamkiem $\tfrac{n}{k}$ . Symbol Newtona zapisujemy bez kreski ułamkowej i liczymy ze wzoru z silniami: $\binom{6}{2} = 15$ , a nie $3$ .

Najczęstsze pytania

Co to jest kombinacja w matematyce? Kombinacja $k$ -elementowa zbioru $n$ -elementowego to dowolny $k$ -elementowy podzbiór tego zbioru

wybór $k$ elementów, w którym kolejność nie ma znaczenia. Liczba kombinacji to $\binom{n}{k}$ .

Jaki jest wzór na kombinacje? $C_n^k = \binom{n}{k} = \tfrac{n!}{k!\,(n-k)!}$ . W praktyce liczymy go jako iloraz $k$ czynników malejących od $n$ przez $k!$ , np. $\binom{9}{3} = \tfrac{9 \cdot 8 \cdot 7}{3 \cdot 2 \cdot 1} = 84$ .

Czym różni się kombinacja od wariacji? W wariacji kolejność wybranych elementów ma znaczenie (ciąg), w kombinacji - nie ma (zbiór). Dlatego kombinacji jest $k!$ razy mniej: $C_n^k = \tfrac{V_n^k}{k!}$ .

Jak obliczyć n po k? Zapisz w liczniku $k$ kolejnych liczb od $n$ w dół, w mianowniku $k!$ , i skróć. Dla dużego $k$ skorzystaj z symetrii $\binom{n}{k} = \binom{n}{n-k}$ , np. $\binom{20}{18} = \binom{20}{2} = 190$ .

Ile wynosi n po 2? $\binom{n}{2} = \tfrac{n(n-1)}{2}$ - tyle jest par w zbiorze $n$ -elementowym. To liczba uścisków dłoni wśród $n$ osób albo liczba odcinków o końcach w $n$ punktach.

Na ile sposobów można wybrać 2 osoby z 10? $\binom{10}{2} = \tfrac{10 \cdot 9}{2} = 45$ , jeśli osoby nie pełnią różnych funkcji. Jeśli pełnią (np. kapitan i zastępca), to $10 \cdot 9 = 90$ .

Przećwicz

Kombinacje - zadania → - delegacje z warunkiem, uściski dłoni, przekątne, trójkąty z punktów na prostych, karty, drużyna z kapitanem, drogi w kratce (zadania z pełnym rozwiązaniem krok po kroku).
Cały zestaw: kombinatoryka - zadania z rozwiązaniami →

Podsumowanie

Kombinacja to podzbiór - kolejność nie ma znaczenia.
$C_n^k = \binom{n}{k} = \tfrac{n!}{k!\,(n-k)!} = \tfrac{V_n^k}{k!}$ .
Liczymy skracając: $k$ czynników od $n$ w dół przez $k!$ ; przy dużym $k$ używamy symetrii.
Wybór kilku grup naraz (np. $3$ matematyków i $2$ fizyków) to iloczyn kombinacji.
Kombinacja może wybierać miejsca: ciągi zero-jedynkowe, drogi w kratce, liczba orłów.

Zobacz też

Kombinatoryka - zadania różne - następna lekcja: jak rozpoznać model i łączyć metody.
Symbol Newtona i trójkąt Pascala - własności liczb $\binom{n}{k}$ .
Kombinatoryka - permutacje, wariacje, kombinacje - zestawienie wzorów, także kombinacje z powtórzeniami.