Maximum Number of Terms in a Homogeneous Polynomial of m Variables and Degree n

[danoonez]

I'm having a problem with a proof I came across in one of my calculus books but it's not the calculus part of the proof that I'm having trouble with. Here's the actual proof:

"Prove: The number of distinct derivatives of order n is the the same as the number of terms in a homogeneous polynomial in m variables of degree n"

I've got a good idea about how to prove the part about the "number of distinct derivatives," so here, finally, is MY actual problem:

Prove that the maximum number of terms possible in a homogeneous polynomial of m variables and degree n is given by

\frac {(n + m -1) !} {n ! (m - 1) !}<br />


Let me know if it needs further explanation; I may not have done a good job explaining my problem.

 

[Hurkyl]

Ah, counting, I like counting!

You have n factors, each of which is one of m variables, and the order doesn't matter. (xxy and xyx aren't distinct)

There are a couple of ways of modelling such problems. One way is as balls in boxes:

You have n balls you want to distribute amonst m boxes. How many different arrangements are there?

Though, I think what you want to do is to sort the factors, and partition them into m groups, so the first group corresponds to the first variable, the second group to the second variable, etc. Then, you can ask the question:

I have n objects. How many ways can I place m-1 dividers into these objects, partitioning them into m distinct (possibly empty) groups?

Actually, this problem is easier to solve if you can convert it into a similar problem where each group has at least one element...

 

[danoonez]

The balls in the boxes is an interesting (new to me) way to look at it. I'll give that a try and see if I can make any progress. Thanks.

 

[mathwonk]

this seems like a tautology to me. a derivative of degree n is determined, since the order of differentiation is unimportant (with a few hypotheses), by choosing which of the m variables to differentiate wrt, and a total of n of them. that is exactly what it means to choose a monomial of degree n in m variables.

i.e. there is nothing to prove.