Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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
add comment

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.

share|improve this answer
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.