Permutacje
Definicja
Permutacją zbioru \(n\)-elementowego nazywamy każdy \(n\)-wyrazowy ciąg utworzony ze
wszystkich elementów tego zbioru.
Z definicji wynika, że każda permutacja zawiera wszystkie elementy permutowanego zbioru
oraz że istotna jest kolejność elementów permutacji. Oznacza to, że różne permutacje zbioru otrzymujemy,
ustawiając wszystkie jego elementy w różne ciągi.
Przykład
Wyznaczymy wszystkie możliwe permutacje zbioru \(A=\{a,b,c\}\).Zauważmy, że na pierwszym miejscu permutacji może stać jeden z trzech elementów: \(a,\) \(b\) lub \(c\). Są więc trzy sposoby wyboru pierwszego elementu:
\(\left(a,-,-\right)\) albo \(\left(b,-,-\right)\), albo \(\left(c,-,-\right)\)
Na drugim miejscu permutacji może stać już tylko jeden z pozostałych, po wyborze pierwszego, elementów.
Zatem mamy dwa sposoby wyboru drugiego elementu:
\(\left(a,b,-\right)\) lub \(\left(a,c,-\right)\), jeżeli jako pierwszy wybraliśmy element \(a\)
\(\left(b,a,-\right)\) lub \(\left(b,c,-\right)\), jeżeli jako pierwszy wybraliśmy element \(b\)
\(\left(c,a,-\right)\) lub \(\left(c,b,-\right)\), jeżeli jako pierwszy wybraliśmy element \(c.\)
Na trzecim miejscu permutacji może stać już tylko jeden element, pozostały po wyborze pierwszych dwóch.
Stąd mamy tylko jeden sposób wyboru trzeciego elementu i otrzymujemy następujące
permutacje:
\((a,b,c)\), \((a,c,b)\), \((b,a,c)\), \((b,c,a)\), \((c,a,b)\), \((c,b,a)\)
Z elementów zbioru \(A=\{a,b,c\}\) można więc utworzyć
\(\czerwony{\boldsymbol 3}\cdot\niebieski{\boldsymbol 2}\cdot\zielony{\boldsymbol 1}=3!=6\) permutacji.
Jeżeli \(P_n\) oznacza liczbę wszystkich możliwych permutacji zbioru \(n\)-elementowego, to
\[P_n=n!\]
Na ile sposobów może ustawić się w szeregu grupa pięciu chłopców i pięciu dziewcząt, tak aby
dwie osoby tej samej płci nie stały obok siebie?
Skoro dwie osoby jednej płci nie mają stać obok siebie, to znaczy, że dziewczynki i chłopcy
stoją w szeregu na zmianę. Taki szereg może rozpoczynać chłopiec lub dziewczynka, więc mamy
dwa sposoby rozpoczęcia szeregu. W szeregu tych pięciu chłopców możemy ustawić
na 5! sposobów i pięć dziewcząt także możemy ustawić na
5! sposobów.
Zgodnie z regułą mnożenia wszystkich takich szeregów jest \(\czerwony{\boldsymbol 2}\cdot\niebieski{\boldsymbol{5!}}\cdot\zielony{\boldsymbol{5!}} = 28\ 800\).
Zgodnie z regułą mnożenia wszystkich takich szeregów jest \(\czerwony{\boldsymbol 2}\cdot\niebieski{\boldsymbol{5!}}\cdot\zielony{\boldsymbol{5!}} = 28\ 800\).
Ile różnych liczb \(5\)-cyfrowych takich, aby żadna cyfra w liczbie nie powtarzała się, można
utworzyć z cyfr: \(0\), \(1\), \(2\), \(3\), \(4\)?
Tworząc \(5\)-cyfrową liczbę z cyfr: \(0,\) \(1,\) \(2,\) \(3,\) \(4,\) musimy pamiętać, że pierwsza cyfra
nie może być zerem. Na pierwszym miejscu może zatem stać tylko jedna z czterech cyfr: \(1,\) \(2,\) \(3,\)
\(4,\) więc mamy cztery sposoby wyboru pierwszej cyfry. Pozostałe cztery miejsca
tworzonej liczby są już dowolną permutacją zbioru \(4\)-elementowego, gdyż wybraną jako pierwszą cyfrę
zastąpi, nie brane wcześniej pod uwagę, zero.
Zgodnie z regułą mnożenia wszystkich takich \(5\)-cyfrowych liczb można utworzyć \(\czerwony{\boldsymbol 4}\cdot4! = 96\).
Zgodnie z regułą mnożenia wszystkich takich \(5\)-cyfrowych liczb można utworzyć \(\czerwony{\boldsymbol 4}\cdot4! = 96\).
Do autobusu wsiada grupa pasażerów składająca się z sześciu kobiet i czterech mężczyzn.
Ile istnieje wszystkich możliwych sposobów wejścia pasażerów do autobusu, jeżeli pasażerowie
wsiadają pojedynczo, ale pierwsze wsiadają kobiety?
Grupa sześciu kobiet może wejść do autobusu pojedynczo na tyle sposobów, ile istnieje permutacji
zbioru \(6\)-elementowego, czyli \(6!\) Dla każdego z wymienionych ustawień sześciu kobiet grupa
czterech mężczyzn może wsiąść do autobusu na \(4!\) sposoby. Wszystkich możliwych sposobów
wsiadania jest \(6!\cdot4! = 720\cdot24 = 17\ 280\).
Ile jest różnych funkcji różnowartościowych działających ze zbioru \(X=\{x_1,x_2,x_3\}\)
w zbiór \(Y=\{y_1,y_2,y_3\}\)?
Zadanie polega na ustaleniu, ile jest możliwości przyporządkowania każdemu elementowi ze zbioru \(X\)
innego elementu ze zbioru \(Y\). Ponieważ \(\stackrel {=}{X}\:=\:\stackrel{=}{Y}\:=3\), to wszystkie
elementy zbioru \(Y\) muszą zostać wykorzystane. Mamy zatem do czynienia
z permutacją \(3\)-elementowego zbioru \(Y=\{y_1,y_2,y_3\}\).
Zgodnie z twierdzeniem o liczbie permutacji wszystkich funkcji różnowartościowych działających ze zbioru \(X\)
w zbiór \(Y\) jest \(3!=6\).
Pięcioro znajomych: Ala, Darek, Ela, Gosia i Karol, zarezerwowało pięć biletów do kina,
wybierając pięć kolejnych miejsc w jednym rzędzie.
-
Na ile różnych sposobów mogą oni zająć te miejsca?Ponieważ każdy z pięciorga znajomych może zająć tylko jedno z pięciu zarezerwowanych miejsc, to wszystkich możliwych sposobów jest tyle, ile permutacji zbioru \(5\)-elementowego, czyli \(5!\).
-
Na ile różnych sposobów mogą zająć te miejsca, jeżeli Gosia i Karol chcą siedzieć obok siebie?Skoro Gosia i Karol mają siedzieć obok siebie, to muszą zająć dwa sąsiednie miejsca. Wyboru dwóch sąsiednich miejsc z pięciu można dokonać na 4 sposoby, według jednego ze schematów:\(\left(\blacksquare,\blacksquare,-,-,-\right)\) albo \(\left(-,\blacksquare,\blacksquare,-,-\right)\), albo \(\left(-,-,\blacksquare,\blacksquare,-\right)\), albo \(\left(-,-,-,\blacksquare,\blacksquare\right)\)W każdym z powyższych schematów są dwie możliwości zajęcia wskazanych miejsc przez Gosię i Karola. Na przykład jeśli zajmą oni pierwsze dwa miejsca, to mogą usiąść na dwa sposoby:\(\left(G,K,-,-,-\right)\) lub \(\left(K,G,-,-,-\right)\)Pozostałe trzy osoby mogą zająć swoje miejsca dowolnie, więc na 3! sposoby.
Zatem zgodnie z regułą mnożenia znajomi mogą zająć swoje miejsca tak, aby Gosia i Karol siedzieli obok siebie na \(\czerwony{\boldsymbol 4}\cdot\niebieski{\boldsymbol 2}\cdot\zielony{\boldsymbol{3!}}=48\) sposobów.
Przemek urodził się w \(1972\) roku, a jego córka Marysia w \(2001\). Ile różnych
\(4\)-cyfrowych kodów może utworzyć każdy z nich, przestawiając dowolnie cyfry swojego roku urodzenia?
W obydwu przypadkach mamy do czynienia z permutacją zbioru \(4\)-elementowego.
Z cyfr roku urodzenia Przemka \(1\), \(9\), \(7\), \(2\) możliwe jest utworzenie \(4!=24\) różnych kodów \(4\)-cyfrowych. Natomiast z cyfr roku urodzenia Marysi \(2\), \(0\), \(0\), \(1\) można utworzyć dwukrotnie mniej kodów, ponieważ mamy do dyspozycji dwie cyfry \(0\), których przestawienie nie daje nowego kodu. Marysia może utworzyć \(\frac{4!}{2}=\frac{24}{2}=12\) różnych \(4\)-cyfrowych kodów.
Z cyfr roku urodzenia Przemka \(1\), \(9\), \(7\), \(2\) możliwe jest utworzenie \(4!=24\) różnych kodów \(4\)-cyfrowych. Natomiast z cyfr roku urodzenia Marysi \(2\), \(0\), \(0\), \(1\) można utworzyć dwukrotnie mniej kodów, ponieważ mamy do dyspozycji dwie cyfry \(0\), których przestawienie nie daje nowego kodu. Marysia może utworzyć \(\frac{4!}{2}=\frac{24}{2}=12\) różnych \(4\)-cyfrowych kodów.
Na ile sposobów można umieścić siedem ponumerowanych kul w siedmiu szufladach tak, aby żadna
szuflada nie została pusta, a na ile w ośmiu szufladach tak, aby tylko jedna z nich została pusta?
Mamy do czynienia z permutacją \(7\)-elementowego zbioru ponumerowanych kul. Po umieszczeniu
kul pojedynczo w siedmiu szufladach żadna z nich nie zostanie pusta. Różnych sposobów takiego
rozłożenia kul jest \(7!=5040\).
Po umieszczeniu kul pojedynczo w ośmiu szufladach jedna z nich pozostanie pusta. Wyboru szuflady, która będzie pusta, można dokonać na osiem sposobów, a umieścić kule w siedmiu pozostałych szufladach można na \(7!=5040\) sposobów. Zatem możliwości umieszczenia siedmiu kul w ośmiu szufladach tak, aby tylko jedna z nich została pusta, jest \(\czerwony{\boldsymbol 8}\cdot7!=8\cdot5040=40\ 320\).
Po umieszczeniu kul pojedynczo w ośmiu szufladach jedna z nich pozostanie pusta. Wyboru szuflady, która będzie pusta, można dokonać na osiem sposobów, a umieścić kule w siedmiu pozostałych szufladach można na \(7!=5040\) sposobów. Zatem możliwości umieszczenia siedmiu kul w ośmiu szufladach tak, aby tylko jedna z nich została pusta, jest \(\czerwony{\boldsymbol 8}\cdot7!=8\cdot5040=40\ 320\).
Reguła mnożenia
Jeżeli dane są dwa zbiory skończone \(A\) i \(B\), z których zbiór \(A\) ma \(m\) elementów,
a zbiór \(B\) ma \(n\) elementów, to liczba różnych par \((a,b)\), takich że \(a\in A\) i \(b\in B\),
jest równa iloczynowi mocy tych zbiorów: \(m\cdot n\).
Jeżeli dane są dwa zbiory skończone \(A\) i \(B\), z których zbiór \(A\) ma \(m\) elementów,
a zbiór \(B\) ma \(n\) elementów, to liczba różnych par \((a,b)\), takich że \(a\in A\) i \(b\in B\),
jest równa iloczynowi mocy tych zbiorów: \(m\cdot n\).
Twierdzenie o liczbie permutacji
Jeżeli \(P_n\) oznacza liczbę wszystkich możliwych permutacji zbioru \(n\)-elementowego, to \[P_n=n!\]
Jeżeli \(P_n\) oznacza liczbę wszystkich możliwych permutacji zbioru \(n\)-elementowego, to \[P_n=n!\]