motzkin_number
def
The n-th Motzkin number M_n is defined by M_0 = 1 and M_{n+1} = M_n + ∑_{i=0}^{n-1} M_i M_{n-1-i}.
Statement
def motzkin_number : ℕ → ℕ- Defined in
- arXiv:2610.32824 Definition 1.2
- Verified
- 26 Oct 2026
- Axioms
- none listed
Read back from the Lean
The function motzkin_number : ℕ → ℕ defined recursively by:
- motzkin_number 0 = 1
- for all $n : ℕ$, motzkin_number (n + 1) = motzkin_number n + ∑ i : Fin n, motzkin_number i.val * motzkin_number (n - 1 - i.val) (i.e., motzkin_number n plus the sum of motzkin_number i * motzkin_number (n - 1 - i) for $i$ from $0$ to $n - 1$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The n-th Motzkin number defined recursively. -/ def motzkin_number : ℕ → ℕ | 0 => 1 | n + 1 => motzkin_number n + ∑ i : Fin n, motzkin_number i.val * motzkin_number (n - 1 - i.val)