10
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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

$\endgroup$
1
  • 11
    $\begingroup$ It's not so remarkable that the alternating sum is zero for $p<n$. The sum is the $n$th difference at 0 of a polynomial of degree $p$. For any polynomial of degree $p$, the $p$th difference is constant and the $n$th difference for $n>p$ is 0. $\endgroup$ Aug 30 '20 at 21:48
10
$\begingroup$

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)!} $$

$\endgroup$
1
  • $\begingroup$ Thank you! It is at times like these that I wish I could accept two answers. $\endgroup$
    – Max Muller
    Aug 31 '20 at 11:12
6
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0

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.