Alternating binomial sum of $i^a(n-i)^b$

Question

I would like to know of value (if not, asymptotic growth in $n,a,b$) of the following alternating sum: $$\sum_{i=0}^n(-1)^i\binom{n}{i}i^a(n-i)^b.$$ Here $a$ and $b$ are natural numbers. When $a+b\leq n$, the above sum is zero. What about $a+b>n$? For instance, I'm especially interested in the case when $a=b=n$. Thanks.

Answer 1

Luckily when $a=b=n$ and $n$ is odd the sum is zero:

$$S_n=\sum_{k=0}^{n} (-1)^k {n \choose k}~ k^n ~ (n-k)^n$$ replace $k$ by $n-k$ (summing backwards), then $$S_n=\sum_{k=0}^{n} (-1)^k {n \choose n-k}~(n-k)^n ~ k^n=(-1)^n S_n.$$ So when $n$ is odd $S_n=0$

Answer 2

Let ${n \brace k}$ denote the $(n,k)^{th}$ Stirling number of the second kind, equal to the number of partitions of a set of size $n$ into $k$ parts. We can show that the sum evaluates to $$ n!\sum_{k=0}^n(-1)^k{a \brace k}{b \brace n-k} $$

---

Let $[n]$ denote $\{1,\dots,n\}$.

The summation $\sum_{i=0}^n \binom{n}{i} (-1)^i i^a(n-i)^b$ enumerates tuples $(I,f,g)$, where

• $I\subseteq [n]$,

• $f$ is a function from $[a]$ to $I$,

• $g$ is a function from $[b]$ to $[n]\setminus I$,

and where the contribution of a tuple is $(-1)^{|I|}$. Consider the following sign-reversing involution defined on the set of tuples $(I,f,g)$:

Given $(I,f,g)$, let $m$ be the smallest element of $[n]\setminus (\text{im }f\cup \text{im }g)$. (If $[n]\setminus (\text{im }f\cup \text{im }g)$ is empty, the involution is undefined). Then the involution is $$(I,f,g)\longleftrightarrow (I\oplus \{m\},f,g),$$where $\oplus$ is the symmetric difference of sets. That is, if $m\in I$, remove it, and if $m\notin I$, then add it.

This involution divides the set of tuples $(I,f,g)$ into pairs which cancel out in $\sum_{i=0}^n\binom{n}i (-1)^ii^a(n-i)^b$, so anything in the domain of the involution contributes nothing to the sum. What remains are pairs $(I,f,g)$ where $f:[a]\to I$ is surjective and $g:[b]\to ([n]\setminus I)$ is surjective. The number of surjective functions $f:[a]\to I$ is $|I|!\cdot {a\brace |I|}$. Therefore, $$ \sum_{i=0}^n\binom{n}i(-1)^ii^a(n-i)^b =\sum_{I\subseteq [n]} (-1)^{|I|}\cdot|I|!{a\brace |I|}\cdot (n-|I|)!{b\brace n-|I|}\\ \phantom{\sum_{i=0}^n\binom{n}i(-1)^ii^a(n-i)^b} =n!\sum_{i=0}^n(-1)^i{a\brace i}{b\brace n-i} $$

---

In particular, with $a=b=n$, we get $$ n!\sum_{i=0}^n (-1)^i {n\brace i}{n\brace n-i} $$ but I cannot determine the asymptotic of this sequence. It is not even in OEIS...