4
$\begingroup$

So I made an error on the question here: A closed form for $T_N = 1 + \sum\limits_{k=0}^{N-2}{(N-1-k)T_k}$?

The correct formula I'm trying to solve is more complicated and as follows:

$T_0 = T_1 = 1 $

$T_{N+1} = T_N + \sum_{k=1}^{N}T_{k-1}T_{N-k}$

I calculated the first few terms:

$T_2 = 2$

$T_3 = 2 + T_0T_1 + T_1T_0 = 4$

$T_4 = 4 + T_0T_2 + T_1T_1 + T_0T_2 = 4 + 2 + 1 + 2 = 9$

$T_5 = 9 + T_0T_3 + T_1T_2 + T_2T_1 + T_3T_0 = 9 + 4 + 2 + 2 + 4 = 21$

and plugged it into OEIS and it gave me back: http://oeis.org/A001006 . Which is exactly the problem I am trying to solve (non-intersecting chords on a circle).

What I don't understand is how to use the FORMULA section from OEIS. Would someone be kind enough to take one of the formulas from OEIS and walk me through how to use it to actually close my recurrence, so I can efficiently calculate $T_N$ for large N.

  • 0
    Fixed your typos. Anyway, +1 for checking the OEIS before asking; many people don't do that, and/or can't be bothered to.2012-08-02

1 Answers 1

2

We can in fact slightly simplify one of the formulae given in the OEIS entry for the Motzkin numbers:

$M_n=\sum_{k=0}^n \frac1{k+1}\binom{2k}{k}\binom{n}{2k}$

You can then use either the built-in binomial coefficient routine in your computing environment, or use the usual recurrence relations for binomial coefficients.

Alternatively, you can use the nice three-term recurrence (formula 6 here)

$M_k=\frac{2k+1}{k+2}M_{k-1}+3\frac{k-1}{k+2}M_{k-2},\qquad M_0=M_1=1$

and then use any of the methods for propagating a three-term recurrence.

  • 0
    @Chan: If it was a prime base, then you can use the modular inverse. If it isn't a prime base, than you can use arbitrary precision arithmetic.2012-08-11