betaFeedback

WorksMathematics

Counting formulas and refined generating functions for inversion-sequence Classes 152 and 207

Abstract

For the two Class 152 pattern sets, we prove that the common number of inversion sequences of length n≥1n\geq 1 is an=1+∑j=1n−1(2jj)a_n=1+\sum_{j=1}^{n-1}\binom{2j}{j}. The Class 152 proof uses first-descent and last-zero decompositions, with weighted Dyck paths evaluating the resulting generating functions. For Class 207, we prove equality of the three total-count series and give their common generating function as an explicit Lambert-series expression after the substitution z=q/(1+q)2z=q/(1+q)^2. Complete legal-site and catalytic recurrences lead to a Lambert series for one class and qq-product orbit sums for another. A cubic limit of the balanced nonterminating 3ϕ2{}_3ϕ_2 qq-Saalschutz summation identifies these expressions. Fixed-maximum expansions, finite verification data, refined analytic obstructions, and signed specializations are recorded in the supplementary material.

Introduction

An inversion sequence of length nn is a word e0⋯en−1e_0 \cdots e_{n-1} with 0≤ei≤i0 \le e_i \le i. Patterns occur in subsequences, with all equalities and strict inequalities retained. Write In(X)\mathcal{I}_n(X) for the sequences avoiding the pattern set XX, and GX(z)=∑n≥0∣In(X)∣znG_X(z) = \sum_{n \ge0} |\mathcal{I}_n(X)|z^n. The index nn is the number of entries. In the notation of Callan–Mansour [8], a word e0⋯eme_0 \cdots e_m belongs to Im(X)\mathcal{I}_m(X); thus their index is one less than its length. We use the length convention throughout.

The systematic study of length-three patterns in inversion sequences was initiated by Corteel, Martinez, Savage and Weselcouch [10] and Mansour and Shattuck [16]. Martinez and Savage [17] organized a broader classification by triples of relations, and Lin [14] studied such restrictions in inversion and ascent sequences. For sets of ordinary patterns, Yan and Lin [26] investigated pairs, Callan, Jelínek and Mansour [7] triples, and Callan and Mansour [8] quadruples; the last

Email addresses: [email protected] (Haobo Ma), [email protected] (Toufik Mansour), [email protected] (Wenlin Zhang) classification is the source of the two conjectures addressed here. Related work develops statistic refinements for restricted inversion sequences [15], consecutive-pattern enumeration [2], and vincular Wilf equivalences [3]. These adjacency-restricted occurrences use different conventions from the subsequence occurrences considered here.

Generating trees give both structural descriptions and catalytic equations: Kotsireas, Mansour and Yıldırım [13] give an algorithmic approach for inversion sequences, while Testart [24] uses trees growing on the left for further pattern classes. Britt and Beaton [6] complete the enumeration of the triples-of-relations classification using left- and right-growing trees. Within the quadruple classification, Asinowski and Polley [1, Section 4.1] resolve Class 166 through rectangulations. Here we resolve Classes 152 and 207; the Class 207 proof evaluates the published B tree and our C legal-site recurrence and identifies their total-count series by a classical qq-summation.

Callan–Mansour’s numbering [8 Table 1, p. 28] is

207(1)=A={100,101,110,201},207(2)=C={100,101,110,210},207(3)=B={101,110,120,210}.\begin{aligned} 207(1) &= A = \{100,101,110,201\},\\ 207(2) &= C = \{100,101,110,210\},\\ 207(3) &= B = \{101,110,120,210\}. \end{aligned}

Their bijection [8 Section 4.10] gives GA=GCG_A=G_C: in the strict left-to-right-maximum decomposition, leave the maximum blocks fixed and refill the intervening boxes from left to right with the largest available entry below the corresponding maximum.

For Class 152, cutting at the first descent describes one class by a nondecreasing prefix and a suffix whose nonmaximum entries lie in one gap between prefix values. Cutting at the last zero describes the other by a prefix with increasing positive entries and a suffix of rotated increasing blocks. Dyck paths encode the prefixes, and weights on their down-runs evaluate both decompositions as the same generating function.

