DSCF2504

30 2. Kombinaioryka

Przykład 2.3.2. He można utworzyć liczb pięciocyftowych z cyfr 4, 5, 6? Rozwiązanie.

1.    Tworzymy zbiory 5-ełementowe ze zbioru trójelementowego.

2.    W tworzonych zbiorach kolejność odgrywa rolę (liczby są uporządkowanymi zbiorami cyfr).

3.    Cyfry w danej liczbie mogą się powtarzać.

Z 1.2,3 wnioskujemy, że tyle jest różnych liczb pięciocyfrowych, ile jest różnych w ariacji z powtórzeniami z trzech elementów po 5; zatem Ff=3⁵=243.

Przykład 23.3. W wyrażeniu a*=c w miejsce liter a, b, c podstawiamy liczby wymierne lub niewymierne. Oznaczając liczby wymierne literą w, a niewymierne literą n, obliczyć, iloma sposobami możemy to uczynić i sprawdzić, czy wszystkie przypadki są możliwe.

Rozw iązanie. Zgodnie ze wzorem (23.1) otrzymujemy liczbę przypadków równą Vz =2³=8. Mamy mianowicie:

1- *-^w=w, 2. w*=n, 3. w*=w, 4. yę*=n,

5. n^v=w,    6. n*=ii.    7. n*=w,    8. n^m=n.

Podajemy przykłady na poszczególne przypadki:

1. 2²=4.    2. 2*=^2,    3. 10*^s2=2,    4. ł0^1§e=e,

5. (_n/2)²=2, 6. (y2)³=2_N/2,    7. e^h,2=2,    8.

* Przykład ^24. Sześć osób ma do dyspozycji 5 różnokolorowych kieliszków' i 2 różne gatunki win. Iloma sposobami mogą się napić?

£

C3

Rozwiązanie. Obliczamy najpierw ilość sposobów rozmieszczenia 5 kieliszków na stole, przy którym siedzi 6 osób (rys. 23.1). Ponieważ kieliszki są różnokolorowe i jednej osobie dajemy nie więcej niż jeden kieliszek (zawsze jedna osoba pozostaje bez kieliszka), to ilość sposobów rozmieszczenia kieliszków na stole jest równa F$ =720.

Przy każdym ustawieniu 5 kieliszków można do nich nalać dwa gatunki win tyloma sposobami, ile jest wariacji z powtórzeniami z 2 elementów po 5. bowiem:

1.    ten sam gatunek wina z konieczności (są tylko 2 gatunki) powtórzy się w różnych kieliszkach,

2.    jest istotne, jakie wino do jakiego kieliszka jest nalewane, tzn. nie można brać pod uwagę tylko liczby kieliszków napełnionych danym gatunkiem wina.

Ponieważ przy każdym układzie kieliszków istnieją F|=2⁵=32 sposoby nalania do nich wina, więc ogółem istnieje F|* F| =23040 sposobów spełniających warunki zadania.

|Hrzykład 2.3.5. Alfabet Morse’a składa się z dwóch różnych elementów: kreski ^npki. He znaków pisarskich można utworzyć z tych elementów, jeśli każdy znak nie Ipei posiadać więcej niż k miejsc oznaczonych kreskami lub kropkami? De znaków mcfcna Stworzyć, gdy A:=5?

■Rozwiązanie. Znak pisarski składający się co najwyżej z k znaków (kropka, kreska) uzyskuje się przez jednokrotne, dwukrotne, .... fc-krotne użycie kreski lub kropki w okreś-Hyni porządku. Znaczy to, że tworzymy zbiory /-elementowe (1^/^fc) ze zbioru podstawowego dwuelementowego, tj. z kropki i kieski. Ponieważ znaki w tworzonym zbiorze Hementowym mogą się powtarzać i kolejność ich odgrywa rolę, otrzymujemy, że jest kłl tyle, ile jest wariacji z powtórzeniami, tzn. 2\ Wszystkich znaków pisarskich jest Hem

S*= £

1=4

Stosując wzór na sumę wyrazów postępu geometrycznego otrzymujemy S_fc=2-(2*—S fi), tj. w szczególności S_s=62.

I Przykład 2.3.6. Centrala telefoniczna pracuje na połączeniach pięciocyfrowych, óre uzyskuje z cyfr 0, 1,2, ...,9. Du abonentów może centrala zarejestrować, jeśli włączenia pięci ocyfro we, zaczynające się od zera, nie moa być brane pod uwagę, a pocenia dwucyfrowe z zerem na początku są przewidziane dla straży pożarnej, centrali jędzymiastowej itp.?

Rozwiązanie. Tworzymy zbiory pięcioelementowe (pięciocyfrowe numery telefo-J5w^r) z elementów⁷ zbioru dziesięcioelementowego (cyfry), w których kolejność występowania elementów⁷ odgrywa rolę i w których elementy mogą się powtarzać. Dości numerów tefonów. zaczynających się cyframi 0,1,2,...,9 są równe, przeto chcąc otrzymać lko te liczby pięciocyfrowe, które nie zaczynają się zerem, musimy od otrzymanej liczby rariacji V^₀ odjąć jej dziesiątą część. Liczb pięciocyfrowych o pierwszej cyfrze różnej >d zera jest zatem:

«'fo-re»^/?o=^»'.⁵=90000.

W Poza tym przewidziano 10 połączeń: 00,01,02, ...,09.

Centrala może zatem zarejestrować łącznie 90010 abonentów, k/Przykład 2.3.7. De można utworzyć liczb czterocyfrowych, w których na pierwszym Ina ostatnim miejscu występuje ta sama cyfra i w których cyfry mogą się powtarzać? f Rozwiązanie. Przy ustalonej na pierwszym i ostatnim miejscu cyfrze, pozycje drugą Ktrzecią mogą zajmować dowolne z cyfr 0, 1,2,..., 9. Ponieważ cyfr ty ch jest 10. a miejsc |ł i cyfry mogą się na tych miejscach powtarzać, otrzymujemy wariacje z powtórzeniami. Których według wzoru (2.3.1) jest 10²= 100.

Dość liczb, spełniających warunki zadania jest dziewięciokrotnie większa, gdyż pierwsze » ostatnie miejsce mogą zajmować dowolne z cyfr od 1 do 9. (Zero na pierwszym miejscu piiie może występować, gdyż wówczas liczba nie byłaby czterocyfrowa).