styczeń 2016 - permutacje i kombinacje

W tym miesiącu odejdziemy od pojęć bezpośrednio związanych z rachunkiem prawdopodobieństwa i zajmiemy się pewnym zagadnieniem, które będzie nam pomocne w dalszych rozważaniach. Zagadnienie to jest poruszane na lekcjach matematyki pod koniec nauki w szkole ponadgimnazjalnej, mam jednak nadzieję, że nawet jeśli ktoś z czytelników już poznał je w szkole, to niniejszy miniwykład pozwoli lepiej je zrozumieć. Rozpocznijmy od przykładu.

Przykład 1. Na ile sposobów możemy ustawić w kolejności dwa różne obiekty? Na ile sposobów trzy? Na ile cztery?

Rozwiązanie. Dla rozwiązania zadania nie jest istotne, jaką naturę mają obiekty, które ustawiamy w kolejności (byle byłyby rozróżnialne). Mogą to być porcelanowe figurki na półce, książki na regale czy też dzieci recytujące po kolei kolejne zwrotki wiersza w czasie szkolnego apelu. Aby łatwiej było nam operować zadanymi obiektami, ponumerujemy je kolejnymi liczbami naturalnymi począwszy od 1.

Dwa obiekty możemy ustawić w kolejności w następujący sposób: 12 lub 21 (dla przejrzystości zapisu opuszczamy przecinki między kolejnymi liczbami tzn. nie piszemy 1, 2 lub 2, 1, ponieważ w tej sytuacji nie prowadzi to do nieporozumienia). Są więc dwa takie uporządkowania.

Trzem obiektom możemy nadać jedną z następujących kolejności: 123, 132, 213, 231; 312; 321. Widzimy, że możliwych kolejności jest sześć.

Przy czterech obiektach sytuacja staje się już znacznie bardziej skomplikowana, jednak przy odrobinie wytrwałości także możemy wypisać wszystkie możliwe sposoby ustawienia elementów. Są to: 1234; 1243; 1324; 1342; 1423; 1432; 2134; 2143; 2314; 2341; 3124; 3142; 3214; 3241; 4123; 4132; 4213; 4231; 4312; 4321. Tutaj mamy aż dwadzieścia możliwości.

Wraz ze wzrostem liczby elementów, które mamy ustawić w kolejności, wypisanie wszystkich możliwych kolejności staje się coraz bardziej kłopotliwe. Spróbujmy zatem zastanowić się, ile wynosi liczba ustawień danej liczby obiektów w kolejności bez wypisywania wszystkich możliwości.

Przykładu 1 c.d. Wyobraźmy sobie, że każde możliwe ustawienie elementów w kolejności realizujemy poprzez losowanie kolejno z urny wypełnionej ponumerowanymi kulami. Kolejność wyciągania kul będzie wyznaczała kolejność w uporządkowaniu obiektów.

Jeśli chcemy ustawić dwa elementy w kolejności, losujemy z urny, w której mamy dwie kule oznaczone numerami 1 i 2. Najpierw wyciągamy jedną z nich. Można to zrobić na dwa sposoby (gdyż możemy wyciągnąć albo kulę z numerem 1, albo kulę z numerem 2). W urnie została jedna kula, więc nie pozostaje nam nic innego jak tylko wyciągnąć ją. Pierwszą kulę możemy wyciągnąć na dwa sposoby a drugą na jeden sposób, w związku z czym liczba wszystkich sposobów ustawienia w kolejności dwóch elementów wynosi 2·1 = 2.

Gdy mamy do dyspozycji trzy elementy, w urnie umieszczamy kule z numerami 1, 2 i 3. Pierwszą kulę możemy wylosować na trzy sposoby. Kiedy ją wyciągniemy, w urnie pozostaną tylko dwie kule, a zatem kolejną kulę możemy wylosować już tylko na dwa sposoby. Podczas wyciągania z urny trzeciej kuli nie mamy już wyboru i wyciągamy ostatnią kulę, która pozostała w urnie. Liczba możliwych ustawień w kolejności zbioru trzyelementowego jest zatem równa 3·2·1 = 6.

