Wilf-equivalence of classical permutation patterns: the codimension-two maximum

Abstract

Write Avₙ(β) for the set of permutations of length n that avoid the classical pattern β, and call two patterns Wilf-equivalent when these sets have the same size at every n. Ray and West proved that for β of length m the number g₂(β) of permutations of length m+2 containing β is (m⁴+2m³+m²+4m+4-2j)/2 for an integer j=j(β) with 0 ≤ j ≤ m-1; expressing j as a statistic of β is a problem of Vatter's, open since 2007. We determine the extreme case. For every pattern of length 3, 4 and 5 we prove, by exhaustive machine-checked computation, that |Avₘ₊₂(β)| is largest — equivalently j(β)=m-1 — exactly when β is layered or reverse-layered, that is, avoids both 231 and 312, or both 132 and 213; an independent computation confirms this through length 8. There are 2ᵐ-2 such patterns, and neither half of the disjunction can be dropped. The same machinery reproduces the published codimension-one and codimension-two data, the lower bounds 3 and 16 on the number of Wilf classes at lengths 4 and 5, the three shape-Wilf classes of length-3 patterns, and Stankova's Wilf-equivalence 1342 ∼ 2413 that is not shape-Wilf; at length 8 it realises all eight avoidance counts that Ray–West's formula permits at n=10. Separately, Section [sec:external] reports a computation carried out outside the formal development and not machine-checked: there are exactly 4755 Wilf-equivalence classes of permutations of length 8, and the published theorems account for all of them. Except where explicitly marked as external, every statement below is machine-checked in Lean 4.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-08-30 15:34 UTC

   File fingerprint

   fbc039316be1516b95e244d8762d1998278394ea29dd20962a617fa03254e6c2