13
$\begingroup$

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

$\endgroup$
17
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
12
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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