Pith. sign in

REVIEW 5 minor 24 references

Classical and vincular patterns of length three in generalized alternating permutations

T0 review · 0 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves closed-form counts for every length-three classical and vincular pattern-avoidance class in generalized alternating permutations, using forest bijections and poset encodings.

desk verdict A correct and useful complete classification of length-3 pattern avoidance in D_{N,k}; the main counts and bijections hold up, with the 321 case honestly left as an RSK reduction. read the letter →

arxiv 2607.26507 v1 pith:USDMSMWF submitted 2026-07-29 math.CO

Zhenhua Luo , Junting Wang , Ziyi Yang , Feng Zhao , Tongyuan Zhao This is my paper
classification math.CO MSC 05A0505A1505A19
keywords patternavoidancealternatingpermutationsfixeddescentsetvincularpatternsRaneynumbersFuss-Catalank-arytreesRSKcorrespondence
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper studies permutations of {1,...,N} whose descent set is exactly {k,2k,...}: entries rise inside each block of length k and fall at each block boundary. It proves that avoiding any one classical or vincular pattern of length three in this class leads to a closed-form enumeration: Raney or Fuss-Catalan numbers for most classical and adjacent cases, factorial products for two consecutive cases, linear-extension counts of explicit posets for the remaining vincular cases, and an RSK sum for 321. The interest is that a fixed-descent analogue of alternating permutations still produces a complete classification with bijective witnesses, turning pattern avoidance in these classes into a finite catalogue of Raney, Fuss-Catalan, product, and poset formulas.

What carries the argument

The defining object is the block poset B_{m,s,k}, whose linear extensions are exactly D_{N,k}. The main tools are: a recursive bijection between 132- and 231-avoiders and ordered forests of complete k-ary trees (with Lukasiewicz paths as a derived model); completion lemmas that extend the last block by appending largest or consecutive values to reduce 213- and 312-avoidance to the complete-block case; reverse-complement symmetry; the RSK correspondence for 321; and insertion lemmas that convert vincular adjacency conditions into record/tree-poset conditions.

What would settle it

For a small parameter set such as k=2, m=2, s=1 (N=5), enumerate all permutations in D_{5,2} avoiding 132 and compare the count with the Raney number 4; then apply the recursive inverse to each element and check directly whether any 132 occurrence crosses the left/right factors. A mismatch in either the count or the cross-factor check would refute the classification.

Watch

Extended reading notes

Core claim

For N=mk+s with 1≤s≤k, the paper identifies D_{N,k}(132) and D_{N,k}(231) with ordered forests of s complete k-ary trees having m internal vertices, giving the Raney count s/N * binomial(N,m); identifies D_{N,k}(213) and D_{N,k}(312) with complete k-ary trees with m+1 internal vertices, giving the Fuss-Catalan count; and expresses D_{N,k}(321) by RSK as a sum over ballot words whose peaks occur exactly at block boundaries. For all eighteen vincular patterns, the counts are either degenerate, Raney/Fuss-Catalan, explicit factorial products such as k^m m! and product over j of (s+jk), or linear-extension numbers of posets obtained by adding one family of inequalities to the underlying block po

Load-bearing premise

The Raney enumeration of 132- and 231-avoiders rests on the assertion, made in the inverse paragraph of Section 3.1, that after reinflating the left and right recursive factors around the maximum entry, no 132 (or 231) occurrence can span the two factors; the proof states this without exhaustively enumerating cross-pattern cases.

Editorial extensions