The more involved Class 207 step is GC(z)=GB(z)G_C(z)=G_B(z). The C legal-site system gives a kernel equation whose two roots eliminate the diagonal boundary; symmetry and a second-derivative condition then determine the total as a Lambert series. The published B tree gives two qq-product orbit sums. To identify their difference, we specialize the balanced nonterminating 3ϕ2{}_3\phi_2 qq-Saalschütz summation [21 Eq. 17.7.5]. Its multiplier has a triple pole in the limiting parameter. The linear and quadratic terms of the logarithmic product expansion cancel, leaving the cubic term that produces the Lambert series. The transformed tail retains the initial B orbit term; a uniform geometric bound justifies termwise passage to the limit. Section 6 gives the specialization and the passage back to formal length series.

The paper has two focused enumeration results. Section 2 derives the complete C legal-site recurrence and its catalytic equations. Sections 3–5 give the corresponding B system and the two kernel reductions. Section 6 proves the common Class 207 generating function, and Section 7 proves the Class 152 formula by two direct decompositions. The expanded supplementary material records the fixed-maximum rational expansion, numerical checks, the auxiliary B-boundary calculation, refined analytic obstructions, signed specializations, and the reproducibility code.

An explicit recurrence for 207(2)

For a nonempty CC-avoiding prefix ww of length nn, let M=max⁡wM=\max w and write s=n−M>1s=n-M>1 for the slack, called the bounce statistic in Asinowski–Polley [1, Section 2.2]. List its admissible next values at most MM in increasing order as a word pp: write SS for a value already seen and UU for an unused value. Let h=1h=1 if MM is admissible, and h=0h=0 otherwise. All values M+1,…,nM+1,\ldots,n are admissible. The initial word 0 has state (S,1,1)(S,1,1).

We use the labelled generating-tree framework of West [25]. Its translation into generating functions follows the general approach of Banderier et al. [4]. The complete succession rule is as follows; each choice is counted once:

(p,s,h)⟶(pUj−1S,s−j+1,1),1≤j≤s;(1)(p,s,h)\longrightarrow(pU^{j-1}S,s-j+1,1), \qquad1\leq j\leq s; \tag*{(1)}
(p,s,1)⟶(S,s+1,1),repeat M;(2)(p,s,1)\longrightarrow(S,s+1,1), \qquad\text{repeat }M; \tag*{(2)}
(p,s,h)⟶(Uk,s+1,0),select a site below M.(3)(p,s,h)\longrightarrow(U^k,s+1,0), \qquad\text{select a site below }M. \tag*{(3)}

In the last line, kk is the number of unused sites strictly to the right of the selected site. An equal pair a,aa,a forbids a later entry below aa by 110. A descent a>ba>b forbids entries at most bb by 100, 210, and forbids aa by 101. Thus selecting x<Mx<M removes all sites at most xx and all seen sites above xx, leaving precisely the kk unused sites. Repeating MM leaves only its own site; a new maximum introduces no new exclusion. This proves the rule and shows why gaps between listed sites do not affect it.

For r≥0r\geq0, s≥1s\geq1 and k≥0k\geq0, let ar(s,k)a_r(s,k) count continuations of rr further entries from the formal state (Uk,s,0)(U^k,s,0), and let br(s)b_r(s) count them from (S,s,1)(S,s,1). The rules above define these numbers even when a state is not reached from the root.

Proposition 1. The initial conditions are a0(s,k)=b0(s)=1a_0(s,k)=b_0(s)=1. For r≥0r\geq0,

ar+1(s,k)=∑i=0k−1ar(s+1,i)+∑j=1s(ar(s−j+1,k+j−1)+br(s−j+1)−ar(s−j+1,0)).(4)a_{r+1}(s,k)=\sum_{i=0}^{k-1}a_r(s+1,i)+\sum_{j=1}^{s}\left(a_r(s-j+1,k+j-1)+b_r(s-j+1)-a_r(s-j+1,0)\right). \tag*{(4)}
br+1(s)=br(s+1)+∑j=1s(ar(s−j+1,j)+br(s−j+1)−ar(s−j+1,0)).(5)b_{r+1}(s)=b_r(s+1)+\sum_{j=1}^{s}\left(a_r(s-j+1,j)+b_r(s-j+1)-a_r(s-j+1,0)\right). \tag*{(5)}

Empty sums are zero. In particular,

∣I0(C)∣=1,∣In(C)∣=bn−1(1)(n≥1).(6)|\mathcal{I}_0(C)|=1,\qquad|\mathcal{I}_n(C)|=b_{n-1}(1)\qquad(n\geq1). \tag*{(6)}

