Elizalde–Luo pattern counts for nonnesting multiset permutations
Follow the latest progress by email.
How many nonnesting permutations of the multiset {1,1,…,n,n} avoid both patterns 1132 and 3312 under the published containment convention? The conjectured count is 3ⁿ−3·2ⁿ⁻¹+1 for every n≥1.
Why it matters and what counts as progress
Why it matters: The formula counts a specific repeated-letter pattern-avoidance family uniformly in n, beyond finite enumeration.
What counts as progress: Prove the exact formula by a recurrence or bijection, or extend the enumeration to other pattern pairs.
How the problem developed
- 2025 · Conjecture [1]
Sergi Elizalde and Amya Luo Published the conjectured count 3^n − 3·2^(n−1) + 1 for nonnesting permutations avoiding 1132 and 3312; the paper reports checks only through n = 8.
- 12 Jun 2026 · Formal proof [2]
Contributors to the Demonstrandum research project (individual proof authors not named in the cited record) Reported a proof for every n, formalized in Lean and accepted by the kernel under the project’s pinned definitions.
AI contribution
AI-assisted proof of the Elizalde–Luo pattern count
For every n≥1, the number of nonnesting permutations of {1,1,…,n,n} avoiding both 1132 and 3312, under the published containment convention, equals 3ⁿ−3·2ⁿ⁻¹+1.
Sources
Website timeline
Publication dates and editorial changes.