The Catalan number formula
ProvedFamousTheorems.catalan_number_formulaThe Catalan number formula. The -th Catalan number satisfies
Catalan numbers count well-formed bracket sequences, binary trees, triangulations of a convex polygon and many other structures. The closed formula is usually proved by the reflection principle or by generating functions.
Formalization note. Mathlib's succ_mul_catalan_eq_centralBinom and catalan_eq_centralBinom_div. Mathlib defines catalan by the recursion with , and n.centralBinom is . The division in the second part is natural-number division, which is exact by the first part.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems theorem catalan_number_formula (n : ℕ) : (n + 1) * catalan n = n.centralBinom ∧ catalan n = n.centralBinom / (n + 1) := by sorry end FamousTheorems
Source
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `catalan_eq_centralBinom_div`. Proof here reduces to that Mathlib result.