matematyka : Wariacje bez powtórzeń

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.

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

Twierdzenie

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$

Zadanie

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$

Zadanie

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

Zadanie

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.

Zadanie

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$

Zadanie

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$

Zadanie

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:

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).

Wykluczyć musimy więc

$7\cdot2=14$ wariacji.
Zatem dwie osoby mogą zasiąść w rzędzie liczącym osiem krzeseł, nie siedząc obok siebie, na

$56-14=42$ sposoby.

Zadanie

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