AFTD Auto-Formalizing Theoretical Domains

card_two_stack_sortable_perm_ending_in_zero

theoremverifiedformalization

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.

  1. 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.

    line 17

        Finset.univ).card = M n := by first | (simp_all; done) | omega | decide | linarith | positivity | (aesop; done)

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

/-- 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)
See it in the graphDiscuss this resultChallenge it