Na ile sposobów można umieścić 10 nierozróżnialnych kul w 5 rozróżnialnych urnach? Okazuje się, że ten, i podobne problemy można rozwiązać używając prostego triku.
Rozmieszczanie nierozróżnialnych kul w rozróżnialnych urnach może wydawać się niektórym problemem rzucającym pewne wyzwanie. Jak zobaczymy można sobie z nim poradzić bardzo prosto. Wystarczy tylko odpowiednio na niego spojrzeć. My spojrzymy na te zagadnienie z perspektywy kropek i słupków. Na początek rozważmy sytuację, gdy mogą zdarzyć się urny puste. Wymagamy jedynie aby każda kula znalazła się, w którejś urnie. W skrajnym przypadku wszystkie mogą wylądować w jednej urnie.
Zrobimy prosty rysunek, który natychmiast pozwoli nam rozwiązać nie tylko ten problem.
Mamy 10 dużych kropek, z których każda oznacza naturalnie jedną kulę. Zaś słupki dzielą owe kule na poszczególne urny. Każdy kolejny słupek jest zarazem końcem jednej jak i początkiem kolejnej urny. Jedynie pierwsza urna nie ma początkowego słupka, a ostatnia nie ma końcowego. W naszym przykładzie pierwszy słupek znajduje się za pierwszą kulą. Zatem w pierwszej urnie znajduje się jedna kula. Drugi słupek jest zaraz za pierwszym. Oznacza to, że druga urna jest pusta. Między drugim a trzecim słupkiem mamy 4 kule, czyli w trzeciej urnie znajdują się właśnie 4 kule itd. Można już w zasadzie zrozumieć ideę. Każde rozmieszczenie słupków to jeden podział kulek na poszczególne urny. Teraz przejdźmy do ogólnego rozwiązania.
Mamy 10 kropek/kul oraz 5 urn. Ponieważ każdy słupek oddziela dwie urny, to potrzebujemy czterech słupków aby podzielić kule między 5 urn. W ogólności, potrzeba \(k-1\) słupków aby dokonać podziału kul na \(k\) urn. W naszym przypadku, mamy 10 kropek i 4 słupki, czyli łącznie 14 obiektów. Każde rozmieszczenie słupków daje nam podział kul na urny. Co oczywiste, inne rozmieszczenia słupków prowadzą do innych podziałów kul między rozróżnialne urny. Wystarczy teraz zauważyć tylko, że każde rozmieszczenie naszych 4 słupków jest niczym innym jak czteroelementowym podzbiorem zbioru wszystkich naszych obiektów, których jest 14. Czyli jest \[{14 \choose 4} = 1001\] sposobów na umieszczenie 10 kul w 5 rozróżnialnych urnach. W ogólności, gdy mamy \(n\) kul oraz \(k\) urn, to takich sposobów jest \[{n+k-1 \choose k-1}.\]
Teraz rozważmy problem, w którym w każdej urnie musi się znaleźć przynajmniej jedna kula, tzn. nie może być pustych urn. Wymusza to od razu założenie, że \(n\geqslant k\), gdzie podobnie jak poprzednio, \(n\) to liczba kul, a \(k\) to liczba urn. Skoro nie może być pustych urn, to żadne dwa słupki nie mogą się znaleźć obok siebie. Do tego, nie może być słupka na samym początku ani na samym końcu bo wtedy pierwsza lub ostatnia urna byłaby pusta. Innymi słowy mamy \(n-1\) miejsc, w które możemy wetknąć słupki.
Od razu widać, że tym razem problem sprowadza się do umieszczenia \(k-1\) słupków w \(n-1\) miejsc. Przy czym w jednym miejscu może się znajdować co najwyżej jeden słupek. Każde takie rozmieszczenie słupków możemy utożsamiać po prostu z podzbiorem \((n-1)\)-elementowego zbioru. Reasumując, tym razem mamy \[{n-1 \choose k-1}\] sposobów.
Od razu przychodzi do głowy ogólniejsze ograniczenie. Możemy rozważyć sytuację, w której chcemy aby w \(i\)-tej urnie znalazło się co najmniej \(a_i\) kulek. Sprawia to, że musi zachodzić \[n\geqslant a_1+a_2+\cdots + a_k.\] Bezpośrednie zastosowanie naszej metody kropek i słupków jest raczej trudne. Możemy jednak posłużyć się prostym trikiem. Mianowicie, jeżeli przyjmiemy \[m=n-a_1-a_2-\cdots-a_k,\] to nasz problem jest równoważny rozmieszczeniu \(m\) kul w \(k\) urnach. Czyli sposobów rozmieszczenia kul przy założeniu, że w \(i\)-tej urnie musi ich być co najmniej \(a_i\) jest \[{m+k-1 \choose k-1}.\]
Rozważmy teraz inne zadanie, które z pozoru wydaje się zupełnie inne lecz, jak zobaczymy, jest zupełnie takie samo. Mianowicie, ile rozwiązań wśród nieujemnych liczb całkowitych ma równanie \[x_1+x_2+\cdots+x_k = n,\] gdzie \(n\) jest również nieujemną liczbą całkowitą? Może nie dla każdego jest to takie oczywiste na pierwszy rzut oka, ale możemy zauważyć, że każde \(x_i\) możemy utożsamiać z urną, w której znajduje się pewna ilość kul (być może nawet 0), a samych kul jest łącznie \(n\). Odpowiedź jest więc oczywista! Takich rozwiązań jest \[{n+k-1\choose k-1}.\]
Tutaj też, jak w przypadku kul i urn, możemy dodać ograniczenia, że \(x_i\geqslant a_i\) dla pewnych \(a_i\in\mathbb N\). Tak postawiony problem, rozwiążemy tak samo jak analogiczny z kulami i urnami.