DSCF2509

42 2, Kombinstioryka

Przykład 2.6.3. Dana jest grupa elementów ABCD oraz grupa elementów x, y, z. Twarzymy kombinacje po pięć elementów w ten -sposób, że trzy elementy wybieramy z pier wszej grupy i dwa z drugiej grupy. Obliczyć, ile takich kombinacji można utworzyć, a następnie wypisać je.

Rozwiązanie. I) Z czterech elementów A, B, C, D można utworzyć Cl *4 kombinacje po trzy elementy.

2)    Z trzech elementów x, y, z można utworzyć C\**3 kombinacje po dwa elementy.

3)    Ponieważ każda kombinacja pierwszej grupy łączona jest z każdą kombinacją drugiej grupy, więc ogólna liczba kombinacji równa się iloczynowi ilości kombinacji pierwszej

grupy przez ilość drugiej:	C\C\	*12.
A oto rozważane kombinacje:
ABCxy	ABDxy	BCDxy	ACDxy
f ABCxz	ABDxz	BCDxz	ACDxz
1 ABCyz	ABDyz	BCDyz	ACDyz

y P^zjgŁAP Z6.4. Jloma sposobami można położyć 12 książek na trzech półkach tak, by na pientaSo^pSlce znajdowało się sześć książek, na drugiej cztery książki, a na trzeciej reszta?

Rozwiązanie. Przy układaniu książek nie zwracamy uwagi na ich sposób uporządko-wanta na półce, interesuje nas tylko to, by na każdej półce znajdowała się żądana ich ilość. Tekst zadania możemy interpretować jako pobieranie próbki bez zwrotu:

w pierwszym przypadku O półka) o liczności 6 elementów (książek) z populacji generalnej 12-elementowęj.:

w drugim przypadku (Xf półka) o Ikzności 4 elementów z populacji już tylko 12—6= =6-ełcmentowej (książki ułożone na ł półce nie mogą bowiem być układane na pozostałych);

w trzecim przypadku (III półka) o Ikzności 2 elementów z populacji ^-elementowej. W tym przypadku oczywiste jest, że będzie tylko jedna taka próbka. Na podstawie wzoru (2.6.1) ilość różnych próbek w przypadku pierwszym (ilość sposobów wybrania 6 książek spośród 12 na 1 półceywyrazi się liczbą C_f% w przypadku drugim liczbą C*, w przypadku trzecim liczbą Cf*l.

Do każdej 6-dementow ;i próbki z J Elementowej populacji pobieramy próbkę 4-ete-mentową z 6-t\emenUrwej populacji i próbkę 2-demerttową z populacji Elementowej. Wynika stad, że ilość wszystkich możliwych próbek wyrazi się zgodnie ze wzorem (2.6,2) iloczynem

Cf,' Ci' Cf * —— * 13 fc60,

^{,z 2} 61412?

Przekład 2.6.J, Przy grze w preferansa każdy z trzech graczy otrzymuje 10 kart. a dwie karty zostają do tzw, kujona lub banku. Iloma sposobami można rozdać karty graczom siedzącym na ustalonych miejscach?

Rozwiązanie. Dla określonych w zadaniu warunków W ma znaczenia, ■* kolejności gracz otrzymuje 10 kart, Pierwszemu %jwsw«' meto* nadać 10 kart spośród

M kart Q ftpmobami, dra*i*mu - Q tpo***™' ^1,“^c,emu >^tó •»*» C|«) W*⁰¹*""*

a rozdani* kart do „bank,/ może na^pid tytko w (₃)-»    Rd*ny«H MX«ob/«

rozdań kart jest przeto, zgodnie ze wzorem (2.6,2),

/»% /22| (n\

<to) łioj iio; 001^21

Żmudne rachunki dają wynik: 2 753 294 40fc 504 640. Unikamy ich sł/nojąc przybliżony wzór Siirlinga. Podstawiając dane do wzoru (IX2a) otrzymujemy:

32^f.W64i'32^Me"^,2f    (t0tf*20* 'Jtt*' l&*e~**,

skąd

32!    32^m

i&^f ?'

Logarytmując otrzymane wyrażenie ot ramujemy 2Ż505' 10* *, Błąd popełniony przy użyciu wzoru Stirfśnga i tablic logarytmicznych wynosi około J.S f%,

U waga. Jeżeli zmienić warunki zadania, dopuszczając jeszcze możbwość zmiany miejsc przez graczy po rozdaniu kart hib — co na jedno wychodzi - pemrot/m-ame tych samych układów kart wśród graczy, to wyżej podana liczba rozdań kart zwiększy .ile jeszcze X razy.

Przykład 2,6.6. Spośród członków sześciofj-sobowjch egzekutyw dwóch organ z;:cvi wybiera się wspólny komitet, składający się z czterech osób (po dwie osoby z każdej organizacji), Tak ukonstytuowany komitet wybiera spośród siebie przewodniczącego. Traku*' jąc komitety z różnymi przewodniczącymi jako różne, obliczyć, ile tych komitetów można otworzyć?

Rozwiązanie, Tworzymy pary spośród sześciu osób organizacji /U Wszystkich możliwych par jest tyle, ile jest kombinacp bez powtórzeń z sześcioekmentowtgo zbioru podstawowego po dwa elementy, tzn. C*—15,

Podobnie wszystkie możliwe pary z sześciu osób organizacji B wyznaczone ta przez C| kombinacji bez powtórzeń,

Każda para organizacji 4 może utworzyć z każdą parą organizacji B ,/tcroosohowe grupy. Można utworzyć (C«j² *225 takich grup.

Z kolei każdy z członków grupy czteroosobowej może być wybrany na przewodniczą* cego, tzn, że można otworzyć 4'225*900 różnych komitetów,

V Przykład 2,6,7,₇ Iloma sposobami można rozdzielić cztery różne .sagrody miedzy trzecK ^racowmk^wj jeżeli każdy z nich otrzyma co «iajmiwq jedną nagrodę?

Rozwiązanie. Zastrzeżenie, że każdy z pracowników otrzyma co ruąmmt) jedną nagrodę oznacza, że jeden z nich otrzyma dwie nagrody, a pozostali po jednej. Oznaczając