These are recurrences for nonnegative integers; the differences in the formulas come from an affine reduction of the site word.

Proof. For a site aa in pp, let k(a)k(a) count unused sites strictly to its right, and put Tp(y)=∑a∈pyk(a)T_p(y)=\sum_{a\in p}y^{k(a)}. Write ϕr(p,s,h)\phi_r(p,s,h) for the number of continuations of length rr. We first prove that it is affine in hh and the coefficients of TpT_p, for fixed r,sr,s. At r=0r=0 it is 1. For the induction step, lower selections and a possible repetition of MM contribute

∑a∈par(s+1,k(a))+h(br(s+1)−ar(s+1,0)).\sum_{a\in p}a_r(s+1,k(a))+h\left(b_r(s+1)-a_r(s+1,0)\right).

For a new maximum, the child’s site polynomial is

TpUj−1S(y)=yj−1Tp(y)+1−yj−11−y+1.(7)T_{pU^{j-1}S}(y)=y^{j-1}T_p(y)+\frac{1-y^{j-1}}{1-y}+1. \tag*{(7)}

so its contribution is also affine by induction. Evaluating this affine function on the empty word, on UkU^k, and on S gives

ϕr(p,s,h)=ar(s,0)+h(br(s)−ar(s,1))+∑a∈P(ar(s,k(a)+1)−ar(s,k(a))).(8)\phi_r(p,s,h)=a_r(s,0)+h\bigl(b_r(s)-a_r(s,1)\bigr)+\sum_{a\in P}\bigl(a_r(s,k(a)+1)-a_r(s,k(a))\bigr). \tag*{(8)}

Indeed, TUk+1−TUk=ykT_{U^{k+1}}-T_{U^k}=y^k and TS=TU=1T_S=T_U=1. Apply (8) to the new-maximum children Uk+j−1SU^{k+j-1}S and SUj−1SSU^{j-1}S; their continuation counts are respectively ar(s′,k+j−1)+br(s′)−ar(s′,0)a_r(s',k+j-1)+b_r(s')-a_r(s',0) and ar(s′,j)+br(s′)−ar(s′,0)a_r(s',j)+b_r(s')-a_r(s',0), where s′=s−j+1s'=s-j+1. The lower children of UkU^k are U0,…,Uk−1U^0,\ldots,U^{k-1}; the repetition child of S is S with slack s+1s+1. This proves (4)–(5). The root has length one, which proves (6).

For example, a1(s,k)=s+ka_1(s,k)=s+k and b1(s)=s+1b_1(s)=s+1. To calculate all counts through length NN, at depth rr it suffices to retain ar(s,k)a_r(s,k) for s+k≤N−rs+k\le N-r and br(s)b_r(s) for s≤N−rs\le N-r. Row and diagonal partial sums evaluate (4)–(5) in O(N3)O(N^3) integer operations and O(N2)O(N^2) stored integers; ?? of the supplement gives the complete program.

Catalytic equations and their proof

For CC, let the sums below run over all nonempty CC-avoiding inversion prefixes. Define

