Pattern avoidance in compositions and powers of permutations

Kassie Archer; Noel Bourne

arxiv: 2505.05218 · v3 · submitted 2025-05-08 · 🧮 math.CO

Pattern avoidance in compositions and powers of permutations

Kassie Archer , Noel Bourne This is my paper

Pith reviewed 2026-05-22 16:41 UTC · model grok-4.3

classification 🧮 math.CO MSC 05A05

keywords pattern avoidancecompositionspermutationspattern chainspermutation squaresenumeration

0 comments

The pith

A new pattern avoidance notion on compositions enumerates permutations that avoid specified chains involving the permutation and its square.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines pattern avoidance for compositions of positive integers to handle conditions that involve both a permutation and its square. It applies this definition to count permutations of length n avoiding the chain (312,321:σ) for every pattern σ and those avoiding (312,4321:σ) for every σ of length 3. A reader cares because pattern avoidance is a major enumerative topic and the square introduces an algebraic constraint that the composition model resolves into ordinary counting.

Core claim

We define a notion of pattern avoidance for compositions of positive integers and use that idea to enumerate permutations of length n that avoid the chain (312,321:σ) for any pattern σ∈⋃m≥1 Sm. We also enumerate those permutations that avoid the chain (312,4321:σ) for any σ∈S3.

What carries the argument

Pattern avoidance for compositions of positive integers, which translates the joint avoidance of one pattern in π and another in π² into an equivalent problem on compositions.

Load-bearing premise

The newly defined pattern avoidance on compositions correctly translates the joint avoidance conditions on a permutation π and its square π² into an equivalent counting problem on compositions.

What would settle it

A concrete counterexample would be a permutation of [n] that avoids the given chain but whose associated composition does not avoid the corresponding composition pattern, or the reverse.

read the original abstract

A permutation $\pi$ is said to avoid a chain $(\sigma:\tau)$ of patterns if $\pi$ avoids $\sigma$ and $\pi^2$ avoids $\tau.$ In this paper, we define a notion of pattern avoidance for compositions of positive integers and use that idea to enumerate permutations of length $n$ that avoid the chain $(312,321:\sigma)$ for any pattern $\sigma\in \bigcup_{m\geq 1} S_m$. We also enumerate those permutations that avoid the chain $(312,4321:\sigma)$ for any $\sigma\in S_3.$

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper defines pattern avoidance on compositions to count permutations avoiding 312 plus a pattern in their square, delivering new enumerations for two families but hinging on an equivalence that needs direct checks.

read the letter

Hi, the main point is that Archer and Bourne define a notion of pattern avoidance for compositions and use it to enumerate permutations that avoid 312 while their square avoids either 321 or 4321, each paired with an auxiliary pattern σ. They handle the first case for arbitrary σ and the second for σ of length at most 3. This produces explicit counts or generating functions that were not previously known for these joint conditions. The work is honest and stays inside the usual toolkit of permutation patterns, so the derivations look like standard recurrence or generating-function arguments once the composition model is set up. The definition itself is the real addition, turning the problem about π and π² into a counting problem on integer compositions. The soft spot is the translation between the two languages. The composition avoidance has to reproduce exactly the relative-order conditions that appear when you look at both π and π²; if the standardization or the auxiliary permutation built from the parts misses or adds an occurrence for some σ, the claimed numbers will be off. The abstract gives no small-n verification or explicit bijection, so that step is the one a referee should examine first. If the full text includes a direct comparison for n up to 8 or 9 against brute-force enumeration, the concern shrinks to minor. This is for people already working on pattern avoidance and its extensions to powers or chains. A reader in that subfield will find the new counts and the composition trick worth seeing. It deserves a serious referee because the results are concrete and the method is adaptable even if the equivalence needs tightening.

Referee Report

2 major / 2 minor

