Rozkład liczby n na sumę k składników

[kinwotar]

Na ile sposobów można zapisać liczbę naturalną \(\displaystyle{ n}\) za pomocą sumy \(\displaystyle{ k}\) liczb całkowitych dodatnich przy czym kolejność liczb w sumie nie ma znaczenia np. \(\displaystyle{ a+b+c}\) jest tym samym co \(\displaystyle{ a+c+b}\) .

[mol_ksiazkowy]

Wsk: Ilość rozwiązań równania \(\displaystyle{ x_1+....+x_n=k}\) w zbiorze liczb całkowitych nieujemnych można utożsamić z liczbą rozmieszczeń \(\displaystyle{ k}\) nierozróżnialnych kul w \(\displaystyle{ n}\) szufladach, tj. \(\displaystyle{ x_i}\) jest liczbą kul w szufladzie nr \(\displaystyle{ i}\) . A wiec jest ich razem \(\displaystyle{ k+n-1 \choose k}}\) .

[kinwotar]

Hmm, no tak... Ale czy jest to to samo co napisałeś. Wydaje mi się, że w swoim rozwiązaniu uwzględniasz kolejność czynników.
Np. liczbę \(\displaystyle{ 4}\) można rozbić na takie sumy: \(\displaystyle{ 4; 3+1; 2+2; 2+1+1; 1+1+1+1}\) . W sumie powinno wyjść \(\displaystyle{ 5}\) , a wg tego wzoru zakładając że liczba \(\displaystyle{ x}\)-ów jest równa \(\displaystyle{ 4}\) wychodzi \(\displaystyle{ 35}\) . Chodzi mi o rozmieszczenie \(\displaystyle{ n}\) nierozróżnialnych kul w \(\displaystyle{ n}\) nierozróżnialnych szufladach.

[Qń]

Rzeczywiście, ilość rozwiązań podanego równania (pomijam już zamianę \(\displaystyle{ n}\) z \(\displaystyle{ k}\) ) w liczbach całkowitych nieujemnych, to mocno nie to samo co liczba rozkładów liczby na ustaloną ilość składników dodatnich, gdzie kolejność nie gra roli.

Na to drugie nie ma jakiegoś ładnego, zwartego wzoru – natomiast jeśli znamy konkretne \(\displaystyle{ k}\) , to możemy ułożyć stosowną rekurencję pozwalającą nam obliczać liczbę podziałów dla dowolnego \(\displaystyle{ n}\) (choć złożoność obliczeniowa jest duża).

Pozdrawiam.

Qń

[kinwotar]

Ok. Dzięki za odpowiedz.

[msissek]

Odświeżam temat. Czy jest wzór na obliczenie wszystkich możliwych podziałów liczby\(\displaystyle{ n}\) na \(\displaystyle{ k}\) składników, gdzie składniki te będą z góry określone? Np. liczbę \(\displaystyle{ 15}\) zapisać za pomocą sumy \(\displaystyle{ 3}\) składników, gdzie składniki te mogą być od \(\displaystyle{ 1}\) do \(\displaystyle{ 9}\) .