Przy czterech elementach, które reprezentują kule z numerami 1, 2, 3 i 4, losując pierwszą kulę, mamy cztery możliwości wyboru. Po jej wyciągnięciu z urny pozostają trzy możliwości wyboru drugiej kuli, przy losowaniu trzeciej dwie, a przy wyciąganiu czwartej już tylko jedna. Liczba wszystkich możliwych ustawień czterech obiektów w kolejności wynosi zatem 4·3·2·1 = 20.

Myślę, że po tych rozważaniach nietrudno jest zauważyć, że jeśli zastanawialibyśmy się nad liczbą możliwych ustawień w kolejności n obiektów, to w naszym eksperymencie w urnie umieścilibyśmy kule o numerach 1, 2, ..., n. Wówczas pierwszą kulę możemy wylosować na n sposobów, zaś po jej wyciągnięciu następną kulę możemy wylosować na n-1 sposobów (bo w urnie zostało n-1 kul) itd. aż do ostatniej kuli pozostałej w urnie. W związku z tym liczba możliwych ustawień w kolejności n obiektów wynosi n·(n-1)·...·1.

Każde ustawienie elementów zbioru w kolejności nazywamy permutacją tego zbioru. Liczba permutacji zbioru n-elementowego wynosi zatem n·(n-1)·...·1 czyli (po zmianie kolejności czynników) jest iloczynem kolejnych liczb naturalnych od 1 do n. Iloczyn kolejnych liczb naturalnych od 1 do n oznaczamy jako n! (co czytamy jako: n silnia) tzn. n! = 1·2·...·(n-1)·n.  Ostatecznie możemy zatem powiedzieć, że liczba permutacji zbioru n-elementowego wynosi n!.

W przykładzie obliczyliśmy już pośrednio, że 2! (czytaj: dwa silnia) wynosi 2, 3! (czytaj: trzy silnia) wynosi 6 zaś 4!=20.

Pewien problem może sprawić określenie, ile wynosi 1! i 0!. O ile dość naturalnym jest przyjęcie, że 1! = 1, o tyle trudno byłoby równie łatwo odpowiedzieć na pytanie, ile wynosi 0! (na ile bowiem sposobów można ustawić w kolejności 0 elementów?). Przyjęto, że 0! = 1.

Stosunkowo łatwo też zauważyć, że (n+1)! = n!·(n+1). Istotnie

(n+1)! = 1·2·...·n·(n+1) = (1·2·...·n)·(n+1) = n!·n.

Można powiedzieć, że silnie rosną w dość zawrotnym tempie. Poniżej zamieszczamy silnie liczb od 1 do 10:

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5 040
8! = 40 320
9! = 362 880
10! = 3 628 800

Skoro 8! = 40320, to znaczy, że jeśli w biegu na zawodach lekkoatletycznych bierze udział 8 zawodników, to możliwa liczba kolejności na mecie teoretycznie wynosi aż 40320. Gdybyśmy kontynuowali rachowanie silni coraz większych liczb, przekonalibyśmy się zapis liczby 20! składa się z 18 cyfr, a 30! ma z kolei w zapisie aż 32 cyfry!

Od ustawiania w kolejności danych obiektów przejdźmy teraz do innego problemu

Przykład 2. W klasie jest 6 dziewcząt. Wychowawczyni ma za zadanie wybrać dwie spośród nich jako asystę pocztu sztandarowego. Na ile sposobów może dokonać takiego wyboru?

Rozwiązanie. Jeśli liczby 1, 2, 3, 4, 5 i 6 będą reprezentowały kolejne dziewczęta w ustalonym porządku, to na poniższej liście wszystkich możliwości osoby wybrane do pocztu sztandarowego są reprezentowane przez pogrubione liczby (tak jak poprzednio dla przejrzystości pomijamy przecinki rozdzielające liczby, gdyż nie prowadzi to do nieporozumień):

123456; 123456; 123456; 123456; 123456; 123456; 123456; 123456; 123456; 123456; 123456; 123456; 123456; 123456; 123456.

Wszystkich możliwości jest zatem 15.