Summary. The paper introduces a definition of pattern avoidance for compositions of positive integers. It then uses this notion to enumerate the permutations of length n that avoid the chain (312, 321 : σ) for arbitrary σ in the union over m of S_m, and those that avoid the chain (312, 4321 : σ) for σ in S_3, where chain avoidance means that π avoids the first pattern while π² avoids the second.

Significance. If the claimed equivalence between composition avoidance and the joint (π, π²) avoidance conditions holds, the work supplies explicit enumerations for two infinite families of permutation classes defined via simultaneous avoidance on a permutation and its square. This could furnish a new combinatorial tool for studying pattern avoidance in permutation powers and might yield generating functions or closed forms that are not readily obtainable by direct permutation methods.

major comments (2)

[Section 2] Section 2 (definition of composition pattern avoidance): the manuscript asserts that the new avoidance condition on a composition exactly reproduces the relative-order constraints arising from π avoiding 312 together with π² avoiding the pattern derived from σ, but supplies neither an explicit bijection nor a small-n verification (e.g., brute-force enumeration for n ≤ 6) that the two languages coincide. Because every subsequent count rests on this translation, the equivalence must be established before the enumerations can be accepted.
[Theorems 4.1 and 5.2] The main enumeration statements (Theorems 4.1 and 5.2, or whichever results give the generating functions or closed forms for the two families): these formulas are derived directly from the composition counts; if the composition avoidance over- or under-counts the joint permutation conditions for even one σ, the formulas will be incorrect for infinitely many n. An independent check against the OEIS or direct computation for small n is required.

minor comments (2)

[Section 2] Notation for the composition avoidance relation is introduced without a clear comparison table to the classical permutation pattern notation; a side-by-side example for a short composition and its corresponding permutation would improve readability.
[Introduction] The abstract states that the enumerations are “obtained via the new composition definition,” yet the introduction does not preview the precise recurrence or generating-function equation that will be solved; adding one sentence would clarify the logical flow.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the opportunity to respond to the referee's report on our manuscript arXiv:2505.05218. We appreciate the constructive comments and address each major point below.

read point-by-point responses

Referee: [Section 2] Section 2 (definition of composition pattern avoidance): the manuscript asserts that the new avoidance condition on a composition exactly reproduces the relative-order constraints arising from π avoiding 312 together with π² avoiding the pattern derived from σ, but supplies neither an explicit bijection nor a small-n verification (e.g., brute-force enumeration for n ≤ 6) that the two languages coincide. Because every subsequent count rests on this translation, the equivalence must be established before the enumerations can be accepted.

Authors: We thank the referee for this observation. Upon review, we recognize that while the paper motivates the definition through the correspondence, an explicit bijection and small-n verification were not included. In the revised manuscript, we will insert a detailed explanation of the bijection mapping compositions to the relevant permutations and provide a table of counts for n=1 to 6 obtained both ways to verify agreement. This will confirm the languages coincide for small n and support the general equivalence. revision: yes
Referee: [Theorems 4.1 and 5.2] The main enumeration statements (Theorems 4.1 and 5.2, or whichever results give the generating functions or closed forms for the two families): these formulas are derived directly from the composition counts; if the composition avoidance over- or under-counts the joint permutation conditions for even one σ, the formulas will be incorrect for infinitely many n. An independent check against the OEIS or direct computation for small n is required.

Authors: We agree that an independent check is necessary to validate the enumerations. We will add to the revised paper direct computations for small n by enumerating permutations avoiding the specified chains and compare these counts to the numbers given by our formulas. Additionally, we will search for and reference matching sequences in the OEIS to provide further confirmation where possible. revision: yes

Circularity Check

0 steps flagged

Newly introduced composition avoidance definition yields independent enumerations of chain-avoiding permutations

full rationale

