Elementy kombinatoryki

Kombinatoryka to dział matematyki, który zajmuje się obliczaniem liczby różnych połączeń z elementów danego zbioru skończonego (lub nieskończonego, ale policzalnego). Co ciekawe, pierwotnie kombinatoryka powstała na potrzeby gier hazardowych jako narzędzie do obliczania szansy na wygraną lub przegraną. Z metod kombinatoryki korzystają inne dziedziny matematyki, z resztą bardzo ważne nie tylko same w sobie, ale również dla rozwoju nowoczesnych technologii: rachunek prawdopodobieństwa i statystyka, teoria grafów, teoria informacji, teoria gier. Jeśli interesujesz się robotyką, informatyką, zastosowaniem sztucznej inteligencji, to prawdopodobnie poznasz wiele zagadnień z powyższych dziedzin.

W kombinatoryce wyróżnia się trzy podstawowe połączenia (odwzorowania):

  • permutacje (przemieszczenia),
  • wariacje (rozmieszczenia),
  • kombinacje.

Ponadto każde z powyższych połączeń może występować w wersji bez powtórzeń i z powtórzeniami. Przyjrzyjmy się po kolei wszystkim wariantom.

W przypadku pytań, wątpliwości i uwag związanych z przedmiotem tego artykułu i funkcjami w języku Python, proszę zamieszczać odpowiednie komentarze za pośrednictwem formularza na końcu strony.

Permutacje bez powtórzeń

Permutacją bez powtórzeń jest każdy ciąg złożony ze wszystkich i różnych elementów danego zbioru. Na przykład mając do dyspozycji zbiór pięciu liter \(\{a, b, c, d, e\}\), permutacjami są następujące ciągi: bacde, dbace, abcde. Nie są permutacjami ciągi: acd, bbdec. Dlaczego?

Nasuwa się pytanie, ile takich permutacji bez powtórzeń można ułożyć? Biorąc powyższy przykład widać, że wybierając element zbioru dla pierwszej pozycji mamy do dyspozycji 5 możliwości. Dla drugiej pozycji pozostają nam 4 możliwości, dla trzeciej – 3 możliwości, dla czwartej 2 możliwości, i w końcu dla piątej pozostaje nam tylko jedna. Z tego wynika, że liczbą wszystkich permutacji bez powtórzeń powyższego zbioru jest iloczyn \(5 * 4 * 3 * 2 * 1\). Ile on wynosi?

I tutaj wprowadzimy definicję silni, która jest szeroko wykorzystywana w wielu działach matematyki. Polecam sprawdzić! Silnia liczby całkowitej n, większej od zera, to iloczyn wszystkich liczb całkowitych poczynając od 1, a kończąc na n, przy czym zero silnia równa się 1. Ten iloczyn zapisujemy \(n!\). Oznaczenie to zostało wprowadzone przez francuskiego matematyka Christiana Krampa w 1808 r., a czytamy je “n silnia”.

Mała dygresja. Istnieje uogólnienie silni na liczby rzeczywiste i zespolone, a jest nim funkcja gamma.

Wracając do permutacji bez powtórzeń, widzimy, że ich liczba dla zbioru 5 – elementowego z naszego przykładu wynosi \(5!\), czyli, jak jeszcze w tym przypadku łatwo obliczyć, \(120\). Jednak do znajdowania liczby permutacji na zbiorach znacznie większych, warto wykorzystać komputer i można powiedzieć “matematyczny” 😉 język programowania Python.

Ogólny wzór na liczbę permutacji na zbiorze n – elementowym: \(P_{n} = n!\). Poniżej znajduje się przykład implementacji funkcji obliczającej silnię, więc ile różnych permutacji bez powtórzeń można utworzyć ze zbioru liter alfabetu języka polskiego?

""" n! dla n całkowitych i większych lub równych 0 """
def silnia(n):
    assert(n >= 0)
    wynik = 1
    while n > 1:
        wynik *= n n -= 1
    return wynik

