Are there any identities for alternating binomial sums of the form $\sum_{k=0}^{n} (-1)^{k}k^{p}{n \choose k} $?

Question

In equations (20) - (25) of Mathworld's article on binomial sums, identities are given for sums of the form $$\sum_{k=0}^{n} k^{p}{n \choose k}, $$ with $p \in \mathbb{Z}_{\geq 0}$. I wonder whether identities also exist for the alternating counterparts: $$\sum_{k=0}^{n} (-1)^{k}k^{p}{n \choose k} .$$ Furthermore, I'm interested in results for the same sum that is “cut off”, i.e. when the summands go from $k=0$ to some $D<n$.

Answer 1

A rewrite of formula (10) on MathWorld (replacing the summation index $k-i\mapsto i$) gives the desired formula: $$\sum_{k=0}^{n} (-1)^{k}k^{p}{n \choose k} =(-1)^n n! S_2(p,n),$$ where $S_2(p,n)$ is the Stirling number of the second kind (the number of ways of partitioning a set of $p$ elements into $n$ non-empty subsets).
It is remarkable that the alternating sum equals zero for $p<n$.

Answer 2

For the cutoff version:

---

We can get a subtraction-free formula for the cutoff version, which should be sufficient to get asymptotics, by the same idea that gives a simple bijective proof of the identity that Carlo Beenakker mentioned. That is:

$k^p$ counts maps from a $p$-element set $[p]$ to a $k$-element set

Thus $\binom{n}{k} k^p$ counts pairs of a $k$-element subset $S$ of an $n$-elements set $[n]$ with a map from $[p]$ to $S$. In other words, it counts maps $f$ from $[p]$ to $[n]$ together with a $k$-element subset $S$ of $[n]$ containing the image of $f$.

So $\sum_{k=0}^d (-1)^k \binom{n}{k} k^p$ is the sum over maps $f: [p] \to n$ of the sum over subsets $S$ of $[n]$, containing the image of $f$, of size at most $k$, of $(-1)^{|S|}$. We may assume the image of $f$ has size $\leq d < n $ and thus that there is some element $e$ not in the image of $f$. We can cancel each subset with $e\notin S$ with the $S \cup \{e\}$, as these have opposite signs. The only subsets that fail to cancel are those that have size exactly $d$ and do not contain $e$, of which there are $\binom{n - | \operatorname{Im}(f) | -1}{ d - |\operatorname{Im}(f)| } $.

With $S_2(p,j)$ again the Stirling numbers of the second kind, the number of maps from $[p]$ to $[n]$ with image of size $j$ is $ \frac{n!}{ (n-j)!} S_2(p,j) $, so the sum is

$$ (-1)^d \sum_{j=0}^d S_2(p,j) \frac{n!}{(n-j)!} \binom{ n-j-1}{d-j} $$

$$= (-1)^d \frac{n!}{ (n-1-d)!} \sum_{j=0}^d S_2(p,j) \frac{1}{(n-j)} \frac{1}{(d-j)!} $$

(If $d=n$ then all subsets cancel and so only the terms with $| \operatorname{Im} f| =n$ remain, so we just obtain the count of surjections from $[p]$ to $[n]$, as in Carlo Beenakker's answer.)

---

Alternately, a formula-based proof:

we have $$ k^p = \sum_{j=0}^k S_2( p,j) \frac{k!}{ (k-j)!} $$ ( a standard identity.) so

$$\sum_{k=0}^d (-1)^k k^p {n \choose k} = \sum_{j=0}^d \sum_{k=j}^d (-1)^k S_2( p,j) \frac{k!}{(k-j)!} {n \choose k} $$ and $$\frac{k!}{(k-j)!}{n\choose k} = \frac{k! n!}{ (k-j)! k! (n-k)! } = \frac{n!}{ (k-j)! (n-k)!} = \frac{n!}{(n-j)!} \binom{n-j}{k-j} $$ so $$ \sum_{k=0}^d (-1)^k k^p {n \choose k} = \sum_{j=0}^d \sum_{k=j}^d (-1)^k S_2( p,j) \frac{n!}{(n-j)!} \binom{n-j}{k-j}$$ $$ = \sum_{j=0}^d (-1)^d S_2( p,j) \frac{n!}{(n-j)!} \binom{n-j-1}{d-j} = (-1)^d \frac{n!}{ (n-1-d)!} \sum_{j=0}^d S_2(p,j) \frac{1}{(n-j)} \frac{1}{(d-j)!} $$

Answer 3

Up to the factor $(-1)^n$, the uncut sum is $$s_{p,n}:=\sum_{k=0}^n(-1)^{n-k}\, k^p\,\binom nk.$$ As noted in the comment by Richard Stanley, $$s_{p,n}=(\Delta^n f_p)(0),$$ where $f_p(x):=x^p$ and $(\Delta f)(x):=f(x+1)-f(x)$. Here and in what follows, $x$ denotes any real number.

It is easy to check by induction on $n$ that for any smooth enough function $f$ we have $$(\Delta^n f)(x)=Ef^{(n)}(x+S_n),$$ where $f^{(n)}$ is the $n$th derivative of $f$, $S_n:=U_1+\cdots+U_n$, and $U_1,\dots,U_n$ are independent random variables uniformly distributed on the interval $[0,1]$. So, $$s_{p,n}=n!\binom pn ES_n^{p-n} \tag{1}$$ for $p=0,1,\dots$ and $n=0,1,\dots$. In particular, it follows that $s_{p,n}=0$ for $n=p+1,p+2,\dots$, as noted in the answer by Carlo Beenakker.

In fact, (1) holds for all real $p\ge n$ (and $n=0,1,\dots$), and then, obviously, $$0<s_{p,n}\le n!\binom pn n^{p-n}. \tag{2}$$

If $p-n\ge1$, then, in view of Jensen's inequality, the lower bound $0$ on $s_{p,n}$ in (2) can be greatly improved, to $$b_{p,n}:=n!\binom pn \Big(\frac n2\Big)^{p-n}.$$

Moreover, by the law of large numbers, $S_n/n\to1/2$ in probability (say). Also, $0\le S_n/n\le1$. So, by dominated convergence, from (1) we immediately get the following asymptotics: if $n\to\infty$ and $p-n\to a$ for some real $a>0$, then $$s_{p,n}\sim b_{p,n}.$$

Answer 4

You can find plenty of documentation on Gould's site. Maybe it could be useful. The link is https://math.wvu.edu/~hgould/ Interesting files are Vol.1.PDF to Vol. 8.PDF.