The paper introduces a fresh definition of pattern avoidance for compositions of positive integers and then derives enumerations for permutations avoiding the specified chains (312,321:σ) and (312,4321:σ). No step reduces a claimed prediction or count to a fitted parameter, prior self-citation, or tautological renaming; the central results follow from applying the new definition to translate the joint avoidance condition into a composition counting problem. The derivation is therefore self-contained against external benchmarks and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The abstract indicates reliance on the standard definition of permutation pattern avoidance and the algebraic notion of permutation composition (squaring). No free parameters, ad-hoc axioms, or invented entities are mentioned.

axioms (2)

standard math Standard definition of classical pattern avoidance in permutations
Invoked when stating that π avoids σ and π² avoids τ.
standard math Permutation composition is well-defined and associative
Required to form π².

pith-pipeline@v0.9.0 · 5612 in / 1283 out tokens · 49533 ms · 2026-05-22T16:41:18.173700+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel (J-cost uniqueness) echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

We define a notion of pattern avoidance for compositions ... bn(c) = sum_{i=1}^{c1-1} bn-i(c) + sum_{i=c1}^n bn-i(ĉ) ... solutions are F_{n+3}−n−1, T_{n+2}, Q_{n+3}
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat ≃ Nat, embed_strictMono unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

π = ⊕ ϵ_{d_i} for composition d of n; π² = ⊕ ϵ²_{d_i}; avoidance of chain (312,321:σ) ⇔ d avoids C(σ)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[1]

Archer and A

K. Archer and A. Geary, Powers of permutations avoiding chains of patterns.Discrete Math.347(9) (2024)

work page 2024
[2]

B´ ona,Combinatorics of Permutations, 2nd edition, CRC Press, 2012

M. B´ ona,Combinatorics of Permutations, 2nd edition, CRC Press, 2012

work page 2012
[3]

B´ ona and R

M. B´ ona and R. Smith, Pattern avoidance in permutations and their squares.Discrete Math.342(11) (2019), 3194–3200

work page 2019
[4]

Burcroff and C

A. Burcroff and C. Defant, Pattern-avoiding permutation powers.Discrete Math.343(11) (2020), 112017

work page 2020
[5]

Heubach and T

S. Heubach and T. Mansour, Avoiding patterns of length three in compositions and multiset permuta- tions,Adv. in Appl. Math., 36(2) (2006), 156–174

work page 2006
[6]

Jel´ ınek, T

V. Jel´ ınek, T. Mansour, and M. Shattuck, On multiple pattern avoiding set partitions,Adv. in Appl. Math.50(2) (2013), 292–326

work page 2013
[7]

Knuth,The Art of Computer Programming, Vol

D. Knuth,The Art of Computer Programming, Vol. 1, Addison-Wesley, 1968

work page 1968
[8]

Menon and A

K. Menon and A. Singh, Pattern Avoidance and Dominating Compositions,ECA2(1) (2022), Article #S2R4

work page 2022
[9]

(2023), The On-Line Encyclopedia of Integer Sequences, Published electronically athttps://oeis.org

OEIS Foundation Inc. (2023), The On-Line Encyclopedia of Integer Sequences, Published electronically athttps://oeis.org

work page 2023
[10]

Pan, On a Conjecture About Strong Pattern Avoidance,Graphs and Combinatorics39(2) (2023)

J. Pan, On a Conjecture About Strong Pattern Avoidance,Graphs and Combinatorics39(2) (2023)

work page 2023
[11]

J. Y. Pan and P. F. Guo, On the permutations that strongly avoid the pattern 312 or 231,Graphs and Combinatorics41, 17 (2025)

work page 2025
[12]

Sagan and V

B.E. Sagan and V. Vatter, The M¨ obius function of a composition poset.J Algebr Comb24, (2006), 117–136

work page 2006
[13]

Sage Developers, Sagemath, the Sage Mathematics Software System (Version 9.5.0), 2022, https://www.sagemath.org

work page 2022
[14]

C. D. Savage, H. S. Wilf, Pattern avoidance in compositions and multiset permutations,Adv. in Appl. Math., 36(2) (2006), 194–201

work page 2006
[15]

