Podział liczby 'n' na sumę 'k' nieujemnych składników (kol.)

[dariusz_konieczny]

Problem: na ile sposobów można podzielić liczbę naturalną \(\displaystyle{ n}\) na sumę \(\displaystyle{ k}\) naturalnych (z zerem) składników, przy czym kolejność gra rolę. Np. dla \(\displaystyle{ n=2}\) i \(\displaystyle{ k=4}\) mamy rozwiązania:
\(\displaystyle{ 2+0+0+0\\
0+2+0+0\\
0+0+2+0\\
0+0+0+2\\
1+1+0+0\\
1+0+1+0\\
1+0+0+1\\
0+1+1+0\\
0+1+0+1\\
0+0+1+1}\)
czyli \(\displaystyle{ 10}\) możliwości

1) czy ten problem ma jaką inną nazwę?
2) czy jego rozwiązanie jest gdzieś na sieci (w książce) wytłumaczone
3) ew. jak go rozwiązać

Osiągnąłem równanie rekurencyjne (zakładając, że jednostkę wstawiam na pewną pozycję, a kolejne jednostki mogę wstawić tylko na pozycję nie wcześniej niż pierwszą):
\(\displaystyle{ f(k,n)=
\begin{cases}
1 &\text{dla } n=0 \\
1 &\text{dla } k=1 \\
\sum_{i=1}^{k} f(i,n-1) &\text{dla } k>1, n \neq 0
\end{cases}}\)

Które po rozwiązaniu dla trzech pierwszych \(\displaystyle{ k}\) wynosi:
\(\displaystyle{ \begin{array}{l}
f(1,n)=1 \\
f(2,n)=n+1 \\
f(3,n)= \frac{(n+1) \cdot (n+2)}{2} \\
\end{array}}\)

czy to możliwe, że ogólny wzór będzie (dla \(\displaystyle{ k>1}\)):
\(\displaystyle{ f(k,n)=\frac{(n+1) \cdot (n+2) \cdot ... \cdot (n+k-1)}{(k-1)!}}\)

[Gouranga]

to jest zadanie na funkcje generujące / szeregi formalne
\(\displaystyle{ x_1 + x_2 + x_3 + x_4 = n}\)
wprowadzamy sobie roboczą zmienną \(\displaystyle{ z}\) i dla każdej zmiennej \(\displaystyle{ x_i}\) tworzymy jeden nawias, w którym mamy sumę zmiennych \(\displaystyle{ z}\) w potęgach, które reprezentują wartość możliwą dla danego \(\displaystyle{ x_i}\)

\(\displaystyle{ \left(z^0 + z^1 + z^2 + \ldots + z^n\right) \cdot \left(z^0 + z^1 + z^2 + \ldots + z^n\right) \cdot \ldots}\)
i tak nawias dla każdego \(\displaystyle{ x_i}\)
w przykładzie z dwójką:
\(\displaystyle{ \left(z^0 + z^1 + z^2\right)\left(z^0 + z^1 + z^2\right)\left(z^0 + z^1 + z^2\right)\left(z^0 + z^1 + z^2\right)}\)
bo rozkładamy na 4 składniki, z których każdy może mieć wartość od 0 do 2 i teraz co jest dla nas kluczowe, to jak przemnożymy to wszystko to wyjdzie nam:
\(\displaystyle{ \left(z^0 + z^1 + z^2\right)^4 = z^8 + 4z^7 + 10z^6 + 16z^5 + 19z^4 + 16z^3 + 10z^2 + 4z + 1}\)
i skoro suma ma być \(\displaystyle{ 2}\) to patrzymy na czynnik przy \(\displaystyle{ z^2}\), jest to \(\displaystyle{ 10}\) więc na 10 sposobów można to rozłożyć
wiadomo, że dla dużych liczb nikt nie będzie tego wszystkiego mnożył, więc na wyższym poziomie wystarczająco dokładną odpowiedzią jest zapis:
\(\displaystyle{ \left(z^0 + z^1 + z^2\right)^4 \quad \left[z^2\right]}\)
czyli ten nawias kwadratowy po prawej mówi, że odpowiedzią jest czynnik przy \(\displaystyle{ z^2}\) w rozwinięciu tej funkcji

[Waylays]

Kolega wyżej podał rozwiązanie za pomocą funkcji tworzących, a ja podejde to tego zagadnienia inaczej. O ile dobrze myślę, to chodzi ci o znalezienie liczby rozwiązań równania \(\displaystyle{ x_1+x_2+...+x_k=n}\), gdzie \(\displaystyle{ x_i \in \{0, 1, 2, ...\}}\). Ponieważ rozwiązań szukamy w liczbach naturalnych, to równanie nazywa się równaniem diofantycznym. Odpowiedź na twoje pytanie jest bardzo prosta, lecz niekoniecznie łatwa - liczbę takich rozwiązań możemy wyrazić za pomocą liczby kombinacji z powtórzeniami \(\displaystyle{ n}\)-elementowych ze zbioru \(\displaystyle{ k}\)-elementowego (i tu trzeba uważać żeby się nie pogubić bo jeżeli przez \(\displaystyle{ n}\) oznaczymy prawą stronę, a przez \(\displaystyle{ k}\) liczbę niewiadomych, to tworzymy właśnie \(\displaystyle{ n}\)-elementowe kombinacje ze zbioru \(\displaystyle{ k}\)-elementowego). Czyli liczba takich rozwiązań to \(\displaystyle{ \overline {C}^n_k={{n+k-1} \choose n}={{n+k-1} \choose {k-1}}}\). Sytuacja analogiczna do rozmieszczania \(\displaystyle{ n}\) nierozróżnialnych kulek w \(\displaystyle{ k}\) rozróżnialnych pudełkach.

