Fix a positive integer $k$. For positive integer $n$ let $p(n;\le k)$ denote the number of partitions of $n$ into at most $k$ parts, and let $p(0;\le k)=1$.
(1) Show that there is a polynomial $P(x)$ s.t. $p(n;\le k)=P(n)$ for all nonnegative integers $n$.
(2) And show that $(-1)^{k-1}P(-n)$ equals the number of partitions of n into exactly $k$ distinct parts.
I'm very confused that if the required polynomial has degree $d$, then it is determined uniquely by $d+1$ values, say $P(0),P(1),\cdots,P(d)$. But it seems that the polynomial works for infinite many $n$. I tried to use Lagrange interpolation, but it didn't work well. So how to figure out that? And I think if I know the answer to problem (1), I can work out problem (2). Thanks!

New idea:

I'm trying to use Proposition 4.3 on page 79 of Combinatorial Reciprocity Theorems (a book draft) by Matthias Beck and Raman Sanyal to prove it.

The proposition says "A sequence $f(n)$ is given by a polynomial of degree $\leqslant d$ iff $(\Delta^m f)(0)=0$ for $m>d$."

Where we can set $(\Delta f)(n)=f(n+1)-f(n)$. Then $f(n)=p(n;\le k)$ in our problem. But I'm chocked to find out $(\Delta^m f)(0)$ now.

  • $\begingroup$ This would appear to need clarification. E.g. using Polya Enumeration for at most three parts we get $$\sum_{q=1}^3 Z(S_q)\left(\frac{z}{1-z}\right)$$ which gives the sequence $$ 1, 2, 3, 4, 5, 7, 8, 10, 12, 14, 16, 19, 21, 24,\ldots $$ which is OEIS A001399. Maple GFUN says this has closed form $${\frac {35}{72}}+n/4+1/8\, \left( -1 \right) ^{-n}+1/12\, \left( n+1 \right) \left( n+2 \right)\\ +1/9\, \left( -1/2+i/2\sqrt {3} \right) ^{-n}+1/9\, \left( -1/2-i/2\sqrt {3} \right) ^{-n}+\cases{-1&$n=0$\cr 0&otherwise\cr}$$ which is not a polynomial. $\endgroup$ – Marko Riedel Sep 6 '15 at 20:22
  • 1
    $\begingroup$ Perhaps instead of $p(n;\le k)=P(n)$ the question statement should say that $p(n;\le k)=\mathrm{round}(P(n))$? E.g. for at most three parts, $p(n;\le 3)$ is the nearest integer to $(n+3)^2/12$ $\endgroup$ – Peter Taylor Sep 9 '15 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.