2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ The EGF appeared at the following MSE link. $\endgroup$ Oct 12 '17 at 21:00
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Wow. I am an idiot! Thank you so much for this! $\endgroup$ Oct 12 '17 at 21:31
0
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.