+ Pokaż spis treści

Kombinatoryka

Kombinatoryka i rachunek prawdopodobieństwa
[-]

Kombinatoryką nazywamy dział matematyki zajmujący się zbiorami skończonymi oraz odwzorowaniami między nimi. Kombinatoryka jest sztuką liczenia - zajmuje się wyznaczaniem liczby elementów zbiorów skończonych utworzonych zgodnie z określonymi zasadami. Powstała dzięki grom hazardowym, a swój rozwój zawdzięcza głównie rachunkowi prawdopodobieństwa, gdzie znajduje szerokie zastosowanie przy wyznaczaniu ilości zdarzeń elementarnych.

Przypomnienie

Najpierw przypomnimy pojęcia i oznaczenia, którymi posługuje się kombinatoryka.

Zbiór

       - oznacza zbiór o elementach . Kolejność wypisania elementów zbioru nie odgrywa roli. Dwa zbiory o takich samych elementach są równe.

Ciąg

       - oznacza ciąg o wyrazach . Kolejność ustawienia wyrazów w ciągu jest bardzo ważna. Zmieniając kolejność wyrazów w ciągu otrzymujemy inny ciąg.

Silnia

      Symbol - oznacza iloczyn kolejnych liczb naturalnych od 1 do n: , przy czym .

Symbol Newtona

      Symbol Newtona dla n, k Î N i k ? n - oznacza liczbę określoną wzorem: .

Własności symbolu Newtona.
  1. ,
  2. ,
  3. ,
  4. .

Kombinacje

-elementową kombinacją zbioru -elementowego   nazywamy każdy k-elementowy podzbiór zbioru .

Dwie kombinacje uważamy za różne, gdy jakiś element występuje w jednej z tych kombinacji, a nie występuje w drugiej.

Liczba -elementowych kombinacji zbioru -elementowego wyraża się wzorem:
.

Permutacje

Permutacją -elementowego zbioru  nazywamy każdy - wyrazowy ciąg utworzony ze wszystkich elementów zbioru , czyli każde ustawienie wszystkich jego elementów w dowolnej kolejności.

Dwie permutacje uważamy za różne, gdy przynajmniej dwa elementy występują w nich na różnych miejscach.

Liczba permutacji zbioru -elementowego wyraża się wzorem:
.

Wariacje bez powtórzeń

Każdy ciąg - wyrazowy o wyrazach ze zbioru - elementowego , przy czym każdy element zbioru  może wystąpić w ciągu co najwyżej raz, nazywamy - wyrazową wariacją bez powtórzeń - elementowego zbioru .

Liczba - wyrazowych wariacji bez powtórzeń zbioru - elementowego wyraża się wzorem:
.

-wyrazowe wariancje bez powtórzeń zbioru -elementowego są permutacjami tego zbioru. Zatem zachodzi zależność: .

Wariacje z powtórzeniami

Każdy ciąg - wyrazowy o wyrazach ze zbioru - elementowego , przy czym każdy element zbioru  może wystąpić w ciągu dowolną liczbę  razy,  nazywamy  - wyrazową wariancją z powtórzeniami - elementowego zbioru .

Liczba -wyrazowych wariacji z powtórzeniami zbioru - elementowego wyraża się wzorem: 


Reguła mnożenia

      Jeśli pewien wybór zależy od skończenie wielu decyzji, przy czym podejmując decyzję
      pierwszą mamy  możliwości,
      drugą -  możliwości, ...,
      .
      .
      .
      ostatnią -  możliwości,

to wybór ten może być zrobiony na:  sposobów.

Przykład 1:

Dany jest zbiór cyfr:
  1. Ile różnych liczb 9-cyfrowych można utworzyć z elementów tego zbioru?
  2. Ile liczb 4-cyfrowych o nie powtarzających się cyfrach można utworzyć z elementów tego zbioru?
  3. Ile liczb 4-cyfrowych można utworzyć z elementów tego zbioru?

Rozwiązanie:

  1. Każda liczba 9-cyfrowa jest pewnym ustawieniem elementów zbioru 9-elementowego, a więc jego permutacją.  Ilość wszystkich liczb 9-cyfrowych jest równa liczbie permutacji zbioru 9-elementowego, a więc



  2. Każda liczba 4-cyfrowa o nie powtarzających się cyfrach jest 4-wyrazową wariacją bez powtórzeń zbioru 9-elementowego, a więc ich ilość wynosi:

  3. Każda liczba 4-cyfrowa jest  4-wyrazową wariacją z powtórzeniami zbioru 9-elementowego, więc ich ilość wynosi:


Przykład 2:

Z ilu osób składa się klasa, jeśli wiadomo, że dwuosobową delegację można wybrać na 300 sposobów?

Rozwiązanie:

Każda dwuosobowa delegacja jest 2-elementową kombinacją zbioru -elementowego, gdzie  oznacza ilość uczniów w klasie. Wszystkich kombinacji 2-elementowych zbioru uczniów jest 300. Korzystając ze wzoru na ilość kombinacji można wyznaczyć liczbę uczniów:


Liczba  nie spełnia założeń zadania (liczba osób w klasie musi być dodatnia), więc jedynym rozwiązaniem jest .

Odp. W klasie jest 25 osób.

Przykład 3:

Z talii 52 kart losujemy 5 kart. Ile istnieje możliwych wyników losowania, w których wylosujemy 3 asy?

Rozwiązanie:

W talii są 4 asy, więc 3 asy można wylosować na sposobów.
Wśród pozostałych 2 kart nie może już być asa, zatem losujemy je z 48 kart (52karty - 4 asy). Można to zrobić na  sposobów.
Aby obliczyć na ile sposobów można wylosować 5 kart, wśród których są 3 asy skorzystamy z reguły mnożenia: ilość sposobów .
Odp. 5 kart, wśród których są 3 asy można wylosować na 4512 sposobów.