A generating function for ordered Bell numbers

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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

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.