1. Kombinatoryka – powtórzenie wiadomości - M_R_W22_M2 Rachunek prawdopodobieństwa, cz. 1

RXPyZhdPHiYvg

1. Kombinatoryka – powtórzenie wiadomości

Początków kombinatoryki można doszukać się już za czasów starożytnych, bowiem sam Arystoteles zajmował się problemem ustawień liter alfabetu. Jednak uzyskanie wzorów, którymi się dziś posługujemy zajęło kilkanaście wieków! Wzory na liczbę permutacji i wariacji podano w XIII wieku, a na liczbę kombinacji dopiero w XVI wieku. Termin $k o m b i n a t o r y k a$ po raz pierwszy został użyty w 1666 roku w pracy wielkiego filozofa i naukowca Leibniza pt. „Rozprawa o sztuce kombinacji”.

W tym materiale powtórzymy i utrwalimy wiadomości dotyczące schematów kombinatorycznych takich jak permutacja, kombinacja, wariacja bez powtórzeń i z powtórzeniami. Będziemy rozwiązywać ćwiczenia interaktywne, bazując na części teoretycznej materiału i podanych przykładach.

Twoje cele

Zastosujesz silnię do obliczenia liczby permutacji podanego zbioru.
Obliczysz liczbę wariacji bez powtórzeń w sytuacjach problemowych.
Wykorzystasz definicję symbolu Newtona do znalezienia liczby kombinacji w zadanym zbiorze.
Nauczysz się rozróżniać sytuacje problemowe i korzysta z odpowiednich schematów: permutacji, kombinacji lub wariacji.

Permutacje

Permutacją zbioru skończonego nazywamy każde ustawienie wszystkich jego elementów w pewnej kolejności.

Dwie permutacjepermutacjapermutacje uważamy za różne, gdy przynajmniej dwa elementy występują w nich na różnych miejscach. Wszystkich permutacji zbioru $n$ -elementowego jest $P_{n} = n!$ ,

gdzie

$n! = 1 \cdot 2 \cdot \dots \cdot n$ .

Ponadto przyjmuje się, że

$0! = 1$ .

Przykład 1

Wypisz wszystkie permutacje zbioru $\{A, B, C\}$ .

R1bRDtJ1yUXFA

W tym przypadku ważna jest kolejność. Postępując zgodnie ze schematem zaprezentowanym na powyższym rysunku, na pierwszym miejscu stawiamy $A$ , $B$ lub $C$ . Jeśli na pierwszym miejscu jest $A$ , to na dalszych mogą być $B$ , $C$ lub $C$ , $B$ . Analogicznie jest w przypadkach, gdy na pierwszym miejscu jest $B$ oraz $C$ .

W ten sposób łatwo obliczyć, że permutacji zbioru trójelementowego jest $3 \cdot 2 \cdot 1 = 3! = 6$ .

Analogicznie wyprowadza się wzór ogólny.

Przykład 2

Na ile sposobów można ustawić w kolejce trójkę dziewcząt i dwójkę chłopców? A co w sytuacji, gdy dziewczęta mają stać przed chłopcami?

R12DKEcaTKonG1

Na zdjęciu przedstawione są osoby stojące w kolejce na chodniku. Osoby pokazane są od połowy ciała w dół. — Źródło: dostępny w internecie: Obraz aykapog z Pixabay.

W pierwszej sytuacji nie jest istotna płeć. Mamy $3 + 2 = 5$ elementów ustawić w kolejce.

Tak więc $(3 + 2)! = 5! = 120$ , bo te ustawienia to po prostu permutacje.

W drugiej sytuacji dziewczęta muszą stać przed chłopcami. Popatrzmy więc na ten przykład jak na dwie kolejki – kolejkę dziewcząt i kolejkę chłopców.

Najpierw zastanówmy się, na ile sposobów możemy ustawić kolejkę dziewcząt?

Na $3! = 6$ sposobów, bo są $3$ dziewczynki.

Podobnie chłopców można ustawić na $2! = 2$ sposoby.

Zatem na podstawie reguły mnożeniareguła mnożeniareguły mnożenia dostajemy: $3! \cdot 2! = 6 \cdot 2 = 12$ ustawień.

Można je łatwo wypisać, oznaczmy dziewczynki literami: $A$ , $B$ i $C$ , a chłopców $F$ i $G$ , wówczas:

$A B C - F G$ , $A B C - G F$ ,
$A C B - F G$ , $A C B - G F$
$B A C - F G_{,}$ , $B A C - G F$
$B C A - F G$ , $B C A - G F$ ,
$C A B - F G$ , $C A B - G F$ ,
$C B A - F G$ , $C B A - G F$ .

Mamy więc $12$ ustawień, gdy dziewczynki stoją przed chłopcami.

Kombinacje

$k$ -elementową kombinacją zbioru $n$ -elementowego nazywamy dowolny $k$ -elementowy podzbiór tego zbioru. Kolejność występowania (wypisywania) elementów nie jest istotna.

Liczba kombinacjikombinacjakombinacji $k$ -elementowych zbioru $n$ -elementowego jest oznaczana symbolem $C_{n}^{k}$ i wynosi $(\binom{n}{k})$ .

Symbol $(\binom{n}{k})$ nazywamy symbolem Newtona lub współczynnikiem dwumianowym.

Dla ustalonego $n$ oraz $k \leq n$ mamy:

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

kombinacji $k$ -elementowych zbioru $n$ elementowego.

Przykład 3

Policz $(\binom{5}{0})$ , $(\binom{5}{1})$ , $(\binom{5}{2})$ , $(\binom{5}{3})$ , $(\binom{5}{4})$ , $(\binom{5}{5})$ .

$\begin{array}{lll} (\frac{5}{0}) = \frac{5!}{0! \cdot 5!} = 1 & (\frac{5}{5}) = \frac{5!}{5! \cdot 0!} = 1 \\ (\frac{5}{1}) = \frac{5!}{1! \cdot 4!} = \frac{4! \cdot 5}{1! \cdot 4!} = 5 & (\frac{5}{4}) = \frac{5!}{4! \cdot 1!} = \frac{4! \cdot 5}{4! \cdot 1!} = 5 \\ (\frac{5}{2}) = \frac{5!}{2! \cdot 3!} = \frac{3! \cdot 4 \cdot 5}{2! \cdot 3!} = 10 & (\frac{5}{3}) = \frac{5!}{3! \cdot 2!} = \frac{3! \cdot 4 \cdot 5}{3! \cdot 2!} = 10 \end{array}$

Ciekawostka

Łatwo zauważyć, że istnieje pewna symetria: $(\binom{n}{k}) = (\binom{n}{n - k})$ , oraz że wartości skrajne zawsze są równe: $(\binom{n}{0}) = (\binom{n}{n}) = 1$ , $(\binom{n}{1}) = (\binom{n}{n - 1}) = n$ . Wzory te wynikają bezpośrednio z definicji współczynników newtonowskich.

Przykład 4

Wypisz wszystkie kombinacje dwuelementowe zbioru ${A, B, C, D}$ .

Jest sześć takich kombinacji:

${A, B}, {A, C}, {A, D}, {B, C}, {B, D}, {C, D}$ .

Przykład 5

Na ile sposobów z grupy pięciu dziewcząt i pięciu chłopców można wybrać delegację złożoną z

trzech dziewcząt i dwóch chłopców,
trzech dziewcząt lub dwóch chłopców?

Rozwiązanie

W pierwszym przypadku: trójkę dziewcząt spośród 5 można wybrać na $(\binom{5}{3})$ sposobów, a dwójkę chłopców spośród pięciu na $(\binom{5}{2})$ sposobów, więc na mocy reguły mnożeniareguła mnożeniareguły mnożenia otrzymujemy:
$(\binom{5}{3}) \cdot (\binom{5}{2}) = 10 \cdot 10 = 100$ możliwości.
W drugim przypadku mamy wybrać delegację złożoną albo z trójki dziewcząt (można wybrać ją na $(\binom{5}{3})$ sposobów), albo z dwójki chłopców (tu mamy $(\binom{5}{2})$ możliwości), więc na mocy reguły dodawaniareguła dodawaniareguły dodawania otrzymujemy:
$(\binom{5}{3}) + (\binom{5}{2}) = 10 + 10 = 20$ możliwości.

Przykład 6

RN9lVesyd44fc1

Na zdjęciu przedstawiona jest talia kart ułożona w okrąg wierzchem do dołu. — Źródło: dostępny w internecie: www.pixabay.com.

Na ile sposobów można z talii $52$ kart wyciągnąć $13$ tak, aby były wśród nich:

dokładnie $4$ asy,
dokładnie $2$ asy,
dokładnie $2$ asy i dokładnie $2$ króle?

Rozwiązanie

W przypadku pierwszym mamy mieć wśród $13$ kart wszystkie $4$ asy, a brakujące $9$ kart może być dowolnymi kartami spośród $52 - 4 = 48$ kart, które pozostały po wybraniu asów. Tak więc mamy $(\binom{4}{4}) \cdot (\binom{48}{9})$ możliwości.
W drugim przypadku wiemy, że $2$ karty wybieramy spośród $4$ asów, $11$ brakujących kart zaś z pozostałych $48$ , zatem mamy: $(\binom{4}{2}) \cdot (\binom{48}{11})$ możliwości.
W trzecim przypadku mamy: $2$ karty z $4$ asów, $2$ karty z $4$ króli, pozostałe $9$ kart z $52 - 8 = 44$ kart, co daje nam: $(\binom{4}{2}) \cdot (\binom{4}{2}) \cdot (\binom{44}{9})$ możliwości.

Ciekawostka

Na ile sposobów można rozdać $52$ karty pomiędzy $4$ graczy tak, by każdy otrzymał po $13$ kart?

Pierwszy gracz może otrzymać dowolne $13$ kart z $52$ , czyli $(\binom{52}{13})$ .
Drugi może otrzymać dowolne $13$ kart z pozostałych $52 - 13 = 39$ kart, czyli $(\binom{39}{13})$ .
Trzeci może otrzymać dowolne $13$ kart z pozostałych $26$ kart, czyli $(\binom{26}{13})$ .
Czwartemu pozostanie ostatnie $13$ kart. Znając karty trzech pierwszych graczy, wiemy, jakie karty trafią do ostatniego. Jednak możemy zapisać to jako $(\binom{13}{13})$ .
Na mocy reguły mnożenia mamy zatem: $\begin{array}{l} (\binom{52}{13}) \cdot (\binom{39}{13}) \cdot (\binom{26}{13}) \cdot (\binom{13}{13}) = \frac{52!}{13 \cdot! 39!} \cdot \frac{39!}{13! \cdot 26!} \cdot \frac{26!}{13! \cdot 13!} \cdot \frac{13!}{13! \cdot 0!} = \frac{52!}{13! \cdot 13! \cdot 13! \cdot 13!} \end{array}$ .

W zadaniach tego typu ograniczamy się na ogół do podania takiej odpowiedzi, bez prowadzenia dalszych rachunków. Jednak dla osób ciekawych podajemy do wiadomości, że stanowi to $53 644 737 765 488 792 839 237 440 000$ możliwości.

Wariacje

$k$ -wyrazową wariacją bez powtórzeń $n$ -elementowego nazywamy każdy $k$ -wyrazowy ciąg różnych elementów tego zbioru, gdzie $1 \leq k \leq n$ .

Liczba wszystkich $k$ -wyrazowych wariacji bez powtórzeńwariacja bez powtórzeńwariacji bez powtórzeń zbioru $n$ -elementowego jest równa

$V_{n}^{k} = \frac{n!}{(n - k)!}$ .

Ciekawostka

Jeżeli rozważamy $n$ -wyrazową wariację bez powtórzeń zbioru $n$ -elementowego (czyli dotychczasowe $k = n$ ), to mamy do czynienia z permutacją.

Przykład 7

W pewnej klasie liczącej 24 uczniów postanowiono wybrać samorząd składający się z przewodniczącego, sekretarza i skarbnika. Na ile sposobów można to zrobić?

Każda możliwość składu samorządu to ciąg trzech osób (pierwsza – przewodniczący, druga – sekretarz, trzecia – skarbnik), więc jest to wariacja 3‑elementowa ze zbioru 24‑elementowego. Liczba wszystkich możliwości jest zatem równa $V_{24}^{3} = \frac{24!}{(24 - 3)!} = \frac{24!}{21!} = 22 \cdot 23 \cdot 24 = 12144$ .

Przykład 8

RU898D0XDWmo21

Na zdjęciu przedstawione są różnokolorowe puste krzesła stojące przy okrągłych stolikach w restauracyjnym ogródku. — Źródło: dostępny w internecie: www.pixabay.com.

Na ile sposobów można posadzić $2$ osoby na dwóch spośród czterech krzeseł? A gdy krzeseł mamy $n$ ?

