knowing that the number of surjections $N_m\to N_n$ is (using the principle of inclusion exclusion):
$\displaystyle\sum_{i=0}^n (-1)^i\binom{n}{i} (n-i)^m$
furthermore, we know the connection with stirling numbers:
$\displaystyle\frac{1}{n!}\sum_{i=0}^n (-1)^i\binom{n}{i} (n-i)^m$
Knowing this, how can I obtain the generating function of the surjections $e^x-1$ ?
Best Answer
Using the fact that $(n-i)^m=m![x^m]e^{(n-i)x}$, where $[x^m]f(x)$ means the coefficient of $x^m$ in the power series $f(x)$, \begin{align} \sum_{i=0}^n (-1)^i\binom ni(n-i)^m &=m!\sum_{i=0}^n (-1)^i \binom ni [x^m] e^{(n-i)x} \\ &=m![x^m]\sum_{i=0}^n \binom ni (e^{x})^{n-i}(-1)^i \\ &=m^n \end{align} This shows that the exponential generating function (e.g.f.) for surjections onto a set of size $n$ is $(e^x-1)^n$. If you instead want the e.g.f. for surjections onto a set of any size, then you need to sum over all possible $n$. In conclusion, the e.g.f for all surjections is $$ \sum_{n=0}^\infty (e^x-1)^n=\frac1{1-(e^x-1)}=\frac1{2-e^x}. $$