Simion and F

R. Simion and F. W. Schmidt, Restricted permutations,European J. Combin.6(4) (1985), 383–406

work page 1985
[16]

Vatter, Reconstructing compositions,Discrete Math., 308(9) (2008), 1524–1530

V. Vatter, Reconstructing compositions,Discrete Math., 308(9) (2008), 1524–1530. 12 Statements and Declarations The authors declare that no funds, grants, or other support were received during the preparation of this manuscript. The authors have no relevant financial or non-financial interests to disclose. The views expressed in this article do not necess...

work page 2008

[1] [1]

Archer and A

K. Archer and A. Geary, Powers of permutations avoiding chains of patterns.Discrete Math.347(9) (2024)

work page 2024

[2] [2]

B´ ona,Combinatorics of Permutations, 2nd edition, CRC Press, 2012

M. B´ ona,Combinatorics of Permutations, 2nd edition, CRC Press, 2012

work page 2012

[3] [3]

B´ ona and R

M. B´ ona and R. Smith, Pattern avoidance in permutations and their squares.Discrete Math.342(11) (2019), 3194–3200

work page 2019

[4] [4]

Burcroff and C

A. Burcroff and C. Defant, Pattern-avoiding permutation powers.Discrete Math.343(11) (2020), 112017

work page 2020

[5] [5]

Heubach and T

S. Heubach and T. Mansour, Avoiding patterns of length three in compositions and multiset permuta- tions,Adv. in Appl. Math., 36(2) (2006), 156–174

work page 2006

[6] [6]

Jel´ ınek, T

V. Jel´ ınek, T. Mansour, and M. Shattuck, On multiple pattern avoiding set partitions,Adv. in Appl. Math.50(2) (2013), 292–326

work page 2013

[7] [7]

Knuth,The Art of Computer Programming, Vol

D. Knuth,The Art of Computer Programming, Vol. 1, Addison-Wesley, 1968

work page 1968

[8] [8]

Menon and A

K. Menon and A. Singh, Pattern Avoidance and Dominating Compositions,ECA2(1) (2022), Article #S2R4

work page 2022

[9] [9]

(2023), The On-Line Encyclopedia of Integer Sequences, Published electronically athttps://oeis.org

OEIS Foundation Inc. (2023), The On-Line Encyclopedia of Integer Sequences, Published electronically athttps://oeis.org

work page 2023

[10] [10]

Pan, On a Conjecture About Strong Pattern Avoidance,Graphs and Combinatorics39(2) (2023)

J. Pan, On a Conjecture About Strong Pattern Avoidance,Graphs and Combinatorics39(2) (2023)

work page 2023

[11] [11]

J. Y. Pan and P. F. Guo, On the permutations that strongly avoid the pattern 312 or 231,Graphs and Combinatorics41, 17 (2025)

work page 2025

[12] [12]

Sagan and V

B.E. Sagan and V. Vatter, The M¨ obius function of a composition poset.J Algebr Comb24, (2006), 117–136

work page 2006

[13] [13]

Sage Developers, Sagemath, the Sage Mathematics Software System (Version 9.5.0), 2022, https://www.sagemath.org

work page 2022

[14] [14]

C. D. Savage, H. S. Wilf, Pattern avoidance in compositions and multiset permutations,Adv. in Appl. Math., 36(2) (2006), 194–201

work page 2006

[15] [15]

Simion and F

R. Simion and F. W. Schmidt, Restricted permutations,European J. Combin.6(4) (1985), 383–406

work page 1985

[16] [16]

Vatter, Reconstructing compositions,Discrete Math., 308(9) (2008), 1524–1530

V. Vatter, Reconstructing compositions,Discrete Math., 308(9) (2008), 1524–1530. 12 Statements and Declarations The authors declare that no funds, grants, or other support were received during the preparation of this manuscript. The authors have no relevant financial or non-financial interests to disclose. The views expressed in this article do not necess...

work page 2008