Wariacje bez powtórzeń
Definicja
Wariacją \(k\)-elementową bez powtórzeń utworzoną ze zbioru \(n\)-elementowego \((k\le n)\)
nazywamy każdy \(k\)-wyrazowy ciąg różnych elementów z tego zbioru.
Z definicji wynika, że wariacja bez powtórzeń zawiera jedynie określoną liczbę
\(k \left(k\le n\right)\) różnych elementów spośród danych \(n\) elementów oraz że istotna
jest kolejność elementów wariacji. Z \(k\)-wyrazowymi wariacjami bez powtórzeń zbioru \(n\)-elementowego
mamy do czynienia wówczas, gdy \(k\) razy wybieramy po jednym elemencie z danego zbioru \(n\)-elementowego
i nie zwracamy go po wylosowaniu.
Jeżeli \(k=n\), to \(k\)-elementowa wariacja bez powtórzeń utworzona ze zbioru \(n\)-elementowego jest permutacją tego zbioru.
Jeżeli \(k=n\), to \(k\)-elementowa wariacja bez powtórzeń utworzona ze zbioru \(n\)-elementowego jest permutacją tego zbioru.
Przykład
Wyznaczymy wszystkie możliwe \(2\)-elementowe wariacje bez powtórzeń zbioru \(A=\{a,b,c\}\).
Zauważmy, że na pierwszym miejscu \(2\)-elementowej wariacji bez powtórzeń 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 \(2\)-elementowej wariacji 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.\)
Z elementów zbioru \(A\) można zatem utworzyć \(\czerwony{\boldsymbol 3}\cdot\niebieski{\boldsymbol{2=}}6\)
następujących \(2\)-elementowych wariacji bez powtórzeń:
\((a,b)\), \((a,c)\), \((b,a)\), \((b,c)\), \((c,a)\), \((c,b)\)
Jeżeli \(k\le n\) oraz \(V_n^k\) oznacza liczbę wszystkich możliwych \(k\)-elementowych
wariacji bez powtórzeń zbioru \(n\)-elementowego, to
\[V_n^k=\frac{n!}{\left(n-k\right)!}=
\frac{\ccancel{\fioletowy}{\left(n-k\right)!}\cdot \left(n-k+1\right)\cdot\left(n-k+2\right) \cdot \ldots \cdot n}
{\ccancel{\fioletowy}{\left(n-k\right)!}}=
\left(n-k+1\right)\cdot\left(n-k+2\right) \cdot \ldots \cdot n\]
Ile różnych liczb \(3\)-cyfrowych takich, aby żadna cyfra w liczbie nie powtarzała się,
można utworzyć z cyfr: \(1\), \(2\), \(3\), \(4\), \(5\)?
Zadanie to polega na utworzeniu \(3\)-wyrazowych ciągów z \(5\)-elementowego zbioru cyfr
\(\{1,2,3,4,5\}\). Mamy do czynienia z \(3\)-elementową wariacją bez powtórzeń zbioru \(5\)-elementowego.
Zatem tak utworzonych liczb \(3\)-cyfrowych jest
\[V_5^3=\frac{5!}{\left(5-3\right)!}=\frac{5!}{2!}=
\frac{\ccancel{\fioletowy}{2!}\cdot3\cdot4\cdot5}{\ccancel{\fioletowy}{2!}}=60\]
Ile jest liczb \(5\)-cyfrowych o niepowtarzających się cyfrach, jeżeli pierwsza cyfra
jest parzysta, a pozostałe są nieparzyste?
Zadanie to polega na utworzeniu \(5\)-wyrazowych ciągów, których pierwsze wyrazy należą
do zbioru cyfr parzystych \(\{2,4,6,8\}\), a pozostałe cztery wyrazy są różne i należą do
zbioru \(\{1,3,5,7,9\}\). Wyboru pierwszej cyfry tworzonej liczby można dokonać na
cztery sposoby. Pozostałe cztery cyfry to \(4\)-elementowe wariacje
bez powtórzeń zbioru \(5\)-elementowego, więc jest ich
\[V_5^4=\frac{5!}{\left(5-4\right)!}=\frac{5!}{1!}=5!=120\]
Zgodnie z regułą mnożenia \(5\)-cyfrowych liczb spełniających warunki zadania jest
\(\czerwony{\boldsymbol 4}\cdot120=480\).
W turnieju szachowym wystartowało dziesięciu zawodników. Na pierwszym etapie każdy z każdym
rozgrywa jedną partię i rewanż. Ile wszystkich partii szachów zostanie rozegranych na tym etapie?
Mamy do czynienia z wariacją bez powtórzeń, a liczba wszystkich rozegranych partii jest równa
liczbie \(2\)-wyrazowych wariacji bez powtórzeń zbioru dziesięciu zawodników
\[V_{10}^2=\frac{10!}{\left(10-2\right)!}=\frac{10!}{8!}=
\frac{\ccancel{\fioletowy}{8!}\cdot9\cdot10}{\ccancel{\fioletowy}{8!}}=90\]
Na pierwszym etapie turnieju zostanie więc rozegranych \(90\) partii.
W biegu startuje dziesięciu zawodników. Ile istnieje możliwości przyznania punktów za zajęcie miejsca
na podium, przy założeniu, że wszyscy dobiegli do mety?
Ponieważ jeden zawodnik może zająć tylko jedno miejsce i kolejność ukończenia biegu jest ważna,
to mamy \(3\)-wyrazowe wariacje bez powtórzeń zbioru dziesięciu zawodników. Możliwości przyznania
punktów za trzy pierwsze miejsca jest więc:
\[V_{10}^3=\frac{10!}{\left(10-3\right)!}=\frac{10!}{7!}=
\frac{\ccancel{\fioletowy}{7!}\cdot8\cdot9\cdot10}{\ccancel{\fioletowy}{7!}}=720\]
Ile można utworzyć 3-literowych wyrazów (mających sens lub nie), dysponując \(24\)-literowym
alfabetem, jeżeli litery w wyrazach nie powtarzają się?
Ze zbioru \(24\) liter musimy utworzyć \(3\)-wyrazowe ciągi, w których litery się nie powtarzają.
Możemy zatem utworzyć tyle takich wyrazów, ile jest \(3\)-wyrazowych wariacji bez powtórzeń zbioru
\(24\)-elementowego, czyli
\[V_{24}^3=\frac{24!}{\left(24-3\right)!}=\frac{24!}{21!}=
\frac{\ccancel{\fioletowy}{21!}\cdot22\cdot23\cdot24}{\ccancel{\fioletowy}{21!}}=12\ 144\]
Na ile sposobów można posadzić dwie osoby w rzędzie liczącym osiem krzeseł tak, aby nie siedziały
obok siebie?
Dwie osoby można posadzić w rzędzie złożonym z ośmiu krzeseł na tyle sposobów, ile jest
\(2\)-wyrazowych wariacji bez powtórzeń \(8\)-elementowego zbioru krzeseł, czyli
\[V_8^2=\frac{8!}{\left(8-2\right)!}=\frac{8!}{6!}=\frac{\ccancel{\fioletowy}{6!}\cdot7\cdot8}{\ccancel{\fioletowy}{6!}}=56\]
Jednak wśród nich są przypadki, w których dwie osoby musiałyby siedzieć obok siebie, więc trzeba
je wykluczyć. Liczba takich niedopuszczalnych wariacji zależy od:
Zatem dwie osoby mogą zasiąść w rzędzie liczącym osiem krzeseł, nie siedząc obok siebie, na \(56-14=42\) sposoby.
- możliwości wyboru dwóch sąsiednich krzeseł spośród ośmiu (siedem możliwości)
\(\left(\blacksquare,\blacksquare,-,-,-,-,-,-\right)\) albo \(\left(-,\blacksquare,\blacksquare,-,-,-,-,-\right)\), albo \(\left(-,-,\blacksquare,\blacksquare,-,-,-,-\right)\), albo \(\left(-,-,-,\blacksquare,\blacksquare,-,-,-\right)\), albo \(\left(-,-,-,-,\blacksquare,\blacksquare,-,-\right)\), albo \(\left(-,-,-,-,-,\blacksquare,\blacksquare,-\right)\), albo \(\left(-,-,-,-,-,-,\blacksquare,\blacksquare\right)\) oraz - sposobu zajęcia wskazanych dwóch miejsc przez te osoby (dwa sposoby).
Zatem dwie osoby mogą zasiąść w rzędzie liczącym osiem krzeseł, nie siedząc obok siebie, na \(56-14=42\) sposoby.
Ile jest różnych funkcji różnowartościowych działających ze zbioru \(X=\{x_1,x_2\}\)
do zbioru \(Y=\{y_1,y_2,y_3,y_4\}\)?
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}\:=2 \lt \: \stackrel{=}{Y}\:=4\), to każda taka
funkcja wykorzysta tylko dwa elementy ze zbioru \(Y\). Mamy zatem do czynienia
z \(2\)-elementową wariacją bez powtórzeń \(4\)-elementowego zbioru \(Y\).
Zgodnie z twierdzeniem o liczbie wariacji bez powtórzeń wszystkich funkcji różnowartościowych działających ze zbioru \(X\)
w zbiór \(Y\) jest
\[V_4^2=\frac{4!}{\left(4-2\right)!}=
\frac{\ccancel{\fioletowy}{2!}\cdot 3\cdot 4}{\ccancel{\fioletowy}{2!}}=12\]
Twierdzenie o liczbie wariacji bez powtórzeń
Jeżeli \(k\le n\) oraz \(V_n^k\) oznacza liczbę wszystkich możliwych
\(k\)-elementowych wariacji bez powtórzeń zbioru \(n\)-elementowego, to \[V_n^k=\frac{n!}{\left(n-k\right)!}\]
Jeżeli \(k\le n\) oraz \(V_n^k\) oznacza liczbę wszystkich możliwych
\(k\)-elementowych wariacji bez powtórzeń zbioru \(n\)-elementowego, to \[V_n^k=\frac{n!}{\left(n-k\right)!}\]