Przedstawienie liczby jako suma

[ad0803]

Na ile różnych sposobów można przedstawić liczbę \(\displaystyle{ n}\) jako sumę liczb \(\displaystyle{ 1,2,...,n}\), tzn. \(\displaystyle{ 1+2}\) to jest to samo co \(\displaystyle{ 2+1}\)?
Czyli dla n=4 mamy 5 takich rozłożeń:
\(\displaystyle{ 1+1+1+1, \quad 1+1+2, \quad 2+2, \quad 1+3, \quad 5}\)

[Medea 2]

Wzoru nie ma, ale jak zwykle: funkcję tworzącą znaleźć można.

\(\displaystyle{ \prod_{k>0} \frac{1}{1-x^k} = \sum_{k = 0}^\infty x^k \prod_{i = 1}^k \frac{1}{1-x^i} = 1+\sum_{k>0}\frac{ x^{k^2}}{\prod_{i = 1}^k (1-x^i)^2}}\)

[ad0803]

Czyli, jeśli chcę policzyć np. ile jest takich przedstawień dla n=10 to nie da się tego policzyć?

[Valiors]

Można, ale żeby to zrobić matematycznie to trzeba się sporo namęczyć i mieć wiedzę o rekurencji, funkcjach tworzących i wielu innych rzeczach. Tutaj znajduje się rozwiązanie podobnego problemu

[Mariusz M]

Valiors, czy aby na pewno twoja rekurencja jest poprawna ?

\(\displaystyle{ F\left( x\right)= \sum_{n=0}^{ \infty }{f_{n}x^{n}}\\
\sum_{n=1}^{ \infty }{f_{n}x^{n}}=\sum_{n=1}^{ \infty }{\left( \sum_{i=1}^{ n }f_{n-i} \right) x^{n}}\\
\sum_{n=1}^{ \infty }{f_{n}x^{n}}=\sum_{n=1}^{ \infty }{\left( \sum_{i=0}^{ n-1 }f_{i} \right) x^{n}}\\
\sum_{n=1}^{ \infty }{f_{n}x^{n}}=\sum_{n=0}^{ \infty }{\left( \sum_{i=0}^{ n }f_{i} \right) x^{n+1}}\\
F\left( x\right)-1= \frac{x}{1-x}F\left( x\right)\\
\left( 1-\frac{x}{1-x}\right) F\left( x\right)=1\\
\frac{1-2x}{1-x}F\left( x\right)=1\\
F\left( x\right)=\frac{1-x}{1-2x}=\frac{1}{2} \cdot \frac{1-2x+1}{1-2x}\\
F\left( x\right)=\frac{1}{2}+\frac{1}{2} \cdot \frac{1}{1-2x}\\
f_{n}=\frac{1}{2}\left( 1-\mathrm{signum}\left( n\right) \right)+ \frac{1}{2} \cdot 2^{n} \\}\)

[Medea 2]

To już lepszym pomysłem jest liczenie tego z

\(\displaystyle{ f(n) = \sum_{k=0}^{n-1}\frac{ f(k) \cdot \sigma(n-k) }{n}.}\)