For fixed positive integers $m$ and $n$, let $$S=\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n.$$Show that $S = 0$ if $n < m$ and $S = n!$ if $n = m$.

I know that I have to use PIE(principle of inclusion and exclusion) and a counting argument. Here's my work so far:

There are $m$ people, $\binom{m}{k}$ represents all the ways to pick $k$ people out of $m$ people. $(m-k)^n$ represents all the ways of giving the people that weren't chosen nn distinguishable objects. What I don't get is how to apply PIE, why the signs are alternating, and how does $S = 0$ if $n < m$ and $S = n!$ if $n = m$. Could anyone offer an answer by the counting argument I started? Thanks!

  • $\begingroup$ Notice: $$\text{S}=\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n=m!\cdot\mathcal{S}_{n}^{(m)}$$ Where $\mathcal{S}_{n}^{(m)}$ is the Stirling number of the second kind. mathworld.wolfram.com/StirlingNumberoftheSecondKind.html $\endgroup$ – Jan Aug 15 '16 at 18:14
  • $\begingroup$ I’ve updated my earlier answer by adding a link to an answer that shows in considerable detail the operation of the PIE. Try to combine it with the informal explanation in the first link that I gave, and if you get stuck, let me know where, and we’ll try to sort it out. $\endgroup$ – Brian M. Scott Aug 15 '16 at 18:20

HINT: Show that $S$ is the number of surjections from $[n]=\{1,\ldots,n\}$ to $[m]=\{1,\ldots,m\}$ counted using an inclusion-exclusion argument. The crucial observation is that for any $I\subseteq[m]$, there are $(m-|I|)^n$ functions from $[n]$ to $[m]$ whose ranges are disjoint from $I$.

If you get stuck, this answer gives an informal explanation, this answer contains a detailed explanation (in the context of a slightly different question), and this answer contains an even more detailed answer to a different but similar question, showing in more detail the application of the inclusion-exclusion principle.

  • $\begingroup$ Wait, I'm having a hard time understanding what you're talking about, so let's start slow. Okay, am I correct so far on the counting arguement(I edited the question)? $\endgroup$ – user359548 Aug 15 '16 at 18:58
  • $\begingroup$ @MathMuse: The statement that you make about $\binom{m}k$ is correct, but it doesn’t really get you anywhere. It looks to me as if the fundamental problem is that you don’t understand how the inclusion-exclusion principle works. The first answer to which I linked gives a very informal explanation of the idea, and the last shows in detail how an inclusion-exclusion argument can be carried out for a similar question. The former gives some idea of why such arguments work; the latter shows how the details work even if one is merely going through them mechanically. And the very first link ... $\endgroup$ – Brian M. Scott Aug 15 '16 at 19:03
  • $\begingroup$ ... in the answer is to the form of the inclusion-exclusion theorem that is most useful here. $\endgroup$ – Brian M. Scott Aug 15 '16 at 19:03
  • $\begingroup$ @MathMuse: You're welcome! $\endgroup$ – Brian M. Scott Aug 16 '16 at 18:55
  • $\begingroup$ Brian, could you also help me on math.stackexchange.com/questions/1894215/…? Thanks! $\endgroup$ – user359548 Aug 16 '16 at 19:02

Your Answer

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