Number of polynomial terms for certain degree and certain number of variables I would like to calculate the maximum number of polynomial terms given a certain number of variables and a certain degree. eg. given that the number of variables is 2 and the degree is 3, the maximum number of terms is 9:
$$x_1^3 + x_1^2 x_2 + x_1 x_2^2 + x_2^3+ x_1^2 +x_1 x_2 + x_2^2 + x_1 + x_2 + 1$$
How can I calculate this maximum number? Thanks for answering.
 A: If you have $k$ variables and want degrees $1,...,n$, you get the sum $$\sum_{i=1}^n h_i(1,...,1)=\sum_{i=1}^n\binom{k+i-1}{i}=\binom{k+n}{n}-1.$$  Here  the $h_i$ are the  complete homogeneous symmetric polynomials.
A: This really isn't a research level question. But here's a nice trick for getting the answer without doing the sum as in Wolfgang's answer. It's easier to ask for the number of distinct monomials of exact degree $n$ in $k+1$ variables $x_0,\ldots,x_k$. Then you can set $x_0=1$ if you want monomials of degree at most $n$ in $k$ variables.
Okay, here's the trick. Write down a list of $k+n$ symbols
$$ \underbrace{*****\cdots***}_{k+n}.$$
Choose any $k$ of your symbols and change them to some other symbol
$$ \underbrace{*o***o*\cdots*o**}_{\text{$n$ stars and $k$ circles}}.$$
Now read how many stars there are between each circle, that's the exponent of that monomial. So for example
$$ **o***oo*o* \quad\longleftrightarrow\quad x_0^2x_1^3x_2^0x_3^1x_4^1 
=x_0^2x_1^3x_3x_4$$
and
$$ o**o***o\quad\longleftrightarrow\quad  x_0^0x_1^2x_2^3x_3^0 = x_1^2x_2^3. $$
Hence the number of monomials of exact degree $n$ in $k+1$ variables is $k+n$ (the number of stars) choose $k$ (the choice of stars to change to circles). Conclusion:
$$
  \text{There are $\binom{k+n}{k}$ monomials $x_0^{e_0}\cdots x_k^{e_k}$
      with $e_0+\cdots+e_k=n$.}
$$
(This differs from Wolfgang's answer by 1 because I include the monomial of degree $0$, i.e., the constant monomial as being a monomial.)
A: I found another combinatorial proof that does not use complex sums or the well-known stars and bars technique.
I consider $n$ variables and maximum degree $d$. I will show that the number of monomials of degree less than or equal to $d$ (including the monomial 
1 that you excluded from your example) is $${n+d}\choose{d}$$
Consider the following set 
$E=\{x_1,~x_2,\dots x_n,~c_1,~c_2,\dots c_d\}$ of cardinal $n+d$. I will show that any monomial of degree less than or equal to $d$ corresponds to choosing $d$ elements from this set.
Choosing some
$x_{i_1},~x_{i_2},\dots x_{i_k}$ amounts to building an initial expression $e=x_{i_1}x_{i_2}\dots x_{i_k}$ (or $e=1$ 
if no $x_i$ term is chosen). Then, choosing some 
$c_j$ amounts to the following: (i) if the $j^\text{th}$ factor of $e$ exists, copy (insert) it at position $j+1$
or (ii) if the $j^\text{th}$ factor of $e$ does not exist ($e$ is shorter), do not modify $e$. Any 
monomial of degree less than or equal to $d$ can be expressed as a combination of $d$ elements 
from above set $E$. We give a few examples:


*

*$x_1$ corresponds to choosing $\{x_1,~c_2,~c_3,\dots c_d\}$. We start with expression
$e=x_1$ and the copying elements $c_2,~c_3,\dots c_d$ do not modify $e$ because $e$ has no factors at positions $2,~3,\dots d$.

*$x_1^2x_2$ corresponds to choosing $\{x_1,~x_2,~c_1,~c_4,~c_5,\dots c_d\}$. Indeed, we first
have the expression $e=x_1x_2$; then, $c_1$ will insert a copy of $x_1$ at position 2 to obtain
$e=x_1x_1x_2$. The $c_4$ element does not change $e$, because $e$ has no factor at position $4$ in $e$.
Same applies to $c_5,~c_6\dots c_d$, and so, the final $e$ is $e=x_1x_1x_2$.

*$x_5x_7^3x_9$ corresponds to choosing $\{x_5,~x_7,~x_9,~c_2,~c_3,~c_6,~c_7,\dots c_d\}$.
We start with $e=x_5x_7x_9$ and $c_2$ inserts at position $3$ a copy of the second element $x_7$, leading
to $e=x_5x_7x_7x_9$. Then, $c_3$ duplicates the third element $x_7$, generating 
$e=x_5x_7x_7x_7x_9$. Elements $c_6,~c_7,\dots c_d$ will perform no modification on $e$ because $e$ has
no factor at positions $6,~7,\dots d$.

*$x_7^{d}$ corresponds to choosing $\{x_7,~c_1,~c_2,\dots c_{d-1}\}$. Indeed, we start with 
$e=x_7$ and $c_1$ duplicates $x_7$ leading to $x_7x_7$. Then $c_2$ duplicates the second term, leading
to $x_7x_7x_7$. Applying this for all $c_1,~c_2,\dots c_{d-1}$, we obtain that $x_7$ is duplicated 
$d-1$ times, and so, the final expression is $\underbrace{x_7x_7\dots x_7}_{d\text{ times }}$.

*$x_7^2x_9^{d-2}$ corresponds to choosing $\{x_7,~x_9,~c_1,~c_3,~c_4,~\dots c_{d-1}\}$. We
start with $e=x_7x_9$ and $c_1$ duplicates $x_7$ leading to $e=x_7x_7x_9$. Since $c_2$ is not chosen, $x_7$
is not duplicated again. On the other hand, $x_9$ is duplicated in cascade $d-3$ times and we obtain
$e=x_7x_7\underbrace{x_9x_9x_9\dots x_9}_{d-2\text{ times }}$.

*$1$ corresponds to choosing $c_1,~c_2,\dots c_d$.

A: The N degree polynomial having n variables and having maximum number of terms in equation is obtained by multiplying N linear equations of n variables each. The maximum number of terms is given as 
((N+1) x (N+2)  x (N+3) …….(N+n)) / n!