W twoim przypadku mamy zatem \(\displaystyle{ \overline {C}^2_4={{2+4-1} \choose 2}= \frac{4\cdot 5}{2} =10}\).
Co do twojego rozwiązania, jak rozpiszesz sobie ogólną liczbę kombinacji za pomocą silni, to zauważysz, że brakuje ci czegoś w mianowniku, a mianowicie \(\displaystyle{ n!}\).

~edit
Racja, niczego we wzorze nie brakuje. Nie zauważyłem, że mianownik leci od \(\displaystyle{ n+1}\) zamiast od \(\displaystyle{ 1}\), więc wszystko wygląda okay.

[dariusz_konieczny]

Dzięki obydwóm Kolegom!

Pierwsze tłumaczenie jest piękne matematycznie - suma zamieniona na iloczyn, jeszcze do tego potęgi itp. Ale, tak - zrozumiałem o co chodzi. Tylko to trochę strzelanie z armaty do muchy.
Drugie rozwiązanie bardziej mi się podoba, dlatego tu wpisałem ten problem, bo coś czułem że to można wzorami kombinatorycznymi rozwiązać. Tylko nie spojrzałem na ten problem pod właściwym kątem, jak drugi z Panów (a gdzieś mi się plątała od wczoraj po głowie zasada szufladkowa Dirichleta). I niczego w moim ostatecznym wzorze nie brakuje, bo to jest dokładnie rozwinięcie tego C z kreską nad. Więc wszystko się zgadza.

Sam problem pojawił mi się wczoraj, gdy żona załapała bakcyla w rozwiązywaniu "obrazków logicznych". Za młodu napisałem program, który dla każdej linii generował możliwe układy punktów i wyznaczał, gdzie na pewno są pola zaczernione, a gdzie na pewno puste (i ostatecznie lecąc po kolumnach, wierszach, kolumnach etc. rozwiązywał całe zadanie). Ale dopiero dzisiaj zacząłem się zastanawiać, ile takich kombinacji właściwie dla danej linii istnieje. I mój wzór rekurencyjny wynika ze sposobu w jaki mój program generował kolejne układy. Po przeformułowaniu to jest właśnie problem, który przedstawiłem powyżej.

Problem uznaję za rozwiązany, aczkolwiek ciekawe, czy istnieją jeszcze inne sposoby rozwiązania tego problemu?

[Hubbaser]

Można podejść do tego problemu kombinatorycznie. Chcesz podzielić \(\displaystyle{ n}\) nierozróżnialnych kulek na bloki, przy czym ważna jest kolejność bloków.

Dodatkowo dysponujemy \(\displaystyle{ k-1}\) przegródkami.

Mamy \(\displaystyle{ n+k-1}\) miejsc - w każdej znajdzie się przegródka lub kulka. Wybieramy więc miejsca w których mają być kulki, a na pozostałych umieszczamy przegródki.

Łatwo zauważyć, że istnieje bijekcja między układami kulek i podziałami liczby \(\displaystyle{ n}\).

[Gouranga]

Hubbaser, to co opisałeś o kulkach i przegródkach w literaturze występuje jako rozwiązanie metodą separatorów. Rozmieszczenie \(\displaystyle{ k}\) nierozróżnialnych kul do \(\displaystyle{ n}\) rozróżnialnych pudełek o ile pamiętam ze studiów było oznaczane jako:
\(\displaystyle{ \left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose k}}\)
czyli dokładnie to co opisałeś, mamy \(\displaystyle{ n+k-1}\) miejsc, z czego wybieramy \(\displaystyle{ k}\) na kule.
A co do "strzelania do muchy z armaty" to jak akurat nic prostszego nie przychodzi do głowy to można strzelać, grunt, żeby trafić. Tak długo jak rozwiązanie jest poprawne jest ok.

[kinia7]

Hubbaser\(\displaystyle{ \left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose k}}\)

raczej

\(\displaystyle{ \left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose n}}\)

edit
rzeczywiście, powinnam była napisać
\(\displaystyle{ \left\langle \begin{array}{c}k\\n\end{array}\right\rangle = {n+k-1 \choose n-1}}\)

[Gouranga]

przy wkładaniu \(\displaystyle{ k}\) kul do \(\displaystyle{ n}\) pudełek wybieramy \(\displaystyle{ k}\) miejsc na kule.