If this is right

  • The 132- and 231-avoiding classes in D_{N,k} are counted exactly by the number of ordered forests of s complete k-ary trees with m internal vertices, namely the Raney number.
  • The 213- and 312-avoiding classes are counted exactly by the Fuss-Catalan number, via completing the last block and applying reverse-complement symmetry.
  • When N is a multiple of k, the four non-monotone classical classes 132, 231, 213, and 312 all have the same Fuss-Catalan count.
  • The generating functions for the Raney classes satisfy sum_{m≥0} |D_{mk+s,k}(132)| z^m = T(z)^s, where T(z)=1+z T(z)^k.
  • Every one-adjacent vincular class is either Raney/Fuss-Catalan, an explicit factorial product, or the linear-extension count of an explicitly described poset.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the classification suggests that pattern avoidance in fixed-descent sets is governed more by block-boundary positions than by value order inside blocks; one testable consequence is that length-four Wilf equivalences will appear as symmetries of the block poset.
  • Editorial inference: the exact poset encodings for the remaining vincular cases likely extend to simultaneous avoidance of one classical and one vincular pattern in D_{N,k}, yielding further finite formulas.
  • Editorial inference: the proof of the 132/231 Raney bijection has one compressed step; a natural next step is to make the inverse's cross-factor no-occurrence claim fully explicit, since the entire forest model depends on it.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. This paper studies the set D_{N,k} of permutations of [N] whose descent set is exactly {k,2k,...,k floor((N-1)/k)} — a k-periodic generalization of alternating permutations. It gives a complete enumeration of D_{N,k} avoiding each classical and each vincular pattern of length three. For classical patterns, 132- and 231-avoiders are shown by explicit recursive bijections to be counted by the Raney number, and 213- and 312-avoiders by the Fuss-Catalan number via completion lemmas and reverse-complement symmetry; the remaining 321 case is expressed through RSK as a sum over ballot words with prescribed UD-peak positions. For the six fully consecutive and twelve one-adjacent vincular patterns, the paper obtains product formulas (e.g., k^m m!, rising factorials), Raney/Fuss-Catalan counts, or exact linear-extension counts of explicitly defined posets. The proofs are bijective and reversible, with independent combinatorial objects (complete k-ary trees, standard Young tableaux, tree posets) carrying the enumeration.

Significance. If correct, this constitutes a complete and systematic extension of Lewis's k=2 results for alternating permutations to periodic descent classes, and it is the first classification of vincular length-3 avoidance in this setting. The paper's strengths are its constructive bijections and the absence of fitted parameters: the enumerations are obtained from standard objects (k-ary trees, RSK, hook-length formula) and the generating-function identities are standard. The 321 formula is deliberately an RSK reduction rather than a closed form, but the paper is transparent about this scope choice. The poset linear-extension cases are exact finite descriptions of otherwise nontrivial classes. I found no internal inconsistency or circularity.

minor comments (5)
  1. [Section 3.1] The inverse paragraph of the recursive bijection asserts 'The inequalities just described prevent cross 132 occurrences' in one sentence. The claim is true—the interval separation between left and right factors excludes any crossing—but for a central, load-bearing bijection the argument is too compressed. A short case analysis (or an explicit statement of the interval ordering) would make the proof fully self-contained.
  2. [Abstract] Typo: 'closed results forms' should be 'closed-form results'.
  3. [Notation (Sections 4–5)] The vincular pattern notation (overlines/underlines) is essential, but in the plain-text rendering the three types (e.g., 132, 132, 132) are indistinguishable. In the actual PDF this is presumably clear, but a legend or a remark in the introduction would help readers who rely on the table entries.
  4. [Section 3.3, Proposition 3.6] The case k >= 3 and N < 3 is not stated explicitly; it is of course trivial (no pattern of length three can occur), but adding a sentence would make the table complete.
  5. [Section 3.3, Theorem 3.7] The quantity K_{N,k}(a) is defined but not evaluated further. Since the authors deliberately frame 321 as 'expressed by RSK' rather than as a closed form, this is a scope choice, but a remark noting that K counts ballot words with prescribed peak positions would clarify that the formula is a finite sum of a standard quantity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all enumerations are derived from explicit bijections, posets, and standard external identities; no fitted parameters or self-citation chains.

full rationale

The paper's central derivations are self-contained. Theorem 3.1 constructs recursive bijections from D_{N,k}(132) and D_{N,k}(231) to ordered forests of s complete k-ary trees, and counts these forests by [z^m]T(z)^s = s/(mk+s) * binom(mk+s,m) via Lagrange inversion; the Raney number is not an input to the bijection. The 213/312 cases are obtained by completion lemmas and the proven reverse-complement symmetry, not by assuming the Fuss-Catalan count. The 321 formula is a direct RSK reduction: it expresses the class as a sum over two-row recording tableaux counted by the independently defined ballot-word statistic K_{N,k}(a), with f^{(N-a,a)} insertion tableaux; this is an exact reduction, not a renamed version of the output. The consecutive and one-adjacent vincular enumerations follow from local boundary analyses, insertion counts, and explicit posets; Lemmas 5.5, 5.6, and 5.2 are independent bijective/counting arguments. The only external citation used as a count is Lewis's k=2 Catalan result in Proposition 3.6, and that is a standard external benchmark confined to an exceptional case; it is not load-bearing for the k>=2 generalizations. There are no self-citations by the present authors and no uniqueness assertions imported from prior work of the same authors. The most compressed step, the assertion that no cross 132/231 occurrence appears in the inverse of the forest bijection, is a compact proof of a local separation property rather than a circular definition; even if one wanted more detail, the gap is one of exposition, not of circular dependence. The paper makes no claim to have evaluated K_{N,k}(a) in closed form, so leaving it as a defined ballot-word count is a scope choice. Overall the derivation chain reduces to independently checkable objects, not to its own conclusions.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted; all constants come from standard combinatorics. The posets P132, P213, P123, P321, and P321' are constructed boundary conditions, not postulates requiring independent evidence.

