Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Wikipedia says that the number of different homogeneous monomials of degree $M$ in $N$ variables is $$\frac{(M+N-1)!}{M!(N-1)!}\; .$$ Can anyone explain why this is true?

share|improve this question

2 Answers 2

It's counted by a method known as stars and bars.

Think of it this way, you have $M$ 'powers' that you can assign with repetition to any of the $N$ variables. Lay out your $M$ 'powers' in a line. Then you choose to insert $N-1$ bars between different powers. Each bar marks a cut off, so for your first bar, all the powers to the left will be applied to the first of $N$ variables, and then all the powers to the right of the first bar and the the left of the second bar will be the powers applied to the second of the $N$ variables and so on.

There are $\binom{M+N-1}{N-1}$ to do this, as you essentially have $M+N-1$ spots to put your $M$ powers and $N-1$ bars, and you choose $N-1$ spots to put down your bars, and fill all the remaining spots up with powers. But $\binom{M+N-1}{N-1}=\frac{(M+N-1)!}{M!(N-1)!}$, and you get your formula.

share|improve this answer

Represent say $x_1^3 x_2^2 x_4^2 x_5$ ($N=5,M=8$) by $***|**||**|*$. Out of $M+N-1$ places we need to choose $N-1$ $|$'s (or $M$ $*$'s) - so we get $M+N-1$ -choose- $N-1$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.