1
$\begingroup$

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 $$ How do I do this? Thanks for answering.

$\endgroup$
  • $\begingroup$ Have you made any approaches to solve this problem? $\endgroup$ – user68386 Dec 12 '15 at 16:36
  • $\begingroup$ it is just the sum of the complete homogeneous symmetric polynomials. en.wikipedia.org/wiki/Complete_homogeneous_symmetric_polynomial $\endgroup$ – Wolfgang Dec 12 '15 at 16:58
  • $\begingroup$ Thanks for answering. What I've tried was writing some of them down and and trying to see if I could derive some calculation, but I failed. I also read the Wiki page about polynomial degrees. $\endgroup$ – raichu Dec 12 '15 at 17:07
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Clever idea to introduce $x_0$. Nice! $\endgroup$ – Wolfgang Dec 12 '15 at 18:36
  • $\begingroup$ @Wolfgang Not my idea, of course. I saw this in some long-ago algebra class, and the professor there presumably had himself seen it in some even longer-ago algebra (or combinatorics) class. $\endgroup$ – Joe Silverman Dec 12 '15 at 19:30
0
$\begingroup$

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.