# Closed form expression for a recursion relation with binomial coefficients

I am interested in the following sequence: $$T_n = \sum\limits^{n-1}_{k=0} \begin{pmatrix} n \\ k \end{pmatrix} T_{k}, \ \ \ \ T_0 = C \in \mathbb{N}$$ I would like to express it as a function of n, but none of the method I have tried work.

Asymptotically, I can tell that $$T_n = \mathcal{O}(2^{\frac{k^2}{2}})$$. One method that failed was to see $$T_n$$ as the $$n$$-th term in a series, but those terms grow to fast for it to work.

Do you know how to solve it, or have an intuition regarding how it might get solved?

Thank you.

• Here is a recipe: sage: T = lambda n: x if n == 0 else sum(binomial(n,k)*T(k) for k in range(n)) sage: T = cached_function(T) sage: [T(n) for n in range(5)] [x, x, 3*x, 13*x, 75*x] sage: oeis([T(n)/x for n in range(20)]) 0: A000670: Fubini numbers: number of preferential arrangements of n labeled elements; or number of weak orders on n labeled elements; or number of ordered partitions of [n]. – Martin Rubey Feb 18 '19 at 12:53

## 1 Answer

The $$T_n$$'s are equal to the product of $$C$$ and the Fubini numbers: number of ordered partitions of $$n$$, also known as ordered Bell numbers. The generating function is $$(2-e^x)^{-1}$$ and the large-$$n$$ asymptotics is $$T_n\sim C \frac{n!}{2(\ln 2)^{n+1}}.$$