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 {n} boxes and {k} 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 {k} are placed. There is a clever way of reducing this problem to the easier problem of counting the number of ways to select {k} items out of a larger set.

Proposition 1 The number of ways to place {k} balls into {n} boxes is {{n+k-1\choose k}}.

Proof: We will represent the problem typographically, using {n+1} vertical bars to form the boxes, and representing the balls by dots. Thus if {n=3} and {k=4}, one arrangement might look like {|\bullet||\bullet\bullet\bullet|}, where the first box contains one ball, the second box is empty, and the last box contains three balls.

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

With this proposition in hand, we can proceed to counting monomials. First, let’s recall some definitions. Let {R} be any commutative ring (e.g. the integers {{\mathbb Z}}), and let {A=R[x_1,\ldots,x_n]} be the ring of polynomials over {A} in {n} variables. A monomial in {A} is a product of the variables: {x_1^{\alpha_1}\cdots x_n^{\alpha_n}}. The degree of a monomial is the sum of its exponents: {\deg(x_1^{\alpha_1}\cdots x_n^{\alpha_n})=\alpha_1+\cdots+\alpha_n}. For example, the monomials of degree three in {{\mathbb Z}[x,y]} are {x^3}, {x^2y}, {xy^2}, and {y^3}.

First we count monomials of fixed degree.

Proposition 2 The number of monomials in {A=R[x_1,\ldots,x_n]} of degree {d} is {{n+d-1\choose d}}.

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 {n=3} and {d=4}, a possible arrangement is {|\bullet||\bullet\bullet\bullet|}, which corresponds to the monomial {x_1x_3^3}. 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 {A} of degree {d} is {{n+d-1\choose d}}, the number of ways to place {d} balls in {n} boxes. \Box

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

Proposition 3 The number of monomials in {A=R[x_1,\ldots,x_n]} of degree less than or equal to {d} is {{n+d\choose d}}.

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 {n=3} and {d=4}, a possible arrangement is {|\bullet||\bullet\bullet|\bullet|}, which corresponds to {x_1x_3^2}. Notice that the dot in the last box isn’t counted, so our monomial is degree three instead of degree four. Since we have {n+1} boxes and {d} balls, the number of possibilities is {{n+d\choose d}}, as desired. \Box

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

The last two propositions yield a nice corollary. Since the number of monomials in {n} variables of degree less than or equal to {d} is the sum of the number of monomials of degree equal to {0,1,2,\ldots, d}, we have a combinatorial proof of the identity

\displaystyle  \sum_{k=0}^d{n+k-1\choose k}={n+k\choose k}.

Advertisements