I would like to record a few propositions about number of monomials of a given degree in the ring of polynomials in several variables. We begin with a basic counting problem: suppose we have boxes and balls—how many ways can we place the balls in the boxes? The boxes may be empty, or they may contain any number of balls, we only require that all are placed. There is a clever way of reducing this problem to the easier problem of counting the number of ways to select items out of a larger set.

Proposition 1The number of ways to place balls into boxes is .

*Proof:* We will represent the problem typographically, using vertical bars to form the boxes, and representing the balls by dots. Thus if and , one arrangement might look like , where the first box contains one ball, the second box is empty, and the last box contains three balls.

Notice that we have symbols. Since the first and last symbols are always lines, out of the inside symbols, we must choose of these to be dots. The number of ways to choose dots out of symbols is , and since every choice of dots corresponds to a way of placing balls into boxes, our desired count is .

With this proposition in hand, we can proceed to counting monomials. First, let’s recall some definitions. Let be any commutative ring (e.g. the integers ), and let be the ring of polynomials over in variables. A monomial in is a product of the variables: . The degree of a monomial is the sum of its exponents: . For example, the monomials of degree three in are , , , and .

First we count monomials of fixed degree.

Proposition 2The number of monomials in of degree is .

*Proof:* We can reduce the problem of counting monomials to the problem of counting balls in boxes. We create a box for each variable, and we let the degree of each variable be the number of balls in its box. Using the example from before, if and , a possible arrangement is , which corresponds to the monomial . Of course we could use the monomial to place balls in boxes, so the two counting problems are equivalent. Hence the number of monomials in of degree is , the number of ways to place balls in boxes.

Next we’ll count the number of monomials of degree less than or equal to .

Proposition 3The number of monomials in of degree less than or equal to is .

*Proof:* Again we reduce the problem of counting monomials to the problem of counting balls in boxes, but this time we add an extra box to get the monomials of lower degree. So if and , a possible arrangement is , which corresponds to . Notice that the dot in the last box isn’t counted, so our monomial is degree three instead of degree four. Since we have boxes and balls, the number of possibilities is , as desired.

We also could have proved this using the previous proposition by noting that the number of monomials in variables of degree less than or equal to is the same as the number of monomials in variables of degree equal to . To get from the monomials of degree in variables to the monomials of degree at most in variables, we simply substitute 1 into the last variable. To get back the other way we must “homogenize.” For example, goes to the degree 5 monomial .

The last two propositions yield a nice corollary. Since the number of monomials in variables of degree less than or equal to is the sum of the number of monomials of degree equal to , we have a combinatorial proof of the identity

## 3 comments

Comments feed for this article

August 29, 2012 at 9:13 pm

Short Proofs of Two Hard Theorems « murphmath[…] Let be the least integer such that . By elementary combinatorics, the number of monomials in of degree at most is , so a polynomial in with variable […]

March 21, 2015 at 9:08 pm

The Kakeya problem | Anurag's Math Blog[…] with degree at most form a dimensional subspace of the infinite dimensional vector space (see this for a complete reasoning). Now look at the evaluation map from to for any given set , which maps […]

March 20, 2016 at 9:59 pm

Anurag BishnoiHere is another neat way of counting monomials. To find the number of monomials in n-variables of degree d, we will find the number of ways of choosing a d-element multi-subset of {1, 2, …, n}, where we correspond the exponent of x_i with the number of occurrences of i in the multiset. Write the elements of such a multiset in sorted order as a_1 <= …. <= a_d. Then define b_i = a_i + i – 1, to get numbers b_1 < … < b_d from the set {1, 2, …, n + d – 1}. Show that this defines a bijection between d-element multi-subsets of {1, 2, …, n} and d-element subsets of {1, 2, …, n + d – 1}.