Przeczytaj

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

Na ilustracji przedstawiony jest schemat różnych połączeń pomiędzy punktami. Narysowany po lewo punkt wyjściowy oznaczony jest jako

\{A, B, C\}

. Z tego punktu poprowadzone są w prawo trzy rozwidlenia do punktów ustawionych pionowo : A, B, C. Z każdego z tych punktów poprowadzone są dwa kolejne rozwidlenia do punktów nazwanych pozostałymi literami, odpowiednio z A do B i C, z B do B i A oraz z C do A i B. Każdy następny punkt łączy się z jednym punktem oznaczonym niewykorzystaną w danym rozwidleniu literą. Mamy zatem 5 następujących układów liter A, B, C takich, że litery w układzie się nie powtarzają: A B C, A C B, B A C, B C A, C A B, C B A.

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.

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} |$

Wprowadzenie

Animacja

Permutacje

Kombinacje

Wariacje

Słownik