Z Skrypty dla studentów Ekonofizyki UPGOW
Spis treści |
Permutacja
Pojęcie permutacji dotyczy przestawiania (permutowania) obiektów lub wartości. Nieformalnie, permutacją zbioru obiektów jest ich rozmieszczenie w określonej kolejności.
Permutacja bez powtórzeń
Permutacją bez powtórzeń zbioru złożonego z \( n \) różnych elementów nazywamy każdy ciąg \( n \) wyrazowy utworzony ze wszystkich elementów zbioru. Wszystkich możliwych permutacji zbioru \( n \)-elementowego jest: \[P_n=n!\] gdzie symbol n silnia \(n!\) jest iloczynem kolejnych liczb naturalnych aż do n \[n!=1 \cdot 2 \cdot 3 \cdot \ldots \cdot n\] przy czym z definicji \(0!=1\), a także \(1!=1.\)
Dla przykładu elementy zbioru A={1,2,3} można ustawić na 3! = 3 \(\cdot\) 2 \(\cdot\) 1 = 6 sposobów: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) oraz (3,2,1). Wybierając pierwszy element permutacji mamy trzy możliwości wyboru, przy wyborze drugiego elementu już tylko dwie (bo ten wybrany poprzednio nie może sie powtórzyć), trzeci element jest zaś wtedy jednoznacznie określony (bedzie to jedyny element nie wybrany w poprzednich dwóch krokach).
Permutacja z powtórzeniami
Niech \( A \) oznacza zbiór złożony z \( k \) różnych elementów \( A \)={\(a_1,a_2,\ldots,a_k\)}. Permutacją \( n \) elementową z powtórzeniami, w której elementy \(a_1,a_2,\ldots,a_k\) powtarzają się odpowiednio \(n_1,n_2,\ldots,n_k\) razy, przy czym \(n=n_1+n_2+\ldots+n_k\), jest każdy \( n \)-wyrazowy ciąg, w którym elementy \(a_1,a_2,\ldots,a_k\) powtarzają się podaną liczbę razy. Liczba takich permutacji z powtórzeniami wynosi: \[P_n^{n_1,n_2, \ldots ,n_k} = \frac{n!}{n_1!\cdot n_2! \cdot \ldots \cdot n_k!}\]
Otrzymujemy \[P_n=n!=\frac{n!}{1!\cdot 1! \cdot \ldots \cdot 1!}\] w przypadku gdy każdy z elementów występuje dokładnie jeden raz.
Obliczymy liczbę permutacji z powtórzeniami zbioru zawierającego cztery kule, dwie białe i dwie czarne. Wstawiając do wzoru na liczbę perumtacji z powtórzeniami \(n = 4\) (cztery kule), oraz \(n_1 = n_2 = 2\) (kule biała i czarna powtarzają się po dwa razy) otrzymujemy \[P_4^{2,2} = \frac{4!}{2! \cdot 2!} = 6.\]
Oznaczając białą kulę przez \(b\), a czarną przez \(c\) możemy przekonać się o poprawności tego wyniku wypisując wszystkie sześć permutacji z powtórzeniami: \((bbcc), (bcbc), (bccb), (cbbc), (cbcb), (ccbb).\)
Kombinacja
Kombinacja jest to sposób wyboru kilku rzeczy z większej grupy, w której (w przeciwieństwie do permutacji) kolejność nie ma znaczenia. Na przykład biorąc pod uwagę kule o różnych kolorach, powiedzmy białą, czarną i czerwoną, istnieją trzy kombinacje dwóch kul, które można wyciągnąć z tego zestawu: biała i czarna, biała i czerwona lub czarna i czerwona. Losowanie liczb w grach liczbowych, jak np. losowanie 6-ciu liczb z 49-ciu jest kombinacją, ponieważ kolejność wylosowanych liczb nie ma znaczenia.
Kombinacja bez powtórzeń
Kombinacją k-elementową bez powtórzeń zbioru A składającego się z n różnych elementów nazywamy każdy k-elementowy podzbiór zbioru A, przy czym \(0 \leq k \leq n\). Liczba kombinacji k-elementowych bez powtórzeń w zbiorze n-elementowym \(C_n^k\) wyraża się następującym wzorem: \[C_n^k=\binom nk = \frac{n!}{k!\,(n-k)!} =\frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots1},\] gdzie \(\binom nk\) jest symbolem Newtona.
W zbiorze trzyelementowym A={1,2,3}, rozważanym powyżej, mieliśmy 3! = 3 \(\cdot\) 2 \(\cdot\) 1 = 6 permutacji. Gdy kolejność nie ma znaczenia to nie rozróżniamy poszczególnych ustawień (kolejności): (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) oraz (3,2,1). Otrzymujemy zatem jedną kombinację trzyelementową w zbiorze trzech elementów. Natomiast ilość kombinacji dwuelementowych w zbiorze A={1,2,3} wynosi trzy ({1,2}, {1,3} i {2,3}): \[C_3^2=\binom 32 = \frac{3!}{2!\,(3-2)!} = 3\]
Obliczymy na ile sposobów można wyciągnąć pięć kart z tali 52 kart. Kolejność wyciągniętych kart nie ma znaczenia, zatem trzeba znaleźć liczbę podzbiorów 5-cio elementowych w zbiorze 52 różnych elementów. Jest to kombinacja bez powtórzeń. \[ C_{52}^5 = {52 \choose 5} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311875200}{120} = 2598960\]
Kombinacja z powtórzeniami
Kombinacja k-elementowa z powtórzeniami w n-elementowym zbiorze A to każdy k-elementowy multizbiór składający się z elementów zbioru A, przy czym w odróżnieniu od kombinacji bez powtórzeń elementy mogą się powtarzać. Multizbiór, w którym elementy mogą występować wiele razy, jest rozszerzeniem pojęcia zbioru.
Dla przykładu z trzech elementów a, b, c, można utworzyć 6 dwuelementowych kombinacji z powtórzeniami: aa, ab, ac, bb, bc oraz cc.
Możemy także utworzyć 3-elementowe kombinacje z powtórzeniami zbioru 2-elementowego a, b. Można utworzyć 4 takie trójelementowe kombinacje z powtórzeniami: aaa, aab, abb oraz bbb. Pamiętamy, że w przypadku kombinacji kolejność elementów nie jest istotna.
Liczba k-elementowych kombinacji z powtórzeniami w zbiorze n-elementowym \( \bar{C}_n^k\) wyraża się następującym wzorem: \[ \bar{C}_n^k=\binom{k+n-1}{k}=\frac{(k+n-1)!}{k!(n-1)!}\]
Obliczymy na ile sposobów można wybrać trzy gałki lodów spośród 8 smaków, przy czym wybór jest zupełnie dowolny, tzn. możemy np. wybrać trzy (lub dwie) gałki lodów tego samego smaku. Jak widać są to kombinacje trójelementowe z powtórzeniami w zbiorze 8-miu elementów, przy czym zakładamy, że kolejność wkładania gałek lodów do kubka nie ma znaczenia. Otrzymujemy: \[ \bar{C}_8^3=\binom{3+8-1}{3}=\frac{(3+8-1)!}{3!(8-1)!}=120\]
Zachęcamy czytelnika do obliczenia na ile sposobów można wybrać 3 RÓŻNE smaki lodów spośród 8.
Wariacja
Wariacja jest to sposób wyboru kilku rzeczy z większej grupy, przy czym tak jak w przypadku permutacji kolejność ma znaczenie. Na przykład czterech zawodników A B C D może zdobyć 3 medale (złoty, srebrny i brązowy) na 24 sposoby: ABC, ABD, ACB,... Zachęcamy czytelnika do sprawdzenia.
Wariacja bez powtórzeń
k-wyrazową wariacją bez powtórzeń zbioru n-elementowego A (gdzie 1 ≤ k ≤ n) nazywamy każdy ciąg k-wyrazowy utworzony z różnych elementów tego zbioru. Jak pamiętamy kolejność elementów w ciągu jest istotna. Gdy k=n wariacja bez powtórzeń staje się permutacją - tworzymy ciągi ze wszystkich n elementów zbioru.
Liczba wszystkich k-wyrazowych wariacji bez powtórzeń zbioru n-elementowego \(V_n^k\) wyraża się następującym wzorem:
- \(V_n^k = {n! \over (n-k)!} = n \cdot (n-1) \cdot ... \cdot (n-k+1)\)
Zachodzi następujący związek pomiędzy liczbą wariacji bez powtórzeń, liczbą kombinacji i liczbą permutacji
\[V_n^k=C_n^k \cdot P_k\]
Obliczymy na ile sposobów można spośród 6-ciu sprinterów utworzyć sztafetę 4 razy 100 metrów. Po pierwsze zauważmy, że nie wiemy czy kolejność zmian jest ustalona (istotna) czy nie jest ustalona. Widzimy, że jeżeli kolejność zmian nie jest ustalona to jest to kombinacja czteroelementowa (4 sprinterów bo sztafeta 4 razy 100 m) w zbiorze 6-ciu sprinterów: \[C_6^4=\binom 64 = \frac{6!}{4!\,(6-4)!} = 15\]
Natomiast jeżeli kolejność zmian jest ustalona to wtedy każdą z kombinacji \(C_6^4\) trzeba pomnożyć przez liczbę ustawień czterech sprinterów czyli przez 4!. Otrzymujemy wariację czteroelementową w zbiorze 6-ciu elementów:
- \(V_6^4 = {6! \over (6-4)!} = 360\)
Jak widzimy ilość wariacji jest większa niż ilość kombinacji. Zachęcamy czytelnika do obliczenia ilości składów sztafet jeśli ustalone są dwie ostatnie zmiany.
Wariacja z powtórzeniami
k-elementową wariacją z powtórzeniami zbioru n-elementowego nazywamy każdy k-wyrazowy ciąg elementów tego zbioru, przy czym dowolny element zbioru może wystąpić wielokrotnie w ciągu. Należy zauważyć, że wariacja z powtórzeniami jest ciągiem co oznacza, że kolejność elementów ma znaczenie.
Liczba wszystkich k-wyrazowych wariacji z możliwymi powtórzeniami zbioru n-elementowego jest równa
- \(W_n^k = n^k\)
Obliczymy ile jest siedmiocyfrowych numerów telefonów nie zawierających cyfr 0 i 1. Cyfry w numerze telefonu mogą sie powtarzać i oczywiście istotna jest ich kolejność. Jest to zatem wariacja siedmioelementowa (numer siedmiocyfrowy) w zbiorze osmioelementowym (osiem cyfr). Otrzymujemy:
\[W_8^7=8^7=2097152\]
Zadania
- Jaka jest liczba słów długości k w n literowym alfabecie jeżeli dwie kolejne litery nie są takie same?
- Ile jest wszystkich liczb naturalnych dwucyfrowych, które są podzielne przez 6 lub przez 10?
- Cztery dziewczynki i sześciu chłopców siedzi na ławce. Dziewczynki siedzą obok siebie i chłopcy również siedzą obok siebie. Ile jest wszystkich możliwych sposobów posadzenia dzieci w taki sposób?
- Oblicz, ile jest liczb naturalnych sześciocyfrowych, w których występuje dokładnie trzy razy cyfra 0 i dokładnie jeden raz występuje cyfra 5.
- Spośród liczb {1,2,3,...,1000} losujemy jednocześnie dwie, które oznaczamy x i y . Ile jest możliwości wylosowania takiej pary liczb (x,y) dla której:
- x jest podzielne przez 23, a y nie jest podzielne przez 23?
- x i y jest podzielne przez 23?
- Ze zbioru dziesięciu cyfr {0,1,2,3,4,5,6,7,8,9} losujemy kolejno 4 cyfry bez zwracania, a następnie zapisujemy je w kolejności losowania tworząc liczbę 4 cyfrową. Ile można otrzymać w ten sposób
- dowolnych liczb?
- liczb podzielnych przez 25?
- Ile permutacji można utworzyć wybierając 3 różne cyfry ze zbioru cyfr od 0 do 9?
- Encyklopedia ma 8 tomów. Na ile sposobów można ułożyć tomy encyklopedii na półce.