Kombinacje z powtórzeniami
Kapitoly: Kombinatoryka, Wariacje, Permutacja, Kombinacja, Wariacje z powtórzeniami, Kombinacje z powtórzeniami, Ile jest różnych kodów PIN?, Kalkulator.
Kombinacje z powtórzeniami są podobne do klasycznych kombinacji, tylko pozwalamy na powtarzanie się elementów ze zbioru podpierającego M.
Definicja i wzór
Zacznijmy od miłego przykładu: wchodzisz do sklepu i chcesz kupić dwanaście butelkowanych piw z kranu. Na półce znajdują się w sumie cztery różne butelki. Teraz masz kilka opcji zakupu butelek - na przykład możesz kupić 5 Pilsnerów, 2 Gambrinusy i 1 Staropramena lub możesz kupić tylko dwie butelki od każdego producenta. Ile jest w sumie różnych opcji zakupu butelek, aby mieć tylko dwanaście?
Mamy więc podstawowy zbiór M = {Plzeň, Gambrinus, Staropramen, Kozel} i pytamy ile istnieje k-tic gdzie k = 12, które zawierają elementy ze zbioru M i dla których kolejność nie ma znaczenia?
Wyprowadzenie wzoru jest już bardziej skomplikowane niż w przypadku innych problemów kombinatorycznych. Po pierwsze, myślimy o naszym zakupie jako sekwencji zer i jedynek, tak że liczba jedynek odpowiada liczbie butelek zakupionych od danego producenta, a zero oddziela producentów. Tak więc 111011101111101 mówi nam, że kupiliśmy trzy Pilsnery (pierwsze trzy jedynki), następnie trzy Gambrinusy (0 jest separatorem, kolejne trzy jedynki), następnie pięć Staropramenów (0 jest separatorem, następnie pięć jedynek), a na końcu jednego Kozela. Cała zasada jest pokazana na poniższym obrazku:
$$ \underbrace{111}_{Plz}0\underbrace{111}_{Gam}0\underbrace{11111}_{Star}0\underbrace{1}_{Koz} $$
Gdybyśmy chcieli kupić 6 Pilsnerów, 4 Gambrinusy, 2 Kozły i żadnego Staropramena, sekwencja wyglądałaby następująco:
$$ \underbrace{111111}_{Plz}0\underbrace{1111}_{Gam}00\underbrace{11}_{Koz} $$
Zauważ, że długość tego ciągu jest zawsze równa 15 - musi być 12 jedynek, aby kupić łącznie 12 piw. I muszą być trzy separatory, aby móc oddzielić czterech różnych producentów. Pozostaje więc obliczyć, ile w sumie istnieje takich ciągów o długości 15, które zawierają dokładnie trzy zera?
Musimy tylko obliczyć rozmieszczenie zer - w momencie, gdy umieścimy 3 zera wśród 12 jedynek, mamy pewną prawidłową kombinację piw. Innymi słowy: mamy w sumie 15 beczek piwa i musimy zająć 3 z nich zerami. Pozostałe beczki automatycznie zajmujemy jedynkami.
To już jest prosty problem kombinacji bez powtórzeń. Numerujemy 15 budek za pomocą {1, …, 15} i teraz zawsze wybieramy trzy liczby z tego zestawu, co daje nam trzy indeksy, w których umieszczamy zero. Na przykład dla kombinacji {2, 4, 7} otrzymamy ciąg: 101011011111111. Indeksy 2, 4 i 7 to zera, a pozostałe to jedynki. Istnieje więc łącznie
$$ {15\choose3} = 455 $$
różnych sposobów na umieszczenie zer w 15 chatach, a zatem 455 różnych sposobów na zakup 12 piw, jeśli mamy cztery różne piwa.
Możemy uogólnić poprzednie rozumowanie. Jeśli mamy zbiór elementów M o rozmiarze n i wybieramy z niego k-tice, a elementy mogą się powtarzać, to tworzymy ciąg zer i jedynek o długości n + k − 1 (k jedynki i n − 1 zera) i znajdujemy, na ilu pozycjach możemy umieścić n − 1 zera, tak aby liczba kombinacji z powtórzeniami, oznaczana C'(k, n), była równa
$$ C'(k, n) = {n+k-1 \choose n-1} = {n+k-1\choose k}. $$
Byliśmy w stanie dokonać ostatniej korekty ze względu na podstawowe zależności między liczbami kombinacji.
Rozwiązane przykłady
- Na ile sposobów można podzielić 20 darmowych biletów na premierę filmu Babel między 10 emerytek? Jest to przykład kombinacji z powtórzeniami, ponieważ jedna emerytka może otrzymać wiele, potencjalnie wszystkie, darmowe bilety. Musimy tylko dobrze zrozumieć, co jest n, a co k. W rzeczywistości wybieramy 20 kombinacji 10 emerytów, innymi słowy, tworzymy sekwencję zer i jedynek taką, że sekwencja ma długość 29, zawiera 20 jedynek i 9 zer. Tak więc n = 10, k = 20 otrzymujemy wynik:
$$ C'(10, 20) = {10 + 20 - 1 \choose 20} = 10{,}015,005. $$