Wilf Equivalence¶
Two permutation classes are Wilf equivalent when they contain the same number of permutations at every length, equivalently when their ordinary generating functions coincide.
Core Idea¶
Wilf equivalence classifies permutation classes by their enumeration at every size. If \(\mathcal C_n=\mathcal C\cap S_n\) and \(\mathcal D_n=\mathcal D\cap S_n\), then
Equivalently, their ordinary generating functions \(C(x)=\sum_{n\ge0}|\mathcal C_n|x^n\) and \(D(x)=\sum_{n\ge0}|\mathcal D_n|x^n\) are identical as formal power series. The relation intentionally forgets which permutations occur and how the classes are structured; it retains the complete length-indexed counting sequence.
Scope of Application¶
The abstraction belongs to enumerative permutation-pattern combinatorics. It organizes principal classes \(\operatorname{Av}(\sigma)\), finitely based classes \(\operatorname{Av}(B)\), and other permutation classes by their length counts. The underlying occurrence relation says that a smaller pattern occurs when some subsequence is order-isomorphic to it, providing the avoidance classes to be enumerated.
The literature uses symmetry, bijection, generating trees, insertion encodings, and generating functions to discover or establish Wilf equivalences. Vatter's survey presents permutation classes as downsets under containment and treats enumeration as a central organizing problem.
Clarity¶
The term makes the quantifiers visible. “These patterns seem equally avoidable” becomes the testable claim that their avoidance counts agree for every \(n\). It separates the object-level carrier (patterns or classes) from the invariant used for classification (the complete enumerating sequence). It also clarifies why a generating-function identity is sufficient: formal-power-series equality is coefficientwise equality.
Manages Complexity¶
Permutation classes can differ in membership, bases, grid structure, and decomposition. Wilf equivalence compresses each class to one graded counting invariant and then groups all classes with the same invariant. This makes large classification problems tractable: prove one enumeration per Wilf class rather than repeat it for every member.
Abstract Reasoning¶
Because equality of sequences is reflexive, symmetric, and transitive, Wilf equivalence is literally an equivalence relation. If \(\mathcal C\sim_W\mathcal D\) and \(\mathcal D\sim_W\mathcal E\), coefficient equality gives \(\mathcal C\sim_W\mathcal E\). The quotient by this relation is the set of Wilf classes, allowing a classification “up to enumeration.”
Knowledge Transfer¶
Wilf equivalence transfers enumerative conclusions exactly. Once \(\mathcal C\sim_W\mathcal D\), a formula, recurrence, rationality or algebraicity statement, and coefficient asymptotic derived solely from the shared generating function applies to both. The proof used for one class may also suggest a bijection or decomposition for another, but that structural transfer requires additional work.
The abstraction teaches a broader method—classify objects by a declared invariant—but its name does not travel as a prime.
Relationships to Other Abstractions¶
Current abstraction Wilf Equivalence Domain-specific
Parents (1) — more general patterns this builds on
-
Wilf Equivalence is a kind of Equivalence Relation Prime
Wilf Equivalence is proposed as a strict specialization of
prime:equivalence_relation.
Hierarchy path (1) — routes to 1 parentless root
- Wilf Equivalence → Equivalence Relation
Neighborhood in Abstraction Space¶
Wilf Equivalence sits in a sparse region of the domain-specific corpus (68th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (1565 abstractions)
Nearest neighbors
- Emptiness problem — 0.86
- Covering Set — 0.85
- Arithmetic Progression — 0.85
- Hamming Scheme — 0.85
- Formal Theory — 0.84
Computed from structural-signature embeddings · 2026-09-08