Let $S(n,k)$ be a Stirling number of the second kind. Then define
$$
a_n = \sum_{k=0}^n k! \cdot S(n,k)
$$
is known as either the $n^{th}$ Fubini number or the $n^{th}$ ordered Bell number.
I know that $a_n$ satisfies the following recurrence:
$$
a_n = \sum_{k=1}^n\binom{n}{k}a_{n-k}
$$
and that
$$
\frac{1}{2-e^x}=f(x) = \sum_{k=0}^\infty a_k\frac{x^k}{k!}
$$
is the exponential generating function. I am attempting to derive this generating function and if I can prove the following convolution
$$
\sum_{k=0}^n\binom{n}{k}a_ka_{n-k} = \frac{a_{n+1}+a_n}{2}
$$
then I can show that $f(x)$ satisfies
$$
2f^2(x)-f(x) = f'(x)
$$
and conclude that
$$
f(x) = \frac{1}{2-e^x}.
$$
Does anyone know of a combinatorial proof or some other basic approach to prove the convolution? The only thing I can find requires the manipulation of lots of Fubini polynomials which I would like to avoid as the consequence is not immediate or trivial.
Best Answer
You don't need to know any additional recurrence or functional relation in order to derive the exponential generating function (egf) $A=A(x)$ of $a_n$ here. All you need is some Analytic Combinatorics, part A (also see the book's website). What you are counting here is the number of ways to put $n$ distinct balls into any possible number of distinct nonempty boxes. Let $n$ range over all nonnegative integers. Now you're just looking at ways to put distinct balls into an arbitrary-length sequence (possibly empty) of distinct nonempty boxes. Let $B=B(x)$ be the egf for number of ways of putting distinct balls into $1$ nonempty box. Then we have $$ B=e^x-1 \quad \text{and} \quad A=\frac{1}{1-B}=\frac{1}{1-(e^x-1)}=\frac{1}{2-e^x}. $$