Motzkin numbers: M(n) counts lattice paths (0,0)→(n,0) with steps U=(1,1), D=(1,−1), F=(1,0), staying ≥0. M(n)=1,1,2,4,9,21,51,127... Recurrence: (n+2)M(n) = (2n+3)M(n-1) + 3nM(n-2). Also counts non-crossing partitions with singletons.
How to Use
Enter n:
- M(n): Motzkin number
- Sequence: First values
- Comparison: vs Catalan
Combinatorial Meanings
M(n) counts: (1) Motzkin paths of length n. (2) Ways to draw non-crossing chords on n+1 points. (3) RNA secondary structures of length n. (4) Certain pattern-avoiding permutations.
Catalan Connection
Catalan numbers count paths with only U and D (no flat steps). Motzkin adds flat steps, giving more paths. C(n)≤M(n) for n≥2. Both satisfy similar recurrences and have generating function connections.
Step-by-Step Instructions
- 1Enter n.
- 2Compute M(n).
- 3View sequence.
- 4Compare to Catalan.
- 5See interpretations.