assumptions (4)
  • standard math Lagrange inversion gives [z^m]T(z)^s equal to the Raney number for T(z)=1+zT(z)^k
    Used in Eq. (1) to convert the forest bijections into the stated Raney counts.
  • standard math RSK correspondence: 321-avoiding permutations correspond to pairs of standard Young tableaux of shape with at most two rows, and descents of the permutation are descents of the recording tableau
    Basis of Theorem 3.7; standard but convention-sensitive.
  • standard math Rooted-tree hook-length formula counts linear extensions of rooted tree posets
    Used in Lemma 5.2 to compute the record-low count U.
  • domain assumption Lewis's k=2 Catalan enumeration of 123-avoiding alternating permutations
    External cited result [14] used for the exceptional k=2 rows in Proposition 3.6 and Theorem 4.1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Classical and vincular patterns of length three in generalized alternating permutations." pith.science (2026). https://pith.science/paper/USDMSMWF

@misc{pith2026260726507,
  author       = {Pith},
  title        = {Pith review of: Classical and vincular patterns of length three in generalized alternating permutations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/USDMSMWF}},
  note         = {Machine review of arXiv:2607.26507}
}
read the original abstract

Let k be an integer at least 2, and let D_{N,k} be the set of permutations of {1,...,N} whose descent set is exactly {k, 2k, ..., k*floor((N-1)/k)}. We enumerate the elements of D_{N,k} avoiding each classical and each vincular pattern of length three. For classical patterns, we give recursive bijections from the 132- and 231-avoiding classes to ordered forests of complete k-ary trees, obtaining the Raney number. The 213- and 312-avoiding classes are obtained from these forest bijections by completing the last block and applying reverse-complement symmetry. The remaining classical case 321 is expressed by RSK. For vincular patterns, we enumerate the six fully consecutive patterns and the twelve patterns with exactly one adjacency. The closed-form results are accompanied by bijective models: the Catalan, Raney, Fuss-Catalan, and RSK cases are natural k-ary or fixed-descent extensions of classical bijections, while the product and poset cases arise from block-insertion and record/tree-poset encodings forced by the adjacency conditions.

Figures

Figures reproduced from arXiv: 2607.26507 by the authors.

Figure 1
Figure 1. Illustration of the recursive bijection in Theorem 3.1 for the two permutations in 5,3 (132). Each permutation maps to a forest of two complete 3-ary trees with one internal vertex. 3.2. The patterns 213 and 312 The following two elementary completion lemmas are the point at which the incomplete last block must be treated carefully. Lemma 3.3. Let 𝜋 ∈ 𝑚𝑘+𝑠,𝑘(312). Then the entries 𝑥𝑚+1,2 ,…, 𝑥𝑚+1,𝑠, when present, … view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

