1

I have worked about a result and want to know if there are better ways of proving the following:

$$N^M - (N-1)^M$$ $$=\binom{N}{1}(N-1)^{M-1} + \binom{N}{2} (N-1)^{M-2} + \binom{N}{3} (N-1)^{M-3} + \cdots +\binom{N}{M}(N-1)^{M-M}.$$

Algebraic Pavel
  • 22,928
Seetha Rama Raju Sanapala
  • 171

2 Answers2

2

This is the expansion of $N^M=((N-1)+1)^M$, if you adjust the $(N,C,k)$ to $(M,C,k)$

Empy2
  • 50,853
1

We give a combinatorial interpretation, with the $\binom{N}{k}$ replaced by the correct $\binom{M}{k}$.

We have $N$ kids, one of whom is George, and $M$ distinct presents. We want to count, in two different ways, the number of ways to give out the presents, with George getting at least $1$ present.

Way $1$: There are $N^M$ ways to distribute the presents. There are $(N-1)^M$ ways to distribute the presents among the $N-1$ non-Georges. So there are $N^M-(N-1)^M$ ways to not shut George out.

Way $2$: George may get anywhere from $1$ to $M$ presents. We count the number of ways to distribute the presents so Geoge gets $k$. The $k$ presents George gets can be chosen in $\binom{M}{k}$ ways. For each such way, the remaining $M-k$ presents can be distributed among the remaining kids in $(N-1)^{M-k}$ ways. So there are $\binom{M}{k}(N-1)^{M-k}$ ways to distribute the presents so George gets $k$. Now sum from $k=1$ to $k=M$.

André Nicolas
  • 507,029
  • Can some one tell me how to write the math symbols here? I know how to write math equations in Microsoft Word but not here. – Seetha Rama Raju Sanapala Jun 24 '14 at 17:46
  • I have arrived at the result using similar arguments but not exactly the same. N^M is the number of you can form M-long words with N symbols and repetitions allowed. It should equal the sum of number of M-long words without a particular symbol say the first symbol, then the number of M-long words with the first symbol exactly once, the the number of M-long words with the first symbol appearing twice, the number of words with the symbol appearing 3 times so on. – Seetha Rama Raju Sanapala Jun 24 '14 at 17:52
  • The combinatorial interpretation I wrote is then not at all new to you. What you had found is mathematically the same as my answer, the "story" just has different characters. – André Nicolas Jun 24 '14 at 19:11