How many cubic (i.e., third-degree) polynomials $f(x)$ are there such that $f(x)$ has positive integer coefficients and $f(1)=9$? (Note: all coefficients must be positive---coefficients are not permitted to be 0, so for example $f(x) = x^3 + 8$ is not a valid polynomial.)
I can't list all of them and I need a 1-1 correspondence, which I haven't figured out yet.
On
Consider polynomial $f(x) \in \mathbb{Z}[X]$. In general it looks like $f(x) = ax^3 + bx^2 + cx + d$ where $a, b, c, d$ are positive integers. Given is, $f(1) = a+ b+ c+ d = 9$. So the number of such cubic polynomials correspond to the number of positive integer solutions of $a+b+c+d=9$.
EDIT: Apply Balls and sticks method. if $x = a-1, y=b-1, z=c-1, w=d-1$ then the number of positive integer solutions of $(a,b,c,d)$ s.t. $a+b+c+d=9$ are the same as non-negative integer solution of $(x,y,z,w)$ s.t. $x+y+z+w = 9-4=5$. The total number of solutions is $\binom{5+3}{3}$. (reference: combinations of multisets) Can you do this for nonnegative coefficients?
Hint: the number of $(a,b,c,d)\in\left(\mathbb{Z}^+\right)^4$ such that $a+b+c+d=9$ is given by the coefficient of $x^9$ in the product $(x+x^2+x^3+\ldots)^4$, i.e. by $$ [x^9]\frac{x^4}{(1-x)^4} = [x^5]\frac{1}{(1-x)^4}=[x^5]\sum_{n\geq 0}\binom{n+3}{3}x^n =\binom{5+3}{3}=\color{red}{56}.$$ See also stars and bars.