Finding a closed form expression for the recurrence relation $a(n,k+1)=(k+1)^n+\sum_{m=1}^k {k+1\choose m}a(n,m)$

I originally stumbled upon this beast whilst trying to find the number of surjective functions from $[n]=\{ 1,...,n\}$ to $[k]$.

Here is my idea, denote this number $a(n,k)$ hence $a(n,k) =k^n- \#\{{f:[n]\to [k]\; | \; f \; isn't \; surjective}\}$. For every $1\leq m\leq k-1$ we have ${m\choose k}$ ways of choosing a set of $m$ elements from $[k]$ and $a(n,m)$ functions in $\{{f:[n]\to [k]\; | \; f \; isn't \; surjective}\}$ with $|im(f)|=m$ and so:

$a(n,k+1)=(k+1)^n-\sum_{m=1}^k {k+1\choose m}a(n,m)$

From here I tried to use induction to get $a(n,k+1)$ to the form of a polynomial in $a(n,1)$ which is clearly $1$, but had no luck as to finding the polynomial itself.

Solutions to the original problem or to the recurrence relation would by much appreciated.

EDIT: from the inclusion-exclusion prinicple I got the follwing expression for $a(n,k)$ which is:

$a(n,k) = \sum_{m=0}^k (-1)^m{k\choose m}(k-m)^n$

and plugging it into $a(n,k+1)=(k+1)^n-\sum_{m=1}^k {k+1\choose m}a(n,m)$ yeilds:

$a(n,k+1)=(k+1)^n-\sum_{m=1}^k{\sum_{i=0}^m {k+1 \choose k+1-m,i,m-i}(m-i)^n}$

which, to be honest, looks terrible.

My original question still stands, what is the closed-form expression (if there even is one) for this monster double sum?

Solution 1:

The Stirling number $n\brace k$ of the second kind is the number of ways to partition $[n]$ into $k$ non-empty sets. The fibres of a surjective function from $[n]$ to $[k]$ are such a partition of $[n]$, and each such partition is generated by $k!$ different surjections, one for each way of assigning the parts to the elements of $[k]$. Thus, there are $k!{n\brace k}$ surjections from $[n]$ to $[k]$.

These numbers satisfy a nice recurrence:

$${{n+1}\brace k}=k{n\brace k}+{n\brace{k-1}}$$

for $k>0$, with initial values ${0\brace 0}=1$ and ${n\brace 0}={0\brace n}=0$ for $n>0$.

They also have an explicit expression as a summation:

$${n\brace k}=\frac1{k!}\sum_{i=0}^k(-1)^{k-i}\binom{k}ii^n\,,$$

which can be derived by an inclusion-exclusion solution to your problem.

For $i\in[k]$ let $F_i$ be the set of functions $f:[n]\to [k]$ such that $i\notin\operatorname{ran}f$; clearly $|F_i|=(k-1)^n$. Thus,

$$\begin{align*} \left|\bigcup_{i\in[k]}F_i\right|&=\sum_{\varnothing\ne I\subseteq[k]}(-1)^{|I|+1}\left|\bigcap_{i\in I}F_i\right|\\ &=\sum_{i=1}^k(-1)^{i+1}\binom{k}i(k-i)^n\,, \end{align*}$$

and the number of surjections is therefore

$$\begin{align*} k!{n\brace k}&=k^n-\sum_{i=1}^k(-1)^{i+1}\binom{k}i(k-i)^n\\ &=\sum_{i=0}^k(-1)^i\binom{k}i(k-i)^n\\ &=\sum_{i=0}^k(-1)^i\binom{k}{k-i}(k-i)^n\\ &=\sum_{i=0}^k(-1)^{k-i}\binom{k}ii^n\,. \end{align*}$$