# Efficiently evaluating the Motzkin numbers

So I made an error on the question here: $T_N = 1 + \sum_{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.

-
Please avoid using $$ in the title. – Asaf Karagila Aug 2 '12 at 2:00 @AsafKaragila: sorry typo – Andrew Tomazos Aug 2 '12 at 2:02 Fixed your typos. Anyway, +1 for checking the OEIS before asking; many people don't do that, and/or can't be bothered to. – J. M. Aug 2 '12 at 2:26 ## 1 Answer 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.

-
I don't think that matrix multiplication offers any real efficiency benefit here; since the coefficients aren't constant you can't 'propagate' by computing matrix powers, instead you're just multiplying a bunch of different matrices, and that's no faster than just memoizing the values of $M_k$. – Steven Stadnicki Aug 2 '12 at 4:39
Hmm, you're right; I had somehow been thinking about Chebyshev polynomials, and forgot that the recursion coefficients in that case do not depend on the index. I've deleted that section... – J. M. Aug 2 '12 at 4:51
I'm solving the same problem, unfortunately the above formula won't work for large $M$ mod a number, the division part won't apply for modular arithmetic. – Chan Aug 9 '12 at 19:12
@Chan, "mod a number" - then it's not really the same problem. Maybe you should ask a new question. – J. M. Aug 10 '12 at 0:05
@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. – Andrew Tomazos Aug 11 '12 at 11:21