podziały liczby

[matinf]

Witam,

Niech \(\displaystyle{ p(n)}\) oznacza liczbę podziałów liczby \(\displaystyle{ n}\).
Udowodnij, ze tempo wzrostu \(\displaystyle{ p(n)}\) jest ponadwielomianowe, czyli że dla każdego ustalonego \(\displaystyle{ k}\) mamy \(\displaystyle{ p(n) = \omega (n^k)}\)

Jak się do tego w ogóle zabrać ?

[Zordon]

Idea:
rozważmy podziały postaci \(\displaystyle{ n=1\cdot x_1 + 2\cdot x_2+3\cdot x_3 +...+k \cdot x_k}\)
gdzie \(\displaystyle{ k \approx n^{1/3}}\) oraz \(\displaystyle{ 0\leq x_i\leq n^{1/3}}\) dla \(\displaystyle{ 2\leq i
\leq k}\)
Takich podziałów jest około \(\displaystyle{ (n^{1/3})^{n^{1/3}}}\) co daje tezę.