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?
 A: 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*}$$
A: After computing some values I have found OEIS A019538 and the formula:
$$k!{n \brace k}$$
You can find further information at the OEIS page.
