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 1 The 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 2 The 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 3 The 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