REDUCE

7.5 Motzkin numbers

A Motzkin number Mn (named after Theodore Motzkin) is the number of different ways of drawing non-intersecting chords on a circle between n points. For a non-negative integer n, the operator Motzkin(n) returns the nth Motzkin number, according to the recursion formula

M0 =  1;  M1 = 1;  Mn+1  =  2n+-3-Mn + --3n- Mn -1.
                            n + 3      n + 3