DSCF2502

26 2. Kombinatoryka

stanu cywilnego (będący w związku małżeńskim lub nie) i zawodu. Jeśli założymy, że jest 17 różnych zawodów, to wszystkich możliwych klas ludzi jest wówczas 2-2-17 = 68. Każda klasa zawiera 3 elementy (cechy) np.: mężczyzna, żonaty, lekarz.

Niech będzie dany zbiór złożony z n różnych elementów: a_x, a₂, a₃,..., o*. Zbiór ten nazwijmy populacją

8		•
7		tv
6		•
5		•
4		•
3		•
2	•	w
1		•
	a	b	c	d	e	f	9	h

Rys. 2.1.1

generalną (*).

Definicja 2.1.1. Dowolny zbiór a_Jt, a_Sl, a_j3,a_Jk, którego elementy są elementami populacji generalnej, nazywamy próbką o liczności k.

Możliwe są dwa sposoby pobierania próbki: pierwszy pi ze zwracaniem, drugi Eg bez zwracania elementów do populacji po ich pobraniu. W pierwszym przypadku pobranie elementu następuje za każdym razem z całej populacji generalnej tak, że ten sam element może być wybrany więcej niż jeden raz, tzn. w próbce mogą zdarzyć się powtórzenia i liczność jej może nawet przekraczać liczność populacji generalnej. W drugim przypadku kolejno pobranych elementów nie zwracamy do populacji generalnej, w związku z czym próbka nie zawiera powtarzających się elementów samej populacji generalnej (A:<n). Dopiero po pobraniu próbki może być ona zwTÓcona do populacji generalnej, a tym samym nowa fc-elementowa próbka może mieć elementy, które zawierała poprzednia. Może się zdarzyć, że pewne próbki będą miały te same i pobrane w tym samym porządku elementy.

Zauważmy, że jeśli porządek elementów w próbce nie jest uwzględniany, to tworzenie próbki przez jednoczesne pobranie elementów z populacji jest równoważne tworzeniu próbki przez ich kolejne pobieranie bez zwrotu.

§ 2.2. Wariacje bez powtórzeń

Definicja 2.2.1. Wariacją (rozmieszczeniem) bez powtórzeń z n elementów po k elementów nazywamy uporządkowany zbiór składający się z k różnych elementów, wybranych spośród n różnych elementów.

Liczbę wariacji bez powtórzeń z n elementów po k oznaczamy symbolem V*.

Przykład 2.2.1. Obliczyć, ile można utworzyć wariacji z n elementów: a) po jednym, b) po dwa, c) po trzy oraz wypisać je wszystkie.

Rozwiązanie, a) Istnieje n wariacji z n elementów po 1. Są to po prostu elementy a_lt02,a_Zy..., a_m.

b) Mamy następujące wariacje z n		elementów po 2:
^a\ ^a2	0103	0,04 ... ata,
a2at	02 03	a2aA ... n20i
*3 01	03 02	03 ••• «a 0,
^fl*0i	0„ 02	0. 03 — 0» 0,

(*) Rozpatrujemy tutaj jedynie populacje generalne skończone.

f W każdym wierszu znajduje się u — 1 wariacji, a w każdej kolumnie n wariacji. Ogólna |lość wariacji jest zatem równa V~ =«•(/!—]). W tablicy nie występują takie układy elementów, jak: AjOi, a₂a₂. — a„a„, gdyż ejementy w rozważanych zbiorach nie mogą się powtarzać.

c) Mamy następujące wariacje z n elementów po 3:

ala2a3	di a2 a4	ala2as	a1a2am
aLa3a2	ata3a4	ata3as IX
ala4a2	o j a4a3	a1a4a 5 HB	<*i a4aM
^al ^an ^a2	ataaa3	aIa„a4	diouaR_!
a2 a i Oj	a2ala4	a2aia5h	a2 a | a„
a2a3al	^fl2^fl3^fl4	a2a3a5	a2a3au
^an^an-\^a\		d-d.-ld3 —	d» d*— i d,,

Wariacje znajdujące się w wierszach mają te same dwa pierwsze elementy. Różnią się i one tylko elementami stojącymi na ostatnim miejscu. Ponieważ elementy stojące na pierwszych dwu miejscach nie mogą się powtórzyć, więc w każdym wierszu znajduje się n—2 wariacji. Jak widać z zestawienia, w każdej kolumnie znajduje się n-{n— 1) wariacji. W całej piblicy znajduje się zatem V_a—n-(n—l)-(n—2) wariacji z n elementów po 3.

Rozważania podane w przykładzie 2.2.1 można uogólnić otrzymując twierdzenie Kastępujące:

| Twierdzenie 2.2.1. Liczba wariacji bez powtórzeń z n elementów po k (k^ń) wyraża pfg wzorem

12.2.1)    .    1^= n • (n -1) - (n -2) •... • (u -k +

| Indukcyjny dowód wzoru (2.2.1) znajdzie czytelnik w przykładzie 2.8.4.

E&Liczba wariacji V* jest równa liczbie sposobów, jakimi można pobrać z populacji l|eneralnej próbkę A"-elementową bez zwrotu przy kolejnym pobieraniu jej elementów, tzn. ■uwzględniającym porządek elementów w próbce. Zauważmy bowiem, że przy próbce bez zwrotu pierwszy element próbki może być wybrany n sposobami, drugi n— 1 sposobami, .... ostatni element próbki n—(k— 1) sposobami. Wobec tego liczba sposobów pobra-

KpP ,    n!

nia k elementów próbki jest równa n-(n— l)*(n—2)*...*(n—A:+1)=--

(n-kyl

Przykład 2.2.2. Ile można wykonać różnych trójkolorowych chorągiewek z sześciu ibarw?

Rozwiązanie. 1. Tworzymy zbiory trójelementowe ze zbioru 6-elementowego.

2. Kolejność układu barw w chorągwi odgrywa rolę, np. chorągiew biało-czerwona jest symbolem państwa polskiego, a chorągiew czerwono-biała jest symbolem księstwa jMonaco.

" 3. Chorągiewki mają być trójkolorowe, a więc w tworzonych zbiorach elementy, siłą rzeczy, nie mogą się powtarzać.