Number of polynomial terms for certain degree and certain number of variables [closed]

Question

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.

Answer 1

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.

Answer 2

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.)

Answer 3

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$.

Answer 4

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!