7
$\begingroup$

How many unique terms does a polynomial of degree $n$ and $m$ variables have?

For instance, a polynomial of degree 1 and $m$ variables has $m$ terms:

$$ f(x_1,...,x_m) = \sum_{i=1}^m a_ix_i $$

Similarly, a polynomial of degree $n$ and 1 variable has $n$ terms:

$$ f(x) = \sum_{i=1}^n a_ix^i $$

A polynomial of degree 2 and 2 (3) variables has 5 (9) terms. A polynomial of degree 3 and 2 variables has 9 terms.

I've tried to find a pattern so that the above can be formalised using combinatorics-related functions, but so far have utterly failed. Any hints?

PS: naturally, we have to add 1 to all the above, to consider the trivial case of a constant term.

$\endgroup$
2
  • 1
    $\begingroup$ You say "A polynomial of degree 2 and 2 (3) variables has 5 (8) terms. A polynomial of degree 3 and 2 variables has 9 terms." I suppose you mean things like $x^2+y^2+xy+x+y$ and $x^2+y^2+z^2+xy+xz+yz+x+y+z$ and $x^3+y^3+x^2y +y^2x + x^2 +y^2+xy+x+y$. The second of these actually has nine terms rather than eight. As you say, all of them could have one extra constant term, and this would give Joppy's ${n+m \choose m}$ result $\endgroup$
    – Henry
    Sep 25, 2018 at 13:30
  • $\begingroup$ @Henry Correct. Thanks for the correction. $\endgroup$
    – luchonacho
    Sep 25, 2018 at 15:31

1 Answer 1

11
$\begingroup$

Let me solve something more specific: how many monomials of degree $n$ can be made using the variables $x_1, \ldots, x_m$? A monomial of degree $n$ is a product of $n$ of the $x_i$, with repetition allowed. For example, $x_1^3 x_2^2 x_3$ and $x_1 x_4^5$ are both monomials of degree $6$.

A monomial of degree $n$ is uniquely represented by a list of natural numbers $(l_1, \ldots, l_m)$ such that $l_1 + \cdots + l_m = n$. For example, if we are using the variables $x_1, \ldots, x_4$, then $x_1^3 x_2^2 x_3$ can be represented by $(3, 2, 1, 0)$, and $x_1 x_4^5$ can be represented by $(1, 0, 0, 5)$. So counting the monomials of degree $n$ is equivalent to counting these lists of length $m$ adding up to $n$. (These are called compositions of $n$ with $m$ parts, if you would like to google around). Now you have to get a bit creative to count how many ways there are to do this.

Continuing with this example where $m = 4$ and $n = 6$, one of these lists is equivalent to the placement of $m - 1 = 3$ bars between $n = 6$ dots. Each of these bars-and-dots lists comes from choosing exactly $m-1$ dots out of $n + m - 1$ dots to "turn into a bar". For example, $$ \begin{aligned} (3, 2, 1, 0) &= [\bullet \bullet \bullet \mid \bullet\, \bullet \mid \bullet \mid ] &= [\bullet \bullet \bullet \color{red} \bullet \bullet \bullet \color{red} \bullet \bullet \color{red} \bullet ] \\ (1, 0, 0, 5) &= [\bullet \mid \mid \mid \bullet \bullet \bullet \bullet \bullet ] &= [\bullet \color{red} \bullet \color{red} \bullet \color{red} \bullet \bullet \bullet \bullet \bullet \bullet ] \end{aligned}$$ So the number of lists of length $m$ whose entries add up to $n$ is equivalent to the number of ways of colouring $m-1$ dots red out of $n + m - 1$ dots, which is $$ \binom{n + m - 1}{m - 1} = \binom{n + m - 1}{n}$$ We can quickly check an example: if $n = 3$ and $m = 3$, the formula gives $\binom{5}{2} = 10$, which agrees with the listing $$x^3, y^3, z^3, x^2 y, x^2 z, y^2 z, xy^2, xz^2, yz^2, xyz$$ of degree $3$ monomials in the variables $x, y, z$.

If you want to allow lower terms as well (since a polynomial of degree $3$ is allowed to have terms like $xy$), you can do a neat trick where you include one extra variable $x_{m + 1}$, for a total of $\binom{n + m}{m}$ monomials of degree $n$ in the variables $x_1, \ldots, x_{m+1}$, and then set $x_{m+1} = 1$, which will get you all monomials of degree at most $n$ in the variables $x_1, \ldots, x_m$. In the example above of the monomials in $x,y,z$, setting $z = 1$ gets $$x^3, y^3, 1, x^2 y, x^2, y^2, xy^2, x, y, xy$$ and you can check that every monomial in $x, y$ of degree at most $3$ appears in that list once.

$\endgroup$
1
  • 1
    $\begingroup$ Amazing. This is the solution. The trick of setting $x_m=1$ was gorgeous! $\endgroup$
    – luchonacho
    Sep 25, 2018 at 13:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .