kombinatoryka

Matematyka - Kombinatoryka

      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. ,
   
5. .

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.