Elementy kombinatoryki

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 [latex]{a, b, c, d, e}[/latex], 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 [latex]5 * 4 * 3 * 2 * 1[/latex]. 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 [latex]n![/latex]. 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 [latex]5![/latex], czyli, jak jeszcze w tym przypadku łatwo obliczyć, [latex]120[/latex]. 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: [latex display=”true”]P_{n} = n![/latex]. 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 [latex]{a, a, a, g, l, m, m, y}[/latex] (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 [latex]{a, g, l, m, y}[/latex]). 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 [latex]n![/latex] 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ć [latex]3![/latex] nieodróżnialnych 3 – elementowych permutacji. Element 'm’ występuje w zbiorze 2 razy i za jego pomocą możemy stworzyć [latex]2![/latex] 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 [latex display=”true”]frac{8!}{3!*1!*1!*2!*1!}[/latex] 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, [latex]n_1, n_2, …, n_k[/latex] to krotności występowania elementów w zbiorze. Trzeba tutaj zauważyć, że [latex]n_1 + n_2 + … + n_k = n[/latex]. Równanie to bardziej elegancko zapiszemy w następujący sposób: [latex display=”true”]sum_{i=1}^{i=k}{n_i} = n[/latex]Wzór na liczbę permutacji z powtórzeniami przyjmie postać: [latex display=”true”]frac{n!}{n_{1}! * n_{2}! * … * n_{k}!}[/latex]. 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: [latex display=”true”]V^{k}_{n} = n * (n-1) * (n – 2) * … * (n – k + 1)[/latex]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: [latex display=”true”]V^{k}_{n} = frac{n!}{(n – k)!}[/latex]. 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 [latex]8 * 8 * 8 * 8[/latex]. 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: [latex display=”true”]overline{V}^{k}_{n} = n^{k}[/latex]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. [latex]abcde neq bacde[/latex]. 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: [latex display=”true”]C^{k}_{n} = binom{n}{k} = frac{n!}{k! * (n – k)!}[/latex]. Na marginesie, symbolu Newtona używa się do obliczania kolejnych czynników tzw. dwumianu Newtona, czyli wielomianu o postaci: [latex](x + y)^n[/latex].

"""
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: [latex display=”true”]overline{C}^{k}_{n} = binom{n + k – 1}{k} = frac{(n + k -1)!}{k! * (n – 1)!}[/latex]

"""
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)