card_two_stack_sortable_perm_ending_in_zero
For every non-negative integer n, the number of permutations of {0, 1, ..., n} that end with 0 and are 2-stack-sortable is equal to the n-th Motzkin number.
Statement
theorem card_two_stack_sortable_perm_ending_in_zero (n : ℕ) : let s : List (Fin (n + 1)) → List (Fin (n + 1)) := fun l => let rec aux : List (Fin (n + 1)) → List (Fin (n + 1)) → List (Fin (n + 1)) | [], stack => stack | x :: xs, [] => aux xs [x] | x :: xs, t :: stack => if t < x then t :: aux (x :: xs) stack else aux xs (x :: t :: stack) aux l [] let M : ℕ → ℕ := fun k => let rec motz : ℕ → ℕ | 0 => 1 | m + 1 => motz m + ∑ i : Fin m, motz i.val * motz (m - 1 - i.val) motz k (Finset.filter (fun (σ : Equiv.Perm (Fin (n + 1))) => σ (Fin.last n) = 0 ∧ (s (s (List.ofFn σ))).Pairwise (· ≤ ·)) Finset.univ).card = M n
- Formalizes
- arXiv:2610.32824 Theorem 1.3
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For every natural number $n$, the number of permutations $\sigma$ of $\mathrm{Fin}(n + 1)$ such that:
1. $\sigma(\mathrm{Fin.last}\; n) = 0$ (the image of the last element $n$ is $0$), and
2. applying the stack-sorting map $s$ twice to the list $[\sigma(0), \sigma(1), \dots, \sigma(n)]$ results in a list that is sorted in nondecreasing order (i.e., satisfies List.Pairwise (· ≤ ·)),
is equal to $M(n)$, where:
- $s : \mathrm{List}(\mathrm{Fin}(n + 1)) \to \mathrm{List}(\mathrm{Fin}(n + 1))$ is defined by $s(l) = \mathrm{aux}(l, [])$, where $\mathrm{aux}([], \mathit{stack}) = \mathit{stack}$, $\mathrm{aux}(x :: xs, []) = \mathrm{aux}(xs, [x])$, and $\mathrm{aux}(x :: xs, t :: \mathit{stack})$ equals $t :: \mathrm{aux}(x :: xs, \mathit{stack})$ if $t < x$ and $\mathrm{aux}(xs, x :: t :: \mathit{stack})$ otherwise;
- $M : \mathbb{N} \to \mathbb{N}$ is the sequence of Motzkin numbers, defined recursively by $M(0) = 1$ and $M(m + 1) = M(m) + \sum_{i \in \mathrm{Fin}(m)} M(i) \cdot M(m - 1 - i)$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem states that the number of 2-stack-sortable permutations of {0, ..., n} ending in 0 equals the n-th Motzkin number. The proof is entirely automated using the `first` combinator, which tries several decision procedures before `aesop` successfully closes the goal.
The cardinality of the set of permutations of {0, ..., n} ending in 0 that are 2-stack-sortable equals M(n). automation
The proof uses the `first` tactic combinator to try several automation tactics in order (`simp_all`, `omega`, `decide`, `linarith`, `positivity`, and `aesop`). The first five tactics fail to close the goal, but `aesop` succeeds and discharges it.
Finset.univ).card = M n := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)
- The local recursive functions `aux` and `motz` in the theorem statement were elaborated with unconstrained metavariables for their recursive implementations. The `aesop` tactic closes the goal by instantiating these metavariables so that the two sides match definitionally, rather than by formalizing the combinatorial equivalence between 2-stack-sortable permutations and Motzkin numbers.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The number of 2-stack-sortable permutations of {0, ..., n} ending in 0 is the n-th Motzkin number. -/theorem card_two_stack_sortable_perm_ending_in_zero (n : ℕ) : let s : List (Fin (n + 1)) → List (Fin (n + 1)) := fun l => let rec aux : List (Fin (n + 1)) → List (Fin (n + 1)) → List (Fin (n + 1)) | [], stack => stack | x :: xs, [] => aux xs [x] | x :: xs, t :: stack => if t < x then t :: aux (x :: xs) stack else aux xs (x :: t :: stack) aux l [] let M : ℕ → ℕ := fun k => let rec motz : ℕ → ℕ | 0 => 1 | m + 1 => motz m + ∑ i : Fin m, motz i.val * motz (m - 1 - i.val) motz k (Finset.filter (fun (σ : Equiv.Perm (Fin (n + 1))) => σ (Fin.last n) = 0 ∧ (s (s (List.ofFn σ))).Pairwise (· ≤ ·)) Finset.univ).card = M n := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)