DSCF2503

28 2. Kombinatoryka

Z 1, 2, 3 wnioskujemy, że tyle jest różnych trójkolorowych chorągiewek, ile jest różnych wariacji bez powtórzeń z 6 elementów po 3, tj.

•, 6!

V\=--—=4-5*6=120.

(6-3)1

Przykład 2.2.3. Obliczyć, ile jest liczb czterocyfrowych, w których nie powtarza się żadna cyfra.

Rozwiązanie. Ilości liczb zaczynających się cyfrą 0, 1, 2, 3,..., 9 są równe, przeto chcąc otrzymać tylko te liczby czterocyfrowe o nie powtarzających się cyfrach, które nie zaczynają się zerem, musimy z otrzymanej liczby wariacji V*₀ odrzucić jej dziesiątą część. Liczb czterocyfrowych, o różnych cyfrach i pierwszej różnej od zera, jest zatem

Pio-ro*to-A*?o-4536.

Zadanie można rozwiązać rozumując również w sposób następujący:

Mamy do dyspozycji cyfry 0,1,2, ...,9. Cyfry te rozmieszczamy w określonym porządku na czterech miejscach, zważając tylko, by żadna z nich nie powtórzyła się w danym układzie czteroelementowym (w różnych układach mogą się, oczywiście, cyfry powtarzać). Wszystkich takich rozmieszczeń będzie    =7-8-9* 10=5040.

Wśród tych rozmieszczeń znajdą się i takie, które na pierwszym miejscu mają cyfrę zero. Jeśli na pierwszym miejscu układu czterocyfrowego umieścimy cyfrę zero, to na pozostałych trzech miejscach możemy rozmieszczać cyfry 1,2,3,.... 9 w dowolnym porządku. Tworzą one wariacje w ilości V$=7-8-9* =504. Szukana ilość liczb czterocyfrowych będzie zatem:

— V\~5040 — 504 =4536.

Przykład 2.2.4. Ile można utworzyć liczb parzystych czterocyfrowych o nic powtarzających się cyfrach i przy założeniu, że zero nie występuje na pierwszym miejscu'(tzn. na miejscu tysięcy)?

1	2	3	4	5	Rozwiązanie. Liczba jest parzysta, jeśli koń-
•	•	O	•	O	czy się cyfrą 0, 2, 4, 6, 8. Pozostałe dziewięć
A	B		C		cyfr rozmieszczamy na trzech pierwszych miej-
1	2	3	4	5	scach, co po uwzględnieniu porządku daje wariacje bez powtórzeń w liczbie

D    i

O -miejsce wolne miejsce zajęte

Rys. 2.2.1

W tej liczbie wariacji znajdują się przypadki z zerem na początku. Wówczas dwa środkowe miejsca może zajmować tylko 8 cyfr, gdyż cyfry na pierwszym i ostatnim miejscu są już ustalone. Sytuacja ta zachodzi tylko w czterech przypadkach, tzn., gdy zero jest na początku. Tę liczbę 4V} wariacji należy odjąć od poprzedniej. Otrzymujemy wynik 5Po-4Pg >2296.

Przykład 2.2.5. W przedziale wagonu są ustawione naprzeciw siebie dwie ławki mające po 5 numerowanych miejsc od 1 do 5, Na ławce I siedzą trzy osoby oznaczone literami

§ 2.2. Wariacje bez powtórzeń

29

A, B, C, a na ławce II siedzą dwie osoby D, E (rys. 2.2.1). Iloma różnymi sposobami mogą usiąść pasażerowie, tak aby zawsze dwie osoby siedziały naprzeciw dwu osób?

I Rozwiązanie. Trzy osoby A, B, C mogą usiąść na 5 numerowanych miejscach tyloma Sposobami, ile jest różnych wariacji bez powtórzeń z 5 elementów po 3 (1. jednocześnie |iMc osoby nie mogą siedzieć na tym samym krześle, 2. uporządkowanie odgrywa tutaj jfolę), tzn. mogą usiąść = 60 sposobami.

||| Do każdego ustawienia na ławce I istnieje tyle ustawień na ławce II takich, aby 2 osoby wiedziały naprzeciw dwu osób, ile jest różnych wariacji bez powtórzeń z 3 elementów po 2 (do trzech osób na ławce I ustawiamy odpowiednio 2 osoby na ławce II), a zatem

Ih>=6.

B Ponieważ różnych rozmieszczeń 3 osób na I ławce było i do każdego takiego rozmieszczenia można było dobrać V\ różnych rozmieszczeń 2 osób siedzących naprzeciw na drugiej ławce, więc ilość wszystkich możliwych rozmieszczeń spełniających warunki badania wyrazi się iloczynem V\■ V*=360.

§ 2.3. Wariacje z powtórzeniami

[ Definicja 2.3.1. Wariacją (rozmieszczeniem) z powtórzeniami z n elementów po k nazywamy uporządkowany zbiór składający się z k elementów różnych lub nie różnią-fbych się między sobą, wybranych spośród n różnych elementów.

R Liczbę-wariacji z powtórzeniami z n różnych elementów po k oznaczamy symbolem V*. 8 Wariację z powtórzeniami z n elementów po k można interpretować jako próbkę K-elemcntową pobraną zc zwracaniem z populacji generalnej n-elementowcj. f Mpże się zdarzyć, że w skład próby wchodzą jednakowe elementy. Próby uważamy pzailiróżne, jeśli różnią się składem lub porządkiem elementów.

Pz populacji generalnej /i-clemcntowej można pobrać pierwszy element próby k-Kcmcntowej n sposobami, gdyż każdy z elementów populacji może być wybranym ele-pientem. Po wylosowaniu pierwszego elementu próby zwracamy go do populacji i losujemy ponownie. Ten element, jak poprzednio, może być wybrany również n sposobami, po samo da się powiedzieć o każdym następnym elemencie próby, aż do k-tego elementu włącznie. Ostatecznie otrzymujemy, że w k losowaniach według przyjętej umowy otrzymujemy

fe.3.1)    pj~n^fc

Późnych układów. Dowód indukcyjny wzoru (2.3.1) podajemy w przykładzie 2.8.3.

1 Przykład 2.3.1. Z n elementów a_]ta₂,a_it..., a„ można utworzyć następujące wa-ffiacje z powtórzeniami z n elementów po 2.

	^al ^a2	f i l Cl 3	a jd,
fl2«,	a 2 Cl 2	a2a3 ..
a3at	Cl 2 Cl 2	«a % ■>-	,, a3a,
	' an a 2	a„a3 .	.. ana,

W każdym wierszu i w każdej kolumnie znajduje się n wariacji, czyli ogółem //.*« -w//² możliwych wariacji, co jest zgodne z podanym wzorem (2.3.1).