1 KOMBINATORYKA

2 Treść wykładu Wprowadzenie Permutacje Kombinacje WariacjeBez powtórzeń Z powtórzeniami Kombinacje Wariacje Zalecana literatura

3 Wprowadzenie Kombinatoryka to teoria obliczania liczby elementów zbiorów skończonych. Powstała dzięki grom hazardowym, a swój rozwój zawdzięcza rachunkowi prawdopodobieństwa, teorii grafów, teorii informacji i innym działom matematyki stosowanej. Stanowi jeden z działów matematyki dyskretnej. Kombinatoryka posługuje się terminologią nie występującą w innych działach matematyki, stąd pozorna jej odrębność. Najważniejszym jej zadaniem jest konstruowanie spełniających pewne określone warunki odwzorowań jednego zbioru skończonego w drugi oraz znajdowanie wzorów na liczbę tych odwzorowań.

4 Permutacje bez powtórzeńPermutacja jest szczególnym przypadkiem wariacji bez powtórzeń. Definicja: Permutacją bez powtórzeń zbioru złożonego z n różnych elementów nazywamy każdy n wyrazowy ciąg utworzony ze wszystkich wyrazów zbioru. Wszystkich możliwych permutacji zbioru n-elementowego jest: Pn = n! Przykład: Elementy zbioru A = {a,b,c} można ustawić w ciąg na P3 = 3! = 6 sposobów: abc, acb, bac, bca, cab, cba. Wyjaśnienie: W każdej z permutacji mamy do zapełnienia trzy wolne miejsca. W pierwszym z nich możemy umieścić dowolną z liter na trzy sposoby (Pn = 3 * …), na drugim dowolną spośród pozostałych jeszcze dwóch liter na dwa sposoby (Pn = 3 * 2 * …), itd. Na ostatnim miejscu musi znaleźć się ostatnia dostępna litera (element zbioru), a zatem możemy to zrobić tylko na jeden sposób. Ostatecznie otrzymujemy: Pn = 3 * 2 * 1 = 3!

5 Permutacje z powtórzeniamiNiech A oznacza zbiór złożony z k różnych elementów A = {a1, a2, …, ak}. Permutacją n elementową z powtórzeniami, w której elementy a1, a2, …, ak powtarzają się odpowiednio n1, n2, …, nk razy, n1 + n2 + … + nk = n, jest każdy n-wyrazowy ciąg, w którym elementy a1, a2, …, ak powtarzają się podaną liczbę razy. Liczba takich permutacji z powtórzeniami wynosi n!/(n1! * n2! * … * n3!). Przykład: Przestawiając litery b, a, b, k, a można otrzymać 5!/(2! * 2! * 1!) różnych napisów. Wyjaśnienie: "Zwykłe" przestawianie liter w słowie babka spowoduje kilkukrotne powstanie identycznych wyrazów, np. zamieniając miejscami pierwszą i trzecią literę znów otrzymamy słowo babka. Należy to uwzględnić przy zliczaniu, dlatego rezultat trzeba podzielić każdorazowo przez liczbę "zbędnych" permutacji, które nie prowadzą do powstania nowych słów (ciągów uporządkowanych). Spostrzeżenie: Można wobec tego zapisać wzór na permutację bez powtórzeń następująco: Pn = n! = n!/(1! * 1! * … * 1!) (każdy z elementów występuje dokładnie raz).

6 Kombinacje bez powtórzeńKombinacja bez powtórzeń to każdy podzbiór zbioru skończonego, poza zbiorem pustym. Kombinacją k- elementową zbioru n-elementowego A nazywa się każdy k-elementowy podzbiór zbioru A (0 ≤ k ≤ n). Używa się też terminu "kombinacja z n elementów po k elementów" lub wręcz "kombinacja z n po k". Dopełnieniem kombinacji z n po k jest kombinacja z n po n−k. Liczba kombinacji z n po k wyraża się wzorem: Liczba kombinacji 2-elementowych zbioru 4- elementowego A={a, b, c, d} jest równa 4!/(2!*2!) = (1*2*3*4)/(2*2) = 6. Kombinacjami są podzbiory: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}. Prawdopodobieństwo trafienia "szóstki", tj. wszystkich liczb podczas losowania Lotto (wszystkich 6 z 49) wynosi

7 Kombinacje z powtórzeniamiKombinacja z powtórzeniami (pojęcie matematyczne), to każdy multizbiór którego elementami są elementy pewnego zbioru skończonego. k-elementową kombinacją z powtórzeniami zbioru n-elementowego A nazywa się każdy k-elementowy multizbiór składający się z elementów zbioru A. W odróżnieniu od kombinacji bez powtórzeń tu elementy mogą się powtarzać. Liczba k-elementowych kombinacji z powtórzeniami zbioru n-elementowego wyraża się wzorem: Liczba kombinacji 2-elementowych z powtórzeniami zbioru 4-elementowego A = {a, b, c, d} jest równa 5!/(2!*3!) = 120/12 = 10. Można je wymienić: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a,a}, {b,b}, {c,c}, {d,d}. Kolejność nie ma tutaj znaczenia, równie dobrze można napisać {c,d}, jak {d,c}.

8 Wariacje bez powtórzeńWariacją bez powtórzeń k-wyrazową zbioru n-elementowego A (1 ≤ k ≤ n) nazywa się każdy k-wyrazowy ciąg różnych elementów z tego n-elementowego zbioru (kolejność tych elementów ma znaczenie). Gdy k=n, wariację bez powtórzeń nazywa się permutacją. Liczba wszystkich k-wyrazowych wariacji bez powtórzeń zbioru n-elementowego wyraża się wzorem: Każda k-wyrazowa wariacja bez powtórzeń zbioru n- elementowego jest funkcją różnowartościową, ze zbioru k- elementowego do zbioru n-elementowgo. Na kalkulatorach liczbę wszystkich wariacji bez powtórzeń ze zbioru r- elementowego do zbioru n-elementowego wyraża się znakiem nPr. Z cyfr 1, 2, 3, 4, 5 można utworzyć 5!/(5-3)! = 60 liczb trzycyfrowych o różnej kolejności cyfr.

9 Wariacje z powtórzeniamiWariacją z powtórzeniami k-wyrazową zbioru n- elementowego A nazywa się k-wyrazowy ciąg elementów tego zbioru (dowolny element może wystąpić wielokrotnie w ciągu). Należy zauważyć, iż kolejność elementów ma znaczenie. Liczba wszystkich k-wyrazowych wariacji z możliwymi powtórzeniami zbioru n-elementowego jest równa Każda wariacja jest funkcją ze zbioru k- elementowego do zbioru n-elementowego. Funkcje na ogół nie są różnowartościowe. Powtórzenia mogą wystąpić, ale nie muszą. Za pomocą cyfr 1, 2, 3, 4, 5 można zapisać 5^2=25 liczb dwucyfrowych (niekoniecznie różnocyfrowych).

10 Zalecana literatura Plucińska Agnieszka, Pluciński Edmund, Probabilistyka Rachunek prawdopodobieństwa, statystyka matematyczna, procesy stochastyczne, WNT 2006 Cieciura Marek, Zacharski Janusz, Podstawy probabilistyki z przykładami zastosowań w informatyce, Warszawa 2011 Gersternkorn Tadeusz, Kombinatoryka i rachunek prawdopodobieństwa, PWN 1979 Feller William, Wstęp do rachunku prawdopodobieństwa, PWN 2007 Ostasiewicz Walenty, Myślenie statystyczne, Wolters Kluwer 2012