Spróbujmy znaleźć rozwiązanie bez wypisywania wszystkich możliwości. Pierwszą uczennicę możemy wybrać na 6 sposobów, drugą zaś na 5 (bo do dyspozycji pozostało 5 uczennic). Czyżby zatem wszystkich możliwości było 6·5 = 30? Ależ nie! W naszym rozumowaniu tym razem nie liczy się kolejność, w jakiej poszczególne osoby będą wybierane, a zatem liczbę 30 należy jeszcze podzielić przez liczbę wszystkich ustawień w kolejności dwóch obiektów czyli przez liczbę 2! = 1·2 = 2. Ostatecznie otrzymujemy zatem ³⁰/₂  =15.

Spróbujmy nieco bardziej skomplikować sytuację.

Przykład 3. W dwudziestoczteroosobowej klasie składającej się z samych tylko chłopców wychowawczyni ma za zadanie wybrać trzech uczniów do pocztu sztandarowego. Na ile sposobów może dokonać takiego wyboru? Zakładamy, że nie jest istotne, który z uczniów będzie chorążym czyli niosącym sztandar, a którzy uczniowie będą w asyście.

Rozwiązanie. Pierwszego ucznia możemy wybrać na 24 sposoby, drugiego na 23 a trzeciego na 22, ponieważ jednak nie liczy się kolejność, w jakiej dokonaliśmy wyboru, liczbę 24·23·22 należy jeszcze podzielić przez 3! (jako że wybieramy trzech uczniów). W takim razie liczba możliwych składów pocztu sztandarowego wynosi [tex]\frac{24\cdot 23\cdot 22}{3!}=\frac{24\cdot 23\cdot 22}{6}=4\cdot 23\cdot 22=2024[/tex].

Nietrudno jest zauważyć, że jeśli wybieralibyśmy k obiektów spośród n (gdzie k<n), to liczbę takich możliwych wyborów obliczylibyśmy, dzieląc iloczyn n·(n-1)·...·(n-k+1) kolejnych liczb naturalnych (który składa się z k czynników) przez liczbę k!. Otrzymalibyśmy zatem [tex]\frac{n\cdot (n-1)\cdot ...\cdot (n-k+1)}{k!}[/tex]. Zapis ten nie jest zbyt wygodny. Zauważmy jednak, że

[tex]\frac{n\cdot (n-1)\cdot ...\cdot (n-k+1)}{k!}= \frac{n\cdot (n-1)\cdot ...\cdot (n-k+1)\cdot (n-k)\cdot (n-k-1)\cdot ...\cdot 2\cdot 1}{k!(n-k)\cdot (n-k-1)\cdot ...\cdot 2\cdot 1}=\frac{n!}{k!(n-k)!}[/tex].

Wielkość [tex]\frac{n!}{k!(n-k)!}[/tex] nazywamy symbolem Newtona i standardowo stosujemy oznaczamy ją jako [tex]{{n}\choose{k}}[/tex], co czytamy jako: n nad k (lub: n po k).

Każdy wybór składającego się z k elementów podzbioru zbioru n-elementowego nazywamy k-elementową kombinacją zbioru n-elementowego. Widzimy zatem, że liczba k-elementowych kombinacji zbioru n-elementowego wynosi [tex]{{n}\choose{k}}[/tex].

Łatwo jest zauważyć, że [tex]{{n}\choose{n-k}}={{n}\choose{k}}[/tex]. Istotnie,

[tex]{{n}\choose{n-k}}=\frac{n!}{(n-k)!(n-(n-k))!}=\frac{n!}{(n-k)!k!}={{n}\choose{k}}[/tex].

Warto również zwrócić uwagę, że

[tex]{{n}\choose{0}}=\frac{n!}{0!n!}=\frac{n!}{1\cdot n!}=1 [/tex] i [tex]{{n}\choose{1}}=\frac{n!}{1!(n-1)!}=\frac{(n-1)!\cdot n}{1\cdot (n-1)!}=n [/tex].

W takim razie również [tex]{{n}\choose{n}}={{n}\choose{n-0}}={{n}\choose{0}}=1[/tex] i [tex]{{n}\choose{n-1}}={{n}\choose{1}}=n[/tex].

