7
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 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
    Commented Feb 18, 2019 at 12:53

1 Answer 1

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .