Podział liczb

[jayson]

Na ile sposobów można podzielić liczbę 72 na cztery liczby całkowite nieujemne nieparzyste podzielne przez 3 ?

[ampersand]

A istnieje jakiś inny podział niż taki:

Kod: Zaznacz cały

                                         72
                                        /  
                                     8/     24
                                      /       
                                     9        3
                                    / 
                                 1/    3
                                  /      
                                 9       3
                                / 
                             1/    3
                              /      
                             9       3
                            / 
                         1/    3
                          /      
                        9        3

?
Jeżeli nie to w sumie można na 5 sposobów. Nie bijcie jeżeli się myle.

[max]

Wcześniej chciałem za szybko, teraz powinno być dobrze:

Pytamy o liczbę niesymetrycznych rozwiązań (w liczbach całkowitych nieujemnych) równania:
\(\displaystyle{ 3(2x_{1} + 1) + 3(2x_{2} + 1) + 3(2x_{3} + 1) + 3(2x_{4} + 1) = 72\\
x_{1} + x_{2} + x_{3} + x_{4} = 10}\)
czyli pytamy na ile różnych sposobów możemy zapisać liczbę 10 jako sumę 4 liczb całkowitych nieujemnych.

Niech \(\displaystyle{ q(n, k)}\) oznacza liczbę sposobów zapisu liczby \(\displaystyle{ n}\) za pomocą \(\displaystyle{ k}\) liczb całkowitych nieujemnych. Można pokazać (np indukcyjnie), że spełniona jest zależność:
\(\displaystyle{ q(n, k) = q(n, k - 1) + q(n - k, k),}\)
przy wartościach brzegowych:
\(\displaystyle{ q(n, 0) = 0, \\ q(0, k) = 1, \\ q(n, m) = q(n, n), \ m > n}\)
skąd można uzyskać:
\(\displaystyle{ q(10, 4) = 23}\)

Można też pominąć teorię i po prostu wypisać te 23 podziały...

Pytanie ode mnie: Czy można obliczać wartość zdefiniowanej powyżej funkcji q(n, k) w sposób bardziej przyjazny niż bezpośrednie korzystanie z rekurencji czy rozpisywanie trójkąta:
1
1 2
1 2 3
1 3 4 5
1 3 5 6 7
1 4 7 9 10 11
1 4 8 11 13 14 15

(chodzi mi tu o coś w miarę ogólnego, bo np q(n, 2) = 1 + [n/2] widać od razu...)