Przykład 4. Oblicz: a) [tex]{{5}\choose{2}}[/tex], b) [tex]{{8}\choose{5}}[/tex].

Rozwiązanie. Symbol Newtona najłatwiej jest obliczyć, zapisując licznik i mianownik za pomocą silni, a następnie skracając ułamek przez większy spośród dwóch czynników w mianowniku, jak to pokazano poniżej:

a) [tex]{{5}\choose{2}}=\frac{5!}{2!\cdot 3!}=\frac{3!\cdot 4 \cdot 5}{2!\cdot 3!}=\frac{4 \cdot 5}{2}=10[/tex]

b) [tex]{{8}\choose{5}}=\frac{8!}{5!\cdot 3!}=\frac{5!\cdot 6 \cdot 7 \cdot 8}{5!\cdot 3!}=\frac{6 \cdot 7 \cdot 8}{6}=56[/tex]

Obliczanie symboli Newtona może być nieco żmudne. Istnieje jednak dość wygodny sposób obliczenia symboli Newtona dla niezbyt dużych liczb. Nosi on nazwę trójkąta Pascala.

Trójkąt Pascala to trójkątna tablica liczb, w której skrajnymi wyrazami w każdym wierszu są jedynki, a pozostałe liczby w danym wierszu powstają poprzez zsumowanie dwóch liczb znajdujących się nad daną liczbą w poprzednim wierszu.

Teoretycznie można napisać dowolną liczbę wierszy trójkąta Pascala. Poniższa animacja pomoże zrozumieć, jak powstają kolejne jego wiersze:

Co jednak trójkąt Pascala ma wspólnego z symbolami Newtona? Otóż k-ta liczba w n-tym wierszu trójkąta Pascala (przy czym zarówno wiersze jak i liczby w wierszach numerujemy od 0) to właśnie [tex]{{n}\choose{k}}[/tex]. Uważny czytelnik może odnaleźć wyniki z przykładu 4 w widocznym powyżej trójkącie Pascala.

Symbol Newtona i trójkąt Pascala pojawiają się w rozważaniach matematycznych w wielu kontekstach. (Jednym z nich jest zagadnienie, którego będzie dotyczył kolejny odcinek ligi. Właśnie ze względu na nie w tym miesiącu poznajemy symbol Newtona). Ciekawym zastosowaniem trójkąta Pascala są... wzory skróconego mnożenia. Przypomnijmy świetnie znany wzór na kwadrat sumy dwóch składników:

(a+b)² = a²+2ab+b².

Część spośród Was zna zapewne także wzór na sześcian sumy dwóch składników:

(a+b)³ = a³+3a²b+3ab²+b³.

Do tych dwóch wzorów dołóżmy jeszcze jedną oczywistą zależność: (a+b)¹ = a+b i zestawmy wszystko w tablicę:

(a+b)¹ = a+b
(a+b)² = a²+2ab+b²
(a+b)³ = a³+3a²b+3ab²+b³

Rzut oka na trójkąt Pascala pozwala nam stwierdzić, że kolejne współczynniki po prawej stronie wzoru na k-tą potęgę sumy dwóch składników to k-ty wiersz trójkąta Pascala (przy czym pamiętamy, że wiersze trójkąta Pascala numerujemy od zera). Przy użyciu trójkąta Pascala bez trudu możemy napisać, że:

(a+b)⁴ = a⁴+4a⁴b+6a²b²+4ab³+b⁴,

(a+b)⁵ = a⁵+5a⁴b+10a³b²+10a²b³+5ab⁴+b⁵

i ogólnie:

[tex](a+b)^n={{n}\choose{0}}a^nb^0+{{n}\choose{1}}a^{n-1}b+{{n}\choose{2}}a^{n-2}b^2+[/tex]

[tex]+\dots+{{n}\choose{n-2}}a^2b^{n-2}+{{n}\choose{n-1}}ab^{n-1}+{{n}\choose{n}} a^0b^n=[/tex]

[tex]=a^n+na^{n-1}b+{{n}\choose{2}}a^{n-2}b^2+\dots+{{n}\choose{n-2}}a^2b^{n-2}+nab^{n-1}+b^n[/tex].

