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.

• The EGF appeared at the following MSE link. Oct 12 '17 at 21:00

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}.$$

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).$$

• Wow. I am an idiot! Thank you so much for this! Oct 12 '17 at 21:31

For $$n\ge0$$, let $$$$\label{Fubini-No.Dfn} F_n=\sum_{k=0}^{n}k!S(n,k),$$$$ 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 $$$$\label{Fubini-Num-Eq} \frac{1}{2-e^t}=\sum_{n=0}^{\infty}F_n\frac{t^n}{n!}$$$$ and an asymptotic estimate for $$F_n$$ were established.

References

1. M. E. Dasef and S. M. Kautz, Some sums of some importance, College Math. J. 28 (1997), 52--55.
2. O. A. Gross, Preferential arrangements, Amer. Math. Monthly 69 (1962), 4--8; available online at https://doi.org/10.2307/2312725.
3. 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.
4. 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.
5. 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.