4
$\begingroup$

I'm going to university in October and thought I'd have a go at a few questions from one of their past papers. I have completed the majority of this question but I'm stuck on the very last part. In honesty I've been working on this paper a while now and I'm a bit tired so I'm probably giving up earlier than I usually would.

I won't write out the full question, only the last part:

Let $$S_r(n) = \sum_{m=0}^n\ (-1)^m m^r {n \choose m}$$ where r is a non-negative integer . Show that $S_r(n)=0$ for $r<n$. Evaluate $S_n(n)$.

I have shown that $S_r(n)=0$ for $r<n$ by taking $(1+z)^n= \sum_{m=0}^n\ z^m {n \choose m}$, letting $D_r(f(z))=z\frac d{dz}(z\frac d{dz}...(\frac d{dz}(f(z)))...)$ where $z\frac d{dz}$ is applied $r$ times and applied it to both sides. The left hand side gives a polynomial, degree n which has factor $(1+z)$ for all $r<n$ and the right hand side gives $\sum_{m=0}^n\ z^m (m)^r {n \choose m}$. Setting $z=-1$ yields the required result.

There is some build up to this, so I'm fairly certain that this was the intended method.

I'm stuck however on the very last part. I have tried finding a form for $D_r((1+z)^n)$, but I'm fairly sure that this isn't the correct approach, as the wording of the question implies that $S_n(n)$ needs to be considered separately.

I'm surprised that I didn't find that this question had already been asked, so apologies if it has been.

Thank you.

$\endgroup$
  • $\begingroup$ Looks like a close relative of Stirling numbers of the second kind. Please see Wikipedia. $\endgroup$ – André Nicolas Jul 7 '16 at 22:01
  • $\begingroup$ Ok thanks, will do $\endgroup$ – Aka_aka_aka_ak Jul 7 '16 at 22:12
  • $\begingroup$ You are welcome. Note the close relationship to the number of onto functions. The calculation you carried out successfully (and that I would have trouble with) can be bypassed once we note there are $0$ onto functions from an $r$-element set to an $n$-element set if $r\lt n$. $\endgroup$ – André Nicolas Jul 7 '16 at 22:23
2
$\begingroup$

The following relation encapsulates the Stirling number semantics:

$$m^r = r! [z^r] \exp(mz).$$

This yields for your sum

$$S_r(n) = r! [z^r] \sum_{m=0}^n {n\choose m} (-1)^m \exp(mz) = r! [z^r] (1-\exp(z))^n.$$

Now observe that

$$1-\exp(z) = - z - \frac{z^2}{2} - \frac{z^3}{6} -\cdots$$

which means that $(1-\exp(z))^n$ starts at $[z^r]$ where $r=n$ with coefficient $(-1)^n$, producing for the sum the value

$$(-1)^n\times n!$$

and the coefficients on $[z^r]$ with $r\lt n$ are zero.

$\endgroup$
2
$\begingroup$

The general form of the summation

$$\sum_{m=0}^n(-1)^mm^n\binom{n}m\;,\tag{1}$$

with the alternating sign and the binomial coefficient $\binom{n}m$, suggests that it can be interpreted as an inclusion-exclusion calculation. However, the $m=0$ term is $0$, from which we begin by subtracting a positive quantity $\binom{n}1=n$, which is a bit odd for such a calculation. This suggests letting $k=n-m$ and rewriting as

$$\sum_{k=0}^n(-1)^{n-k}(n-k)^n\binom{n}{n-k}=(-1)^n\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n\;,$$

where the righthand side has been arranged to look like a more or less typical inclusion-exclusion calculation. The factor $(n-k)^n$ is the one that isn’t part of the inclusion-exclusion machinery. It has a natural interpretation as the number of functions from $[n]$ to $[n]$ whose ranges are disjoint from some $k$-element subset of $[n]$. If for each $k\in[n]$ we let $F_k$ be the set of functions from $[n]$ to $[n]$ whose ranges do not contain $k$, we have

$$\left|\bigcap_{k\in I}F_k\right|=(n-|I|)^n$$

whenever $\varnothing\ne I\subseteq[n]$, so

$$\begin{align*} \left|\bigcup_{k=1}^nF_k\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|-1}\left|\bigcap_{k\in I}F_k\right|\\ &=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|-1}(n-|I|)^n\\ &=\sum_{k=1}^n(-1)^{k-1}\binom{n}k(n-k)^n\;. \end{align*}$$

This is the number of functions from $[n]$ to $[n]$ that are not surjective, i.e., the number that aren’t bijections. It follows that the number of bijections from $[n]$ to $[n]$ is

$$n^n-\sum_{k=1}^n(-1)^{k-1}\binom{n}k(n-k)^n=\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n\;.$$

On the other hand, we know that there are $n!$ bijections from $[n]$ to $[n]$, so

$$\sum_{m=0}^n(-1)^mm^n\binom{n}m=(-1)^n\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^n=(-1)^nn!\;.$$

Note that the same basic argument handles the previous part of the problem. The factor $(n-k)^n$ is replaced by $(n-k)^r$, the number of functions from $[r]$ to $[n]$ whose ranges are disjoint from some specified $k$-element subset of $[n]$. The expression

$$\sum_{k=0}^n(-1)^k\binom{n}k(n-k)^r$$

counts the surjective functions from $[r]$ to $[n]$, and if $r<n$, this is of course $0$.

All of this is very closely related to the Stirling numbers of the second kind.

$\endgroup$
  • $\begingroup$ @BrianMScott: Very nice and clearly written exposition. (+1) $\endgroup$ – Markus Scheuer Jun 30 '18 at 16:51

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.