""" Liczba permutacji bez powtórzeń na zbiorze n - elementowym """
def liczba_perm(n):
    return silnia(n)

Permutacje z powtórzeniami

W tworzeniu permutacji z powtórzeniami zakłada się, że poszczególne elementy zbioru mogą powtarzać się. W zasadzie permutacje tego typu są uogólnieniem permutacji bez powtórzeń, w których zakłada się, że każdy element zbioru występuje dokładnie raz.

Weźmy przykład, wyraz “mamałyga”. Zbiór liter składający się na niego to \(\{a, a, a, g, l, m, m, y\}\) (wielokrotne podanie takich samych liter w tym zbiorze służy jedynie zaznaczeniu, że niektóre jego elementy powtarzają się; zbiór ten jest równoważny zbiorowi \(\{a, g, l, m, y\}\)). Litera ‘a’ powtarza się 3 razy, ‘m’ powtarza się 2 razy, natomiast reszta liter po razie. Zadanie polega na obliczeniu ile różnych wyrazów, niekoniecznie mających znaczenie w języku polskim, można ułożyć przestawiając litery w powyższym wyrazie lub innymi słowy, ile jest różnych permutacji z powtórzeniami podanego zbioru liter?

Stosując wcześniej poznany wzór \(n!\) otrzymamy liczbę zbyt dużą, ponieważ niektóre permutacje będą nieodróżnialne, ze względu na to, że litery powtarzają się. Dlatego należy od uzyskanego wyniku odjąć liczbę permutacji powtarzających się. Jak to zrobić? Element ‘a’ występuje w zbiorze 3 razy, więc za jego pomocą możemy stworzyć \(3!\) nieodróżnialnych 3 – elementowych permutacji. Element ‘m’ występuje w zbiorze 2 razy i za jego pomocą możemy stworzyć \(2!\) nieodróżnialnych 2 – elementowych permutacji.

Intuicja podpowiada, że liczbę permutacji z powtórzeniami uzyskamy dzieląc liczbę uzyskaną ze wzoru na permutacje bez powtórzeń przez iloczyn liczb nieodróżnialnych przestawień (permutacji) poszczególnych powtarzających się elementów zbioru. W naszym przykładzie będzie \(\frac{8!}{3!*1!*1!*2!*1!}\) permutacji z powtórzeniami.

Możemy teraz napisać ogólny wzór na liczbę permutacji z powtórzeniami. Przyjmijmy, że n to liczba elementów zbioru, \(n_1, n_2, …, n_k\) to krotności występowania elementów w zbiorze. Trzeba tutaj zauważyć, że \(n_1 + n_2 + … + n_k = n\). Równanie to bardziej elegancko zapiszemy w następujący sposób: \(\sum_{i=1}^{i=k}{n_i} = n\)Wzór na liczbę permutacji z powtórzeniami przyjmie postać: \(\frac{n!}{n_{1}! * n_{2}! * … * n_{k}!}\). A poniżej implementacja w Pythonie funkcji, która oblicza liczbę permutacji z powtórzeniami, przy zadanej krotności występowania poszczególnych elementów. Ile wynosi liczba permutacji z powtórzeniami dla przytoczonego przykładu?

"""
Liczba permutacji z powtórzeniami dla zadanych krotności powtórzeń
poszczególnych elementów zbioru.
Przykład wywołania: liczba_perm_powt((3, 1, 1, 2, 1))
"""
def liczba_perm_powt(powtorzenia):
    wynik = 1
    for el in powtorzenia:
        if el > 1:
            wynik *= silnia(el)
    return silnia(sum(powtorzenia)) / wynik

Wariacje bez powtórzeń

A co jeśli chcemy wiedzieć, ile możemy zbudować ciągów wybierając nie wszystkie elementy z danego zbioru? Taki ciąg nazywa się wariacją. Zauważmy, że każda permutacja bez powtórzeń jest wariacją bez powtórzeń, która uwzględnia wszystkie elementy danego zbioru, na którym ją tworzymy.

