# Number of elements in polynomial of degree n and m variables

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.

• 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 Sep 25, 2018 at 13:30
• @Henry Correct. Thanks for the correction. Sep 25, 2018 at 15:31

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.
• Amazing. This is the solution. The trick of setting $x_m=1$ was gorgeous! Sep 25, 2018 at 13:09