Kombinacje z powtórzeniami

Kombinacje z powtórzeniami są podobne do zwykłych kombinacji, tylko pozwalamy, żeby elementy zbioru M, z którego wybieramy, mogły się powtarzać.

Definicja i wzór

Zacznijmy od sympatycznego przykładu: wchodzisz do sklepu i chcesz kupić na biwak dwanaście piw w butelkach. Na półce są cztery różne rodzaje. Masz kilka możliwości, jak je kupić — możesz na przykład kupić 5 Żywców, 2 Tyskie, 1 Lecha i 4 Okocimy albo możesz kupić od każdego browaru dokładnie trzy butelki. Na ile różnych sposobów możesz kupić butelki, żeby mieć ich dokładnie dwanaście?

Mamy więc zbiór $M = {\text{Żywiec}, \text{Tyskie}, \text{Lech}, \text{Okocim}}$ i pytamy, ile istnieje zestawów k elementów, gdzie k = 12, które składają się z elementów zbioru M i w których kolejność nie ma znaczenia.

Wyprowadzenie wzoru jest już nieco trudniejsze niż w pozostałych zadaniach kombinatorycznych. Najpierw wyobrazimy sobie nasze zakupy jako ciąg zer i jedynek, w którym liczba jedynek odpowiada liczbie kupionych butelek danego browaru, a zero oddziela od siebie poszczególne browary. Tak więc 111011101111101 mówi nam, że kupiliśmy trzy Żywce (pierwsze trzy 1), potem trzy Tyskie (0 jest separatorem, kolejne trzy 1), potem pięć Lechów (0 separator i pięć 1) i na koniec jednego Okocima. Całą zasadę pokazuje poniższy zapis:

$$ \underbrace{111}_{\text{Żyw}}0\underbrace{111}_{\text{Tys}}0\underbrace{11111}_{\text{Lech}}0\underbrace{1}_{\text{Oko}} $$

Gdybyśmy chcieli kupić 6 Żywców, 4 Tyskie, 2 Okocimy i żadnego Lecha, ciąg wyglądałby tak:

$$ \underbrace{111111}_{\text{Żyw}}0\underbrace{1111}_{\text{Tys}}00\underbrace{11}_{\text{Oko}} $$

Zauważmy, że długość tego ciągu jest zawsze równa 15 — musi w nim być 12 jedynek, żebyśmy kupili łącznie 12 piw. I muszą w nim być trzy separatory, żebyśmy mogli oddzielić od siebie cztery różne browary. Pozostaje więc obliczyć, ile istnieje takich ciągów o długości 15, które zawierają dokładnie trzy zera.

Wystarczy nam policzyć rozmieszczenia zer — w chwili, gdy między 12 jedynek wstawimy 3 zera, mamy jakiś poprawny zestaw piw. Innymi słowy: mamy łącznie 15 przegródek i 3 z nich musimy zająć zerem. Pozostałe przegródki automatycznie wypełniamy jedynkami.

To już proste zadanie na kombinacje bez powtórzeń. 15 przegródek numerujemy liczbami {1, …, 15} i z tego zbioru wybieramy za każdym razem trzy liczby, czyli trzy pozycje, na których postawimy zero. Na przykład dla kombinacji {2, 4, 7} otrzymalibyśmy ciąg: 101011011111111. Na 2., 4. i 7. miejscu jest zero, reszta to jedynki. Istnieje więc łącznie

$$ {15\choose3} = 455 $$

różnych sposobów rozmieszczenia zer w 15 przegródkach, a tym samym 455 różnych sposobów kupienia 12 piw, jeśli mamy do wyboru cztery rodzaje.

Poprzednie rozumowanie możemy uogólnić. Jeśli mamy zbiór M, który ma n elementów, i wybieramy z niego k elementów, przy czym poszczególne elementy mogą się powtarzać, to układamy ciąg zer i jedynek o długości n + k − 1 (k jedynek i n − 1 zer) i sprawdzamy, na ile sposobów możemy rozmieścić n − 1 zer. Liczba kombinacji z powtórzeniami, którą oznaczymy $\overline{C}_n^k$, jest więc równa

$$ \overline{C}_n^k = {n+k-1 \choose n-1} = {n+k-1\choose k}. $$

Ostatnie przekształcenie mogliśmy zrobić dzięki podstawowym zależnościom między symbolami Newtona.

Rozwiązane przykłady

1. Na ile sposobów można rozdzielić 20 darmowych biletów na premierę nowej komedii między 10 emerytek? To przykład na kombinacje z powtórzeniami, bo jedna emerytka może dostać więcej darmowych biletów, potencjalnie nawet wszystkie. Musimy tylko dobrze zrozumieć, co jest n, a co k. W rzeczywistości wybieramy 20-elementowe kombinacje z 10 emerytek, innymi słowy tworzymy ciąg zer i jedynek, który ma długość 29 i zawiera 20 jedynek i 9 zer. Tak więc n = 10, k = 20. Otrzymujemy wynik:

$$ \overline{C}_{10}^{20} = {10 + 20 - 1 \choose 20} = 10{,}015,005. $$