Załóżmy, że mamy zbiór n – elementowy. Wtedy liczba k – elementowych wariacji na tym zbiorze wyraża się wzorem: \(V^{k}_{n} = n * (n-1) * (n – 2) * … * (n – k + 1)\)Jest to intuicyjny wzór, ponieważ postępując jak w przypadku permutacji bez powtórzeń, przy wyborze elementu na kolejne pozycje danej wariacji mamy za każdym razem wybór ograniczony o jeden element. Wyboru na pierwszą pozycję dokonujemy ze zbioru n elementów, a na ostatnią ze zbioru (n – k +1) elementów.

Łatwo sprawdzić, że powyższy iloczyn można wyrazić w następujący sposób: \(V^{k}_{n} = \frac{n!}{(n – k)!}\). Jakiego typu zadania możemy rozwiązać za pomocą powyższego wzoru? Na przykład: ile różnych liczb 4 – cyfrowych uda się ułożyć z użyciem 8 cyfr, przy czym cyfry nie powtarzają się? Załóżmy, że wszystkie cyfry są różne od zera. Dlaczego robimy takie założenie? A jaki wynik uzyskamy, jeśli dopuścimy zero w naszym zbiorze cyfr?

W obliczeniach pomoże poniższa funkcja w języku Python.

"""
Liczba wariacji bez powtórzeń k - elementowych na zbiorze n - elementowym,
przy czym k musi być mniejsze lub równe n
"""
def liczba_war(n, k):
    assert(k <= n)
    wynik = 1
    for el in range(n - k + 1, n + 1):
        wynik *= el
    return wynik

Wariacje z powtórzeniami

W poprzednim przykładzie założyliśmy, że cyfry w liczbie nie mogą się powtarzać. Jeśli postawimy pytanie następujące: ile liczb 4 – cyfrowych można ułożyć mając zbiór 8 cyfr (dla uproszczenia znowu przyjmijmy, że bez zera), przy czym każdą cyfrę możemy użyć dowolną liczbę razy, to mamy do czynienia z obliczeniem liczby wariacji z powtórzeniami.

Teraz na każdą pozycję liczby wybieramy za każdym razem cyfrę ze zbioru 8 – elementowego, więc odpowiedzią na powyższe pytanie jest iloczyn \(8 * 8 * 8 * 8\). Warto zauważyć, że możemy również postawić pytanie: ile liczb 8 cyfrowych można ułożyć mając zbiór 4 cyfr. Dlaczego nie mogliśmy zadać podobnego pytania w przypadku poszukiwania liczby wariacji bez powtórzeń?

Ogólny wzór na liczbę k – elementowych wariacji z powtórzeniami ze zbioru n – elementowego zapisujemy następująco: \(\overline{V}^{k}_{n} = n^{k}\)Zapis odpowiedniej funkcji w Pythonie jest prosty z wykorzystaniem wbudowanej funkcji potęgowania pow.

"""
Liczba wariacji z powtórzeniami k - elementowych ze zbioru n - elementowego
"""
def liczba_war_powt(n, k):
    return pow(n, k)

Kombinacje bez powtórzeń

W permutacjach i wariacjach jest istotna kolejność występujących w nich elementów, np. \(abcde \neq bacde\). Jednak czasami interesuje nas liczba różnych, jednoczesnych wystąpień pewnej liczby elementów z danego zbioru. Klasyczny przykład stanowi obliczenie liczby szóstek ze zbioru 49 liczb w grze Lotto. Nie interesuje nas kolejność wylosowania liczb, ponieważ nie ma ona znaczenia. Innymi słowy liczba k – elementów kombinacji bez powtórzeń ze zbioru n – elementowego jest równa liczbie k – elementowych podzbiorów tego n – elementowego zbioru. Pojęcie podzbioru należy rozumieć zgodnie z intuicją. Podzbiór B danego zbioru A jest zbiorem elementów, które należą do zbioru A (mogą to być również wszystkie elementy i wtedy oba zbiory są równoważne).

