TITLE: Polynomial coefficients
QUESTION [1 upvotes]: How many coefficients does the n-th order polynomial in m variables have? For instance, 2nd order polynomial in 2 variables is:
$p(x_1,x_2) = a_{00}x_1^0 x_2^0 + a_{01} x_1^0 x_2^1 + a_{10} x_1^1x_2^0 + a_{11}x_1^1x_2^1 + a_{02}x_1^0x_2^2 + a_{20}x_1^2 x_2^0$
With coefficients: $a_{00}$, $a_{01}$, $a_{10}$, $a_{11}$, $a_{02}$, $a_{20}$. So, in total 6 coefficients.

REPLY [1 votes]: The number of coefficients is, of course, the number of terms $x_1^{k_1}\cdots x_m^{k_m}$ that occur.  Such a term occurs if and only if $k_1+\cdots+k_m\leq n$.
So, we need to count the number of ways of choosing a tuple $(k_1,\ldots,k_m)$ such that $k_i\geq 0$ for all $i$ and $k_1+\cdots+k_n\leq m$.
Equivalently, we can define the "shortfall" $k^*:=n-k_1-\cdots-k_m$; then we want to count the tuples $(k_1,\ldots,k_m,k^*)$ such that $k_i,k^*\geq0$ and $k_1+\cdots+k_m+k^*=n$.
You can think of this as having $m+1$ bins, and throwing $n$ balls in to them; a standard stars-and-bars argument then says that the number of ways of choosing $(k_1,\ldots,k_m,k^*)$ is precisely
$$
\binom{n+(m+1)-1}{(m+1)-1}=\binom{n+m}{m}.
$$
For instance, taking $n=m=2$ we get that there are $\binom{4}{2}=6$ terms in a general $n$th-degree polynomial in $m$ variables, recovering your example.
{"set_name": "stack_exchange", "score": 1, "question_id": 482988}