References

  1. [2]J. S. Auli and S. Elizalde, Consecutive Patterns in Inversion Sequences, Discrete Mathematics & Theoretical Computer Science 21(2) (2019), Paper 6. doi:10.23638/dmtcs-21-2-6.DOI
  2. [3]J. S. Auli and S. Elizalde, Wilf equivalences between vincular patterns in inversion sequences, Applied Mathematics and Computation 388 (2021), 125514. doi:10.1016/j.amc.2020.125514.DOI
  3. [4]C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating functions for generating trees, Discrete Mathematics 246 (2002), 29–55. doi:10.1016/S0012-365X(01)00250-3.DOI
  4. [5]M. Bousquet-Mélou, Counting permutations with no long monotone subsequence via generating trees and the kernel method, Journal of Algebraic Combinatorics 33 (2011), 571–608. doi:10.1007/s10801-010-0259-z.
  5. [6]N. Britt and N. Beaton, Completing the enumeration of inversion sequences avoiding triples of relations, Discrete Mathematics & Theoretical Computer Science 28(1) (2026), Paper 8. doi:10.46298/dmtcs.17203.DOI
  6. [7]D. Callan, V. Jelínek and T. Mansour, Inversion Sequences Avoiding a Triple of Patterns of 3 Letters, The Electronic Journal of Combinatorics 30(3) (2023), Paper P3.19. doi:10.37236/11603.DOI
  7. [8]D. Callan and T. Mansour, Inversion sequences avoiding quadruple length-3 patterns, Integers 23 (2023), Paper A78. doi:10.5281/zenodo.8399694.DOI
  8. [9]S. Chen and M. F. Singer, Residues and telescopers for bivariate rational functions, Advances in Applied Mathematics 49 (2012), 111–133. doi:10.1016/j.aam.2012.04.003.DOI
  9. [10]S. Corteel, M. A. Martinez, C. D. Savage and M. Welscelouch, Patterns in Inversion Sequences I, Discrete Mathematics & Theoretical Computer Science 18(2) (2016), Paper 2. doi:10.46298/dmtcs.1323.DOI
  10. [11]L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language, in Automated Deduction—CADE 28, Lecture Notes in Computer Science, vol. 12699, Springer, 2021, pp. 625–635. Publisher record.DOI
  11. [12]G. Gasper and M. Rahman, Basic Hypergeometric Series, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 96, Cambridge University Press, Cambridge, 2004. Publisher record.
  12. [13]I. Kotsireas, T. Mansour and G. Yıldırım, An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences, Journal of Symbolic Computation 120 (2024), 102231. doi:10.1016/j.jsc.2023.102231.
  13. [14]Z. Lin, Patterns of relation triples in inversion and ascent sequences, Theoretical Computer Science 804 (2020), 115–125. doi:10.1016/j.tcs.2019.11.007.DOI
  14. [15]Z. Lin and D. Kim, Refined Restricted Inversion Sequences, Annals of Combinatorics 25(4) (2021), 849–875. doi:10.1007/s00026-021-00550-7.DOI
  15. [16]T. Mansour and M. Shattuck, Pattern avoidance in inversion sequences, Pure Mathematics and Applications 25(2) (2015), 157–176. doi:10.1515/puma-2015-0016.DOI
  16. [17]M. A. Martinez and C. D. Savage, Patterns in inversion sequences II: inversion sequences avoiding triples of relations, Journal of Integer Sequences 21 (2018), Article 18.2.2. arXiv:1609.08106. https://cs.uwaterloo.ca/journals/JIS/VOL21/Martinez/mart2.pdf.arxiv.org/abs/1609.08106
  17. [18]The mathlib Community, The Lean mathematical library, in Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs, ACM, 2020, pp. 367–381. doi:10.1145/3372885.3373824.DOI
  18. [19]A. Meurer et al., SymPy: symbolic computing in Python, PeerJ Computer Science 3 (2017), e103. doi:10.7717/peerj-cs.103.DOI
  19. [20]The mpmath development team, mpmath: a Python library for arbitrary-precision floating-point arithmetic, version 1.3.0, 2023. https://mpmath.org/doc/1.3.0/ (accessed 30 October 2026).
  20. [21]NIST Digital Library of Mathematical Functions, Section 17.7(ii), Eq. 17.7.5, nonterminating q-Saalschütz sum. https://dlmf.nist.gov/17.7.E5 (accessed 30 October 2026).
  21. [22]OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, entry A024718, “a(n) = (1 + ∑ₖ₌₀ⁿ (2k choose k))/2”, https://oeis.org/A024718 (accessed 30 October 2026).
  22. [23]Python Software Foundation, The Python Language Reference, Python 3 documentation, 2026. https://docs.python.org/3/reference/ (accessed 30 October 2026).
  23. [24]B. Testart, Generating trees growing on the left for pattern-avoiding inversion sequences, Discrete Mathematics & Theoretical Computer Science 27(1) (2025), Paper 10. doi:10.46298/dmtcs.14716.DOI
  24. [25]J. West, Generating trees and forbidden subsequences, Discrete Mathematics 157 (1996), 363–374. doi:10.1016/S0012-365X(96)83023-8.DOI
  25. [26]C. Yan and Z. Lin, Inversion sequences avoiding pairs of patterns, Discrete Mathematics & Theoretical Computer Science 22(1) (2020), Paper 23. doi:10.26338/dmtcs-22-1-23.DOI

Paper details

vlnc:W_re2ve4ye
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT Pro, Codex, Claude Opus 5.5

View statement
Looking for related papers…
Contents