Na koniec przeanalizujmy jeszcze jeden przykład:

Przykład 5. Klasa składa się z 8 dziewcząt i 16 chłopców. Nauczyciel wychowania fizycznego ma wytypować reprezentację klasy do turnieju tenisa stołowego składającą się z dwóch dziewcząt i dwóch chłopców. Na ile teoretycznie sposobów może to uczynić?

Rozwiązanie. Nauczyciel musi wybrać dwie osoby spośród ośmiu i oprócz tego dwie osoby spośród szesnastu. Liczba możliwych wyborów tych dwójek wynosi odpowiednio [tex]{{8}\choose{2}}[/tex] i [tex] {{16}\choose{2}}[/tex]. Ponieważ oba te wybory dokonywane są niezależnie od siebie i jednocześnie, liczba możliwych składów reprezentacji jest iloczynem tych dwóch liczb (co jest czasem określane jako reguła mnożenia), jest więc równa

[tex]{{8}\choose{2}}\cdot {{16}\choose{2}}=\frac{8!}{2!\cdot 6!}\cdot\frac{16!}{2!\cdot 14!}=\frac{6!\cdot 7\cdot 8}{2!\cdot 6!}\cdot\frac{14!\cdot 15\cdot 16}{2!\cdot 14!}=\frac{7\cdot 8}{2}\cdot \frac{15\cdot 16}{2}=7\cdot 4\cdot 15\cdot 8=3360[/tex].

O regule mnożenia, permutacjach i kombinacjach można przeczytać także w innym miejscu naszego portalu.

Zad. 1. Standardowe wydanie Ogniem i mieczem składa się z dwóch tomów, Potopu - z trzech tomów, zaś Pan Wołodyjowski jest wydawany w jednym tomie. Oblicz, na ile sposobów można ustawić obok siebie na regale wszystkie sześć tomów składających się na Trylogię w taki sposób, żeby poszczególne tomy danej powieści stały obok siebie. Kolejność tomów w obrębie jednej powieści jak również kolejność powieści jest dowolna. Przedstaw pełne rozwiązanie, odwołując się do wiedzy z niniejszego miniwykładu. Rozwiązania oparte na wypisaniu wszystkich możliwości nie zostaną uznane.

Zad. 2. Nauczyciel przygotowuje dla uczniów test jednokrotnego wyboru. Planuje przedłożyć każdemu uczniowi te same pytania, jednak chce, aby każdy uczeń miał je ułożone w innej kolejności. W klasie jest 27 uczniów. Ile co najmniej pytań musi liczyć test? Odpowiedź uzasadnij.

Zad. 3. Na lekcji WF pojawiło się 13 uczniów mogących wykonywać ćwiczenia. Nauczyciel polecił im podzielić się na dwie drużyny, by rozegrać mecz siatkówki, a ten uczeń, który nie znalazł się w żadnej z drużyn, miał być sędzią. Na ile sposobów uczniowie mogą się podzielić na dwie drużyny? Przedstaw pełne rozwiązanie, odwołując się do wiedzy z niniejszego miniwykładu. Rozwiązania oparte na wypisaniu wszystkich możliwości nie zostaną uznane.

Zad. 1. Przekątną wielokąta nazywamy dowolny odcinek o końcach w wierzchołkach tego wielokąta niebędący jego bokiem i zawarty całkowicie w tym wielokącie. Wielokąt nazywamy wypukłym, jeśli wszystkie jego przekątne są w nim zawarte. Oblicz, ile przekątnych ma wielokąt wypukły o n wierzchołkach.

Zad. 2. Uzupełnianie kolejnych wierszy trójkąta Pascala w sposób przedstawiony na animacji opiera się na następującej tożsamości:

[tex]{{n-1}\choose{k-1}}+{{n-1}\choose{k}}={{n}\choose{k}}[/tex].

Udowodnij tę tożsamość.

Zad. 3. Oblicz 2¹⁰ jako (1+1)¹⁰, korzystając z odpowiedniego wzoru skróconego mnożenia.