# Find a polynomial with evaluation equal to # of partitions of n into at most k parts

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.

• 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. – Marko Riedel Sep 6 '15 at 20:22
• 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$ – Peter Taylor Sep 9 '15 at 13:32