Każda możliwość usadzenia osób to ciąg dwuwyrazowy, o wyrazach niepowtarzających się ze zbioru, odpowiednio, $4$ lub $n$ -elementowego.

Liczba wszystkich możliwości usadzeń wynosi

$V_{4}^{2} = \frac{4!}{(4 - 2)!} = \frac{4!}{2!} = 3 \cdot 24 = 12$ , gdy do wyboru są $4$ krzesła i $V_{n}^{2} = \frac{n!}{(n - 2)!} = \frac{(n - 2)! \cdot (n - 1) \cdot n}{(n - 2)!} = (n - 1) \cdot n$ , gdy do wyboru jest $n$ krzeseł.

$k$ -wyrazową wariacją z powtórzeniami zbioru $n$ -elementowego nazywamy każdy $k$ -wyrazowy ciąg elementów tego zbioru (dowolny element może wystąpić wielokrotnie w ciągu).

Liczba wszystkich $k$ -wyrazowych wariacji z powtórzeniamiwariacja z powtórzeniamiwariacji z powtórzeniami zbioru $n$ -elementowego jest równa $W_{n}^{k} = n^{k}$ .

Przykład 9

Ile można zapisać liczb dwucyfrowych (niekoniecznie różnocyfrowych!), mając do dyspozycji cyfry $1, 2, 3, 4, 5$ ?

Każda możliwość zapisania liczby dwucyfrowej o cyfrach ze zbioru ${1, 2, 3, 4, 5}$ , dopuszczając możliwość powtarzania się cyfr, jest dwuwyrazowym ciągiem ze zbioru $5$ -elementowego. Zatem liczba możliwości uzyskania liczb dwucyfrowych jest równa $W_{5}^{2} = 5^{2} = 25$ .

Przykład 10

RyCEi9sKGsXvb1

Na zdjęciu przedstawione są różnokolorowe tablice rejestracyjne. — Źródło: dostępny w internecie: www.pixabay.com.

Przyjmijmy, że numer na tablicach rejestracyjnych samochodu może składać się z dwóch dowolnych liter alfabetu łacińskiego, po których następuje pięć dowolnych cyfr.
Ile jest takich numerów, przyjmując, że alfabet łaciński składa się z 26 liter?

$W_{26}^{2} \cdot W_{10}^{5} = 26^{2} \cdot 10^{5} = 67600000$ możliwości.

Pomocnym w zrozumieniu różnic między permutacją, wariacją a kombinacją może być poniższy schemat.

RzaHfO111tUBp1

Na ilustracji przedstawiony jest schemat pomocny przy określeniu, z jakim typem zagadnienia mamy do czynienia. W prostokątach zapisane są pytania zamknięte, a linie wychodzące z tych prostokątów prowadzą ostatecznie do odpowiedzi. Pytanie główne: Czy kolejność jest ważna? Idą drogą „nie” dojdziemy do kombinacji, a z nich mamy dwie drogi: z powtórzeniami, które opisane są wzorem Cnk¯=n+k-1k. Druga możliwość to kombinacje bez powtórzeń opisane wzorem: Cnk=nk. Wracamy do głównego pytania. Jeśli kolejność jest ważna, to powstaje kolejne pytanie, mianowicie: Czy wszystkie elementy biorą udział w losowaniu? Jeśli nie, to mamy do czynienia z wariancją z powtórzeniami opisaną wzorem: Wnk=nk lub z wariancją bez powtórzeń opisaną wzorem: Vnk=n!n-k!. Jeśli natomiast kolejność ma znaczenie i wszystkie elementy biorą udział w losowaniu, to mamy do czynienia z permutacjami. Permutacje z powtórzeniami opisane są wzorem: Pnn1,n2,n3=n!n1!·n2!·n3!. Permutacje bez powtórzeń opisane są z kolei wzorem: Pn=n!.

Uwaga!

Kombinacje z powtórzeniami i permutacje z powtórzeniami wykraczają poza prezentowaną teorię w lekcji.

Polecenie 1

Przeanalizuj przykłady w animacji i rozwiąż zadania.

R1TnIeaXhqGKE

Polecenie 2

Na ile sposobów można ustawić w pary taneczne grupę pięciu dziewcząt i pięciu chłopców?
Na ile sposobów można ustawić w kolejce trójkę dziewcząt i trójkę chłopców tak, aby dziewczęta i chłopcy stali na przemian?