Zauważmy, że liczbę k – elementowych kombinacji bez powtórzeń zbioru n – elementowego uzyskamy po podzieleniu liczby k – elementowych wariacji tego zbioru, przez liczbę wszystkich permutacji zbioru k – elementowego. Wykorzystamy tę obserwację przy w implementacji odpowiedniej funkcji w Pythonie.

Liczbę kombinacji bez powtórzeń można obliczyć za pomocą tzw. symbolu Newtona: \(C^{k}_{n} = \binom{n}{k} = \frac{n!}{k! * (n – k)!}\). Na marginesie, symbolu Newtona używa się do obliczania kolejnych czynników tzw. dwumianu Newtona, czyli wielomianu o postaci: \((x + y)^n\).

"""
Liczba kombinacji bez powtórzeń k - elementowych zbioru n - elementowego
"""
def liczba_komb(n, k):
    return liczba_war(n, k) / silnia(k)

Kombinacje z powtórzeniami

Zacznijmy od przykładu. Ile jest możliwych wyników rzutu czterema standardowymi kostkami do gry, przy czym wynik rozumiemy jako zbiór czterech liczb i nie ma znaczenia kolejność kostek? Wyniki mogą być następujące: {1, 2, 4, 5}, {3, 3, 5, 6}, {1, 1, 2, 6}. Mamy w tym przypadku do czynienia z kombinacjami z powtórzeniami. Jak obliczyć ich liczbę, w tym przypadku liczbę 4 – elementowych kombinacji z powtórzeniami ze zbioru 6 – elementowego?

Posłużmy się sztuczką. A co gdybyśmy zmienili liczbę elementów zbioru tak, aby cel osiągnąć za pomocą wzoru na liczbę kombinacji bez powtórzeń? Okazuje się, że można to zrobić powiększając wirtualnie nasz zbiór o (k – 1) elementów.

Zatem liczba kombinacji k – elementowych z powtórzeniami ze zbioru n – elementowego wyraża się wzorem: \(\overline{C}^{k}_{n} = \binom{n + k – 1}{k} = \frac{(n + k -1)!}{k! * (n – 1)!}\)

"""
Liczba kombinacji z powtórzeniami k - elementowych zbioru n - elementowego
"""
def liczba_komb_powt(n, k):
    return liczba_war(n + k - 1, k) / silnia(k)

Zbiór

Zbiór można rozumieć jako strukturę matematyczną, która zawiera jakieś elementy. Na przykład zbiór tworzą liczby całkowite nieujemne, mniejsze od 10. Zapisujemy go \(\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\) (więc tak jak w języku Python i nie ma znaczenia kolejność w jakiej podamy elementy zbioru). Zbiór nazywa się pustym, gdy nie zawiera żadnych elementów, skończonym (jak w przykładzie), gdy zawiera skończoną liczbę elementów, nieskończonym, gdy zawiera nieskończoną liczbę elementów. Na przykład zbiór wszystkich liczb całkowitych jest zbiorem nieskończonym.

Więcej informacji znajdziesz tutaj: Zbiór.

Ciąg

Ciąg to struktura uporządkowanych elementów z pewnego zbioru. Innymi słowy ciąg składa się z elementów pewnego zbioru, którym przyporządkowano liczbę naturalną określającą miejsce danego elementu w ciągu. Na przykład, aby zbudować ciąg ze wszystkich elementów zbioru liczb całkowitych nieujemnych, mniejszych od 10, należy przyporządkować każdemu z jego elementów inną liczbę naturalną z przedziału obustronnie domkniętego \(<1, 10>\).

Ciąg w języku Python można zapisać w postaci tablicy lub krotki, a więc dla powyższego ciągu, odpowiednio: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] lub (0, 1, 2, 3, 4, 5, 6, 7, 8, 9).

Więcej o ciągach znajdziesz tutaj: Ciąg.

Silnia

\(n! = \begin{cases} 1, & \text{dla } n = 0\\ 1 * 2 * … * n, & \text{dla } n\geq1\end{cases}\)

Symbol Newtona

\(\binom{n}{k} = \frac{n!}{k! * (n – k)!}\)

Źródła wiedzy