Computing the exponential generating function.

Question

Let $f(n)$ be the number of ordered set partitions of $[n]$. An ordered set partition is a sequence $S_1, \dots , S_k$ of disjoint non-empty subsets whose union is $[n]$. Compute the exponential generating function for $f(n)$.

Answer 1

By definition, $f(0)=0$. We also need the recurrence relation $$ f(n+1) = \sum \limits_{k=0}^n {n \choose k} f(k) $$ for $n \in \mathbb{N}_0$, which is derived here. If we denote the exponential generating function by $g$, we find \begin{align} g(x) &= \sum \limits_{m=0}^\infty \frac{f(m)}{m!} x^m = 1 + \sum \limits_{n =0}^\infty \frac{x^{n+1}}{(n+1)!} f(n+1) \\ &= 1 + \sum \limits_{n =0}^\infty \int \limits_0^x \frac{y^n}{n!} \, \mathrm{d} y \sum \limits_{k=0}^n {n \choose k} f(k) = 1 + \int \limits_0^x \sum \limits_{n =0}^\infty \sum \limits_{k=0}^n \frac{y^n}{n!} {n \choose k} f(k) \, \mathrm{d} y \\ &= 1 + \int \limits_0^x \sum \limits_{k=0}^\infty \frac{f(k)}{k!} y^k \sum \limits_{n=k}^\infty \frac{y^{n-k}}{(n-k)!} \, \mathbb{d} y = 1 + \int \limits_0^x \sum \limits_{k=0}^\infty \frac{f(k)}{k!} y^k \sum \limits_{l=0}^\infty \frac{y^l}{l!} \, \mathbb{d} y \\ &= 1 + \int \limits_0^x g(y) \mathrm{e}^y \, \mathbb{d} y \, . \end{align} Interchanging summation and integration is justified by Levi's monotone convergence theorem. Since $f(n) \leq n!$ holds for $n \in \mathbb{N}_0$ (see this question), the power series converges at least for $|x| < 1$. Now we only need to solve the above integral equation for $g$. Hint: A differential equation may be simpler.