$P_{5} = 5! = 120$
$2 \cdot P_{3} \cdot P_{3} = 2 \cdot 3! \cdot 3! = 72$

Polecenie 3

Na ile sposobów można wypełnić test złożony z $k$ pytań, jeżeli na każde pytanie trzeba udzielić odpowiedzi TAK lub NIE?

$W_{2}^{k} = 2^{k}$

Polecenie 4

Na ile sposobów można wybrać trzyosobową komisję z grupy $5$ osób?

$C_{5}^{3} = (\binom{5}{3}) = \frac{5!}{3! \cdot 2!} = \frac{3! \cdot 4 \cdot 5}{3! \cdot 2!} = 10$

RItIBsqEH2fIa1

Ćwiczenie 1

R1inDRSqvgOVQ1

Ćwiczenie 2

R1ZDZu3mQrRtI2

Ćwiczenie 3

Ćwiczenie 4

Danych jest sześć punktów, z których żadne trzy nie leżą na jednej prostej. Ile różnych wielokątów wypukłych o wierzchołkach w tych punktach można utworzyć? Dla ułatwienia możesz skorzystać ze szkicownika. Odpowiedź wpisz w polu poniżej szkicownika.

Rw70ewBDevEF0

R1SSixXaJE011

Danych jest sześć punktów, z których żadne trzy nie leżą na jednej prostej. Ile różnych wielokątów wypukłych o wierzchołkach w tych punktach można utworzyć?

RHGaN3UPRdqWu

Ćwiczenie 5

Rysunek pokazuje jedną z dróg kulki do przegródki numer $5$ pomiędzy rzędami kołeczków. Kulka każdorazowo po odbiciu od kołeczka spada z jego prawej lub lewej strony wprost na kołeczek o jeden rząd niżej.

RD55hT7anc46g

RIuKHzArfUXPe

Ruvk3rMpgKhxi

RgZGkU6lfmEFR2

Ćwiczenie 6

Ćwiczenie 7

Każdą część figury przedstawionej na rysunku chcemy pomalować na jeden z $k$ kolorów. Na ile sposobów można to zrobić?

R1bUjQhs9Kfrc

Ilustracja przedstawia koło podzielone na trzy równe części.

R3vrzqg2HQtbj

R1J0fM4okoZXI3

Ćwiczenie 8

Słownik

permutacja

zbioru skończonego to każde ustawienie wszystkich jego elementów w pewnej kolejności

kombinacja

$k$ -elementowa zbioru $n$ - elementowego to każdy $k$ -elementowy podzbiór tego zbioru. Kolejność występowania (wypisywania) elementów nie jest istotna

wariacja z powtórzeniami

$k$ -wyrazowa, zbioru $n$ -elementowego to każdy $k$ -wyrazowy ciąg elementów tego zbioru (dowolny element może wystąpić wielokrotnie w ciągu)

wariacja bez powtórzeń

$k$ -wyrazowa, zbioru $n$ -elementowego to każdy $k$ -wyrazowy ciąg różnych elementów tego zbioru, gdzie $1 \leq k \leq n$

reguła mnożenia

liczba wszystkich możliwych wyników doświadczenia, polegającego na wykonaniu po kolei $n$ czynności, z których pierwsza może zakończyć się na jeden z $k_{1}$ sposobów, druga – na jeden z $k_{2}$ sposobów, trzecia – na jeden z $k_{3}$ sposobów i tak dalej do $n$ − tej czynności, która może zakończyć się na jeden z $k_{n}$ sposobów, jest równa $k_{1} \cdot k_{2} \cdot k_{3} \cdot . . . \cdot k_{n}$

reguła dodawania

jeżeli zbiory skończone $A_{1}, A_{2}, . . ., A_{n}$ są parami rozłączne, to liczba elementów zbioru $A_{1} \cup A_{2} \cup . . . \cup A_{n}$ jest równa sumie liczb elementów każdego ze zbiorów $A_{1}, A_{2}, . . ., A_{n} : | A_{1} \cup A_{2} \cup . . . \cup A_{n} | = | A_{1} | + | A_{2} | + . . . + | A_{n} |$

2. Doświadczenie losowe. Przestrzeń zdarzeń elementarnych

M_R_W22_M2 Rachunek prawdopodobieństwa, cz. 1