A generating function for ordered Bell numbers 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.
 A: 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}.
$$
A: We are given $a_0=1$ and $$a_n = \sum_{k=1}^n\binom{n}{k}a_{n-k}$$ for $n>0$.
Now add $a_n$ to both sides to get $$2a_n = \sum_{k=0}^n\binom{n}{k}a_{n-k}$$ for $n>0$ as well. Translating this to generating functions:
$$-1 + 2f(x) = e^xf(x)$$ leads to $$\frac1{2-e^x}=f(x).$$
A: For $n\ge0$, let
\begin{equation}\label{Fubini-No.Dfn}
  F_n=\sum_{k=0}^{n}k!S(n,k),
\end{equation}
where $S(n,k)$, which can be generated by the exponential function
\begin{equation*}
\frac{(e^x-1)^k}{k!}=\sum_{n=k}^\infty S(n,k)\frac{x^n}{n!}
\end{equation*}
and can be computed by the explicit formula
\begin{equation*}
S(n,k)=\frac1{k!}\sum_{\ell=1}^k(-1)^{k-\ell}\binom{k}{\ell}\ell^{n},
\end{equation*}
denotes the Stirling numbers of the second kind.
One calls these numbers $F_n$ the Fubini numbers in the paper [1] below, ordered Bell numbers in the paper [2], or geometric numbers in the paper [3] below.
A Fubini number $F_n$ has been interpreted in the papers [2, 3] combinatorially: it counts all the possible set partitions of an $n$ element set such that the order of the blocks matters. In the paper [2], the Fubini numbers $F_n$ were connected with preference arrangements and the recursion for $F_n$ was derived. In the papers [2, 4] below, the exponential generating function
\begin{equation}\label{Fubini-Num-Eq}
\frac{1}{2-e^t}=\sum_{n=0}^{\infty}F_n\frac{t^n}{n!}
\end{equation}
and an asymptotic estimate for $F_n$ were established.
References

*

*M. E. Dasef and S. M. Kautz, Some sums of some importance, College Math. J. 28 (1997), 52--55.

*O. A. Gross, Preferential arrangements, Amer. Math. Monthly 69 (1962), 4--8; available online at https://doi.org/10.2307/2312725.

*S. M. Tanny, On some numbers related to the Bell numbers, Canad. Math. Bull. 17 (1974/75), no. 5, 733--738; available online at https://doi.org/10.4153/CMB-1974-132-8.

*R. D. James, The factors of a square-free integer, Canad. Math. Bull. 11 (1968), 733--735; available online at https://doi.org/10.4153/CMB-1968-089-7.

*F. Qi, Determinantal expressions and recurrence relations for Fubini and Eulerian polynomials, Journal of Interdisciplinary Mathematics 22 (2019), no. 3, 317--335; available online at https://doi.org/10.1080/09720502.2019.1624063.

