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.

  • 5
    $\begingroup$ 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]. $\endgroup$ – Martin Rubey Feb 18 '19 at 12:53

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


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.