24 extracted references

  1. [1]

    Generalized permutation patterns and a classification of the Mahonian statistics

    Babson, E., Steingrimsson, E., 2000. Generalized permutation patterns and a classification of the Mahonian statistics. Sém. Lothar. Combin. 44, Article B44b, 18 pp

    2000

  2. [2]

    Combinatorics of Permutations

    Bóna, M., 2012. Combinatorics of Permutations. Discrete Mathematics and its Applications. 2nd ed., CRC Press, Boca Raton, FL

    2012

  3. [3]

    On a family of conjectures of Joel Lewis on alternating permutations

    Bóna, M., 2014. On a family of conjectures of Joel Lewis on alternating permutations. Graphs Combin. 30, 521–526

    2014

  4. [4]

    On pattern avoiding alternating permutations

    Chen, J.N., Chen, W.Y.C., Zhou, R.D.P., 2014. On pattern avoiding alternating permutations. European J. Combin. 40, 11–25

    2014

  5. [5]

    Generalized pattern avoidance

    Claesson, A., 2001. Generalized pattern avoidance. European J. Combin. 22, 961–971

    2001

  6. [6]

    A survey of consecutive patterns in permutations, in: Recent Trends in Combinatorics

    Elizalde, S., 2016. A survey of consecutive patterns in permutations, in: Recent Trends in Combinatorics. Springer, Cham. volume 159 ofIMA Vol. Math. Appl., pp. 601–618

    2016

  7. [7]

    Consecutive patterns in permutations

    Elizalde, S., Noy, M., 2003. Consecutive patterns in permutations. Adv. in Appl. Math. 30, 110–125

    2003

  8. [8]

    The hook graphs of the symmetric group

    Frame, J.S., Robinson, G.d.B., Thrall, R.M., 1954. The hook graphs of the symmetric group. Canad. J. Math. 6, 316–324

    1954

Show all 24 references
  1. [9]

    Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux

    Gowravaram, N., Jagadeesan, R., 2013. Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux. Electron. J. Combin. 20

    2013

  2. [10]

    Ascent-descent Young diagrams and pattern avoidance in alternating permutations

    Jagadeesan, R., 2014. Ascent-descent Young diagrams and pattern avoidance in alternating permutations. Electron. J. Combin. 21

    2014

  3. [11]

    Patterns in Permutations and Words

    Kitaev, S., 2011. Patterns in Permutations and Words. Monographs in Theoretical Computer Science. An EATCS Series, Springer, Heidelberg

    2011

  4. [12]

    Permutations, matrices, and generalized Young tableaux

    Knuth, D.E., 1970. Permutations, matrices, and generalized Young tableaux. Pacific J. Math. 34, 709–727

    1970

  5. [13]

    The Art of Computer Programming, Vol

    Knuth, D.E., 1973. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, MA

    1973

  6. [14]

    Alternating, pattern-avoiding permutations

    Lewis, J.B., 2009. Alternating, pattern-avoiding permutations. Electron. J. Combin. 16

    2009

  7. [15]

    Pattern avoidance in alternating permutations and tableaux, in: Discrete Math

    Lewis, J.B., 2010. Pattern avoidance in alternating permutations and tableaux, in: Discrete Math. Theor. Comput. Sci. Proc., pp. 391–402

    2010

  8. [16]

    Pattern avoidance for alternating permutations and Young tableaux

    Lewis, J.B., 2011. Pattern avoidance for alternating permutations and Young tableaux. J. Combin. Theory Ser. A 118, 1436–1450

    2011

  9. [17]

    Generating trees and pattern avoidance in alternating permutations

    Lewis, J.B., 2012. Generating trees and pattern avoidance in alternating permutations. Electron. J. Combin. 19

    2012

  10. [18]

    Restricted132-alternating permutations and Chebyshev polynomials

    Mansour, T., 2003. Restricted132-alternating permutations and Chebyshev polynomials. Ann. Comb. 7, 201–227

    2003

  11. [19]

    Functional composition patterns and power series reversion

    Raney, G.N., 1960. Functional composition patterns and power series reversion. Trans. Amer. Math. Soc. 94, 441–451

    1960

  12. [20]

    Longest increasing and decreasing subsequences

    Schensted, C., 1961. Longest increasing and decreasing subsequences. Canad. J. Math. 13, 179–191

    1961

  13. [21]

    Restricted permutations

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

    1985

  14. [22]

    Enumerative Combinatorics, Vol

    Stanley, R.P., 1999. Enumerative Combinatorics, Vol. 2. volume 62 ofCambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge

    1999

  15. [23]

    A survey of alternating permutations, in: Combinatorics and Graphs

    Stanley, R.P., 2010. A survey of alternating permutations, in: Combinatorics and Graphs. Amer. Math. Soc., Providence, RI. volume 531 of Contemp. Math., pp. 165–196

    2010

  16. [24]

    Alternating permutations with restrictions and standard Young tableaux

    Xu, Y.X., Yan, S.H.F., 2012. Alternating permutations with restrictions and standard Young tableaux. Electron. J. Combin. 19. CRediT authorship contribution statement Zhenhua Luo:Methodology, Investigation.Junting Wang:Investigation, Validation.Ziyi Yang:Writing – review & edi...

    2012

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.