DSCF2505

32    ^iV    ) •< > -    2. Kombinatoryka _ .

\/ Przykład 23.8_; ^Ile można utworzyć liczb parzystych czterocyfrowych takich, że cyfra zero nie występuje na pierwszym miejscu oraz cyfry w danej liczbie mogą się powtarzać?

Rozwiązanie. Wszystkich liczb czterocyfrowych takich, że cyfry mogą się powtarzać, jest tyle, ile jest wariacji z powtórzeniami z 10 elementów po 4:

Pto=10⁴.

Ilość liczb o powtarzających się cyfrach i nie posiadających cyfry 0 na pierwszym' miejscu jest następująca

15^10—9000.

Parzystych liczb jest połowa tej ilości, tj. 4500.

§ 2.4. Permutacje bez powtórzeń

Definicja 2.4.1. Zbiór składający się z n elementów uporządkowanych i różnych nazywamy permutacją (przemianą) bez powtórzeń z n elementów. liczbę utworzonych w ten sposób zbiorów oznaczamy symbolem P_n.

Pennutując ustawiamy wszystkie elementy zbioru różnoelementowego w określonym porządku. Wynika z tego, że dwie permutacje tego samego zbioru elementów różnią się między sobą tylko kolejnością elementów. Permutacja jest więc wariacją z n elementów po n. Liczba permutacji wyraża się zatem wzorem

(2.4.1)    p„=P2=n*(n- l)*(n-2)-... -3-2; l=n!y

Dowód indukcyjny wzoru (2.4.1) znajdzie czytelnik w przykładzie 2.8.6.

Elementy permutacji oznaczamy symbolami

Oi,a₂,a_3j..._ia_k,a_k+ll... ,a_n lub niekiedy dla uproszczenia zapisu wprost

1,2,3,...,fc,fc-f 1, ...,n.

Przykład 2.4.1. Istnieją dwie permutacje z elementów a_t, a₂:

Istnieje sześć permutacji z trzech elementów a_ki a₂, a₃:

CŁ i #2 ^3 i ^1^3 ^2 ’	a2a1a3,	a2 a3 Aj,		a3aia2, a3a2a1.
Istnieją 24=4! permutacje z 4 elementów wskaźników:		<*2, a3)		a4. Podajemy permutacje samych
12 3 4	2 13 4	3 12 4		4 12 3
12 4 3	2 14 3	3 1	4 2	4 13 2
13 2 4	2 3 14	3 2	1 4	4 2 13
13 4 2	2 3 4 1	3 2 4 1		4 2 3 1
14 2 3	2 4 13	3 4	1 2	4 3 12

§ 2.4. Permutacje bez powtórzeń    33

W powyższym przykładzie pogrupowaliśmy elementy w fen sposób, by każda grupa rozpoczynała się tym samym elementem. W przypadku 5 elementów a,, a₂, %, a*, a_s można utworzyć 5 różnych grup, rlo których zaliczy się permutacje o tym samym pierwszym elemencie. Wówczas, poza elementem początkowym, pozostają jeszcze 4 elementy, które można w wyżej wskazany sposób permutować na 24 sposoby. Wynika z tego, że w tym przypadku będziemy mieli 5*4!=5! =120 permutacji. Dla przykładu przytaczamy trzecią grupę permutacji (wskaźników):

3 ]	L 2 4 5	3 2 1 4 5	3 4 12 5	3	5 12 4
3 ]	L -2 5 4	3 2 1 5 4	3 4 15 2	3	5 14 2
3 1	14 2 5	3 2 4 1 5	3 4-2 15	3	5 2 14
.3 ]	14 5 2	3 2 4 5 1	3 4 2 5 1	3	5 2 4 1
3 i	152 4	3 2 5 1 4	3 4 5 1 2	3	5 4 12
3 3	15 4 2	3 2 5 4 1	3 4 5 2.1	3	5 4 2 1

Permutację bez powtórzeń z n elementów można interpretować jako próbkę n-ele-mentową pobraną bez zwrotu z populacji generalnej n-elementowej z zaznaczeniem kolejności pobieranych elementów.

Przykład 2.4.2. W urnie są 3 kule o numerach 1,2, 3. Wyciągamy kolejno trzy kule i notujemy ich numery według kolejności wyciągnięcia. Ile można tym sposobem otrzymać różnych liczb?

Rozwiązanie. Tworzone z poukładanych kolejno kul liczby trzycyfrowe traktujemy jako próbki pobrane z populacji 3-elementowej. Ilość różnych, w ten sposób otrzymanych liczb, jest równa ilości permutacji z 3 elementów, a więc

P₃=3!=6.

Przykład 2.4.3. Iloma sposobami można umieścić pięć osób na pięciu numerowanych krzesłach?

Rozwiązanie. 1. Tworzymy zbiory pięcioelementowe ze zbioru pięcioelemento-wego.

2. W utworzonych zbiorach kolejność odgrywa rolę, gdyż krzesła są numerowane. m’3. Z założenia zbiory są różnoelementowe (jedna i ta sama osoba nie może siedzieć [na dwóch krzesłach).

KvZ 1,2,3 wnioskujemy, że osoby można rozmieścić tyloma sposobami, ile jest permutacji z elementów bez powtórzeń, czyli

Ps^S 1=120.

■EPrzykład 2.4.4. Ile jest permutacji liczb 1,2,w których [I) Eczby 1, 2 nie sąsiadują ze sobą;

2) Eczby 1, 2, 3 nie tworzą trzech kolejnych wyrazów (niezależnie od porządku)? ^Rozwiązanie. 1) Ilość wszystkich możliwych permutacji z n elementów

P_n=n\.

omblnatoryka ...