Introduction
An inversion sequence of length n n n is a word e 0 ⋯ e n − 1 e_0 \cdots e_{n-1} e 0 ⋯ e n − 1 with 0 ≤ e i ≤ i 0 \le e_i \le i 0 ≤ e i ≤ i . Patterns occur in subsequences, with all equalities and strict inequalities retained. Write I n ( X ) \mathcal{I}_n(X) I n ( X ) for the sequences avoiding the pattern set X X X , and G X ( z ) = ∑ n ≥ 0 ∣ I n ( X ) ∣ z n G_X(z) = \sum_{n \ge0} |\mathcal{I}_n(X)|z^n G X ( z ) = ∑ n ≥ 0 ∣ I n ( X ) ∣ z n . The index n n n is the number of entries. In the notation of Callan–Mansour [8 ] , a word e 0 ⋯ e m e_0 \cdots e_m e 0 ⋯ e m belongs to I m ( X ) \mathcal{I}_m(X) 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: auric@aelf.io (Haobo Ma), tmansour@univ.haifa.ac.il (Toufik Mansour), e1327962@u.nus.edu (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 q q q -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} 207 ( 1 ) 207 ( 2 ) 207 ( 3 ) = A = { 100 , 101 , 110 , 201 } , = C = { 100 , 101 , 110 , 210 } , = B = { 101 , 110 , 120 , 210 } .
Their bijection [8 Section 4.10] gives G A = G C G_A=G_C G 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 G C ( z ) = G B ( z ) G_C(z)=G_B(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 q q q -product orbit sums. To identify their difference, we specialize the balanced nonterminating 3 ϕ 2 {}_3\phi_2 3 ϕ 2 q q q -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 C C C -avoiding prefix w w w of length n n n , let M = max w M=\max w M = max w and write s = n − M > 1 s=n-M>1 s = n − M > 1 for the slack, called the bounce statistic in Asinowski–Polley [1, Section 2.2]. List its admissible next values at most M M M in increasing order as a word p p p : write S S S for a value already seen and U U U for an unused value. Let h = 1 h=1 h = 1 if M M M is admissible, and h = 0 h=0 h = 0 otherwise. All values M + 1 , … , n M+1,\ldots,n M + 1 , … , n are admissible. The initial word 0 has state ( S , 1 , 1 ) (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 ) ⟶ ( p U j − 1 S , 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 , h ) ⟶ ( p U j − 1 S , s − j + 1 , 1 ) , 1 ≤ j ≤ s ; (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 , 1 ) ⟶ ( S , s + 1 , 1 ) , repeat M ; (2)
( p , s , h ) ⟶ ( U k , 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)} ( p , s , h ) ⟶ ( U k , s + 1 , 0 ) , select a site below M . (3)
In the last line, k k k is the number of unused sites strictly to the right of the selected site. An equal pair a , a a,a a , a forbids a later entry below a a a by 110. A descent a > b a>b a > b forbids entries at most b b b by 100, 210, and forbids a a a by 101. Thus selecting x < M x<M x < M removes all sites at most x x x and all seen sites above x x x , leaving precisely the k k k unused sites. Repeating M M M 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 ≥ 0 r\geq0 r ≥ 0 , s ≥ 1 s\geq1 s ≥ 1 and k ≥ 0 k\geq0 k ≥ 0 , let a r ( s , k ) a_r(s,k) a r ( s , k ) count continuations of r r r further entries from the formal state ( U k , s , 0 ) (U^k,s,0) ( U k , s , 0 ) , and let b r ( s ) b_r(s) b r ( s ) count them from ( S , s , 1 ) (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 a 0 ( s , k ) = b 0 ( s ) = 1 a_0(s,k)=b_0(s)=1 a 0 ( s , k ) = b 0 ( s ) = 1 . For r ≥ 0 r\geq0 r ≥ 0 ,
a r + 1 ( s , k ) = ∑ i = 0 k − 1 a r ( s + 1 , i ) + ∑ j = 1 s ( a r ( s − j + 1 , k + j − 1 ) + b r ( s − j + 1 ) − a r ( 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)} a r + 1 ( s , k ) = i = 0 ∑ k − 1 a r ( s + 1 , i ) + j = 1 ∑ s ( a r ( s − j + 1 , k + j − 1 ) + b r ( s − j + 1 ) − a r ( s − j + 1 , 0 ) ) . (4) b r + 1 ( s ) = b r ( s + 1 ) + ∑ j = 1 s ( a r ( s − j + 1 , j ) + b r ( s − j + 1 ) − a r ( 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)} b r + 1 ( s ) = b r ( s + 1 ) + j = 1 ∑ s ( a r ( s − j + 1 , j ) + b r ( s − j + 1 ) − a r ( s − j + 1 , 0 ) ) . (5) Empty sums are zero. In particular,
∣ I 0 ( C ) ∣ = 1 , ∣ I n ( C ) ∣ = b n − 1 ( 1 ) ( n ≥ 1 ) . (6) |\mathcal{I}_0(C)|=1,\qquad|\mathcal{I}_n(C)|=b_{n-1}(1)\qquad(n\geq1). \tag*{(6)} ∣ I 0 ( C ) ∣ = 1 , ∣ I n ( C ) ∣ = b n − 1 ( 1 ) ( n ≥ 1 ) . (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 a a a in p p p , let k ( a ) k(a) k ( a ) count unused sites strictly to its right, and put T p ( y ) = ∑ a ∈ p y k ( a ) T_p(y)=\sum_{a\in p}y^{k(a)} T p ( y ) = ∑ a ∈ p y k ( a ) . Write ϕ r ( p , s , h ) \phi_r(p,s,h) ϕ r ( p , s , h ) for the number of continuations of length r r r . We first prove that it is affine in h h h and the coefficients of T p T_p T p , for fixed r , s r,s r , s . At r = 0 r=0 r = 0 it is 1. For the induction step, lower selections and a possible repetition of M M M contribute
∑ a ∈ p a r ( s + 1 , k ( a ) ) + h ( b r ( s + 1 ) − a r ( 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). a ∈ p ∑ a r ( s + 1 , k ( a )) + h ( b r ( s + 1 ) − a r ( s + 1 , 0 ) ) .
For a new maximum, the child’s site polynomial is
T p U j − 1 S ( y ) = y j − 1 T p ( y ) + 1 − y j − 1 1 − 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)} T p U j − 1 S ( y ) = y j − 1 T p ( y ) + 1 − y 1 − y j − 1 + 1. (7)
so its contribution is also affine by induction. Evaluating this affine function on the empty word, on U k U^k U k , and on S gives
ϕ r ( p , s , h ) = a r ( s , 0 ) + h ( b r ( s ) − a r ( s , 1 ) ) + ∑ a ∈ P ( a r ( s , k ( a ) + 1 ) − a r ( 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)} ϕ r ( p , s , h ) = a r ( s , 0 ) + h ( b r ( s ) − a r ( s , 1 ) ) + a ∈ P ∑ ( a r ( s , k ( a ) + 1 ) − a r ( s , k ( a )) ) . (8)
Indeed, T U k + 1 − T U k = y k T_{U^{k+1}}-T_{U^k}=y^k T U k + 1 − T U k = y k and T S = T U = 1 T_S=T_U=1 T S = T U = 1 . Apply (8) to the new-maximum children U k + j − 1 S U^{k+j-1}S U k + j − 1 S and S U j − 1 S SU^{j-1}S S U j − 1 S ; their continuation counts are respectively a r ( s ′ , k + j − 1 ) + b r ( s ′ ) − a r ( s ′ , 0 ) a_r(s',k+j-1)+b_r(s')-a_r(s',0) a r ( s ′ , k + j − 1 ) + b r ( s ′ ) − a r ( s ′ , 0 ) and a r ( s ′ , j ) + b r ( s ′ ) − a r ( s ′ , 0 ) a_r(s',j)+b_r(s')-a_r(s',0) a r ( s ′ , j ) + b r ( s ′ ) − a r ( s ′ , 0 ) , where s ′ = s − j + 1 s'=s-j+1 s ′ = s − j + 1 . The lower children of U k U^k U k are U 0 , … , U k − 1 U^0,\ldots,U^{k-1} U 0 , … , U k − 1 ; the repetition child of S is S with slack s + 1 s+1 s + 1 . This proves (4)–(5). The root has length one, which proves (6) .
For example, a 1 ( s , k ) = s + k a_1(s,k)=s+k a 1 ( s , k ) = s + k and b 1 ( s ) = s + 1 b_1(s)=s+1 b 1 ( s ) = s + 1 . To calculate all counts through length N N N , at depth r r r it suffices to retain a r ( s , k ) a_r(s,k) a r ( s , k ) for s + k ≤ N − r s+k\le N-r s + k ≤ N − r and b r ( s ) b_r(s) b r ( s ) for s ≤ N − r s\le N-r s ≤ N − r . Row and diagonal partial sums evaluate (4)–(5) in O ( N 3 ) O(N^3) O ( N 3 ) integer operations and O ( N 2 ) O(N^2) O ( N 2 ) stored integers; ?? of the supplement gives the complete program.
Catalytic equations and their proof
For C C C , let the sums below run over all nonempty C C C -avoiding inversion prefixes. Define
F C ( x ) = ∑ w z ∣ w ∣ x s ( w ) , P C ( x ) = ∑ w z ∣ w ∣ x s ( w ) h ( w ) , H C ( x , y ) = ∑ w z ∣ w ∣ x s ( w ) T p ( w ) ( y ) . F_C(x)=\sum_w z^{|w|}x^{s(w)},\qquad P_C(x)=\sum_w z^{|w|}x^{s(w)}h(w),\qquad H_C(x,y)=\sum_w z^{|w|}x^{s(w)}T_{p(w)}(y). F C ( x ) = w ∑ z ∣ w ∣ x s ( w ) , P C ( x ) = w ∑ z ∣ w ∣ x s ( w ) h ( w ) , H C ( x , y ) = w ∑ z ∣ w ∣ x s ( w ) T p ( w ) ( y ) .
Throughout this paper, F X ( x ) F_X(x) F X ( x ) and P X ( x ) P_X(x) P X ( x ) are univariate in the catalyst x x x , whereas H X ( x , y ) H_X(x,y) H X ( x , y ) and Z X ( x , y ) Z_X(x,y) Z X ( x , y ) are bivariate in the catalysts x , y x,y x , y . The length variable z z z is suppressed in these arguments, for example F X ( x ) = F X ( z ; x ) F_X(x)=F_X(z;x) F X ( x ) = F X ( z ; x ) . A specialization such as H X ( x , 1 ) H_X(x,1) H X ( x , 1 ) or H X ( y , y ) H_X(y,y) H X ( y , y ) always retains both argument positions. Put
J C ( x ) = z x F C ( x ) − F C ( 1 ) x − 1 . J_C(x)=zx\frac{F_C(x)-F_C(1)}{x-1}. J C ( x ) = z x x − 1 F C ( x ) − F C ( 1 ) .
The succession rule gives
F C ( x ) = z x + z x H C ( x , 1 ) + J C ( x ) , (9) F_C(x)=zx+zxH_C(x,1)+J_C(x), \tag*{(9)} F C ( x ) = z x + z x H C ( x , 1 ) + J C ( x ) , (9)
P C ( x ) = z x + z x P C ( x ) + J C ( x ) , (10) P_C(x)=zx+zxP_C(x)+J_C(x), \tag*{(10)} P C ( x ) = z x + z x P C ( x ) + J C ( x ) , (10)
H C ( x , y ) = z x + z x P C ( x ) + z x 1 − y ( H C ( x , 1 ) − H C ( x , y ) ) + z x x − y ( H C ( x , y ) − H C ( y , y ) ) + 2 − y 1 − y J C ( x ) − z x ( F C ( x ) − F C ( y ) ) ( 1 − y ) ( x − y ) . (11) \begin{aligned}
H_C(x,y)={}&zx+zxP_C(x)+\frac{zx}{1-y}\bigl(H_C(x,1)-H_C(x,y)\bigr)\\
&+\frac{zx}{x-y}\bigl(H_C(x,y)-H_C(y,y)\bigr)+\frac{2-y}{1-y}J_C(x)-\frac{zx\bigl(F_C(x)-F_C(y)\bigr)}{(1-y)(x-y)}. \tag*{(11)}
\end{aligned} H C ( x , y ) = z x + z x P C ( x ) + 1 − y z x ( H C ( x , 1 ) − H C ( x , y ) ) + x − y z x ( H C ( x , y ) − H C ( y , y ) ) + 1 − y 2 − y J C ( x ) − ( 1 − y ) ( x − y ) z x ( F C ( x ) − F C ( y ) ) . (11)
The coefficient ring is Q [ x , y ] [ [ z ] ] \mathbb{Q}[x,y][[z]] Q [ x , y ] [[ z ]] ; for a univariate series use Q [ x ] [ [ z ] ] \mathbb{Q}[x][[z]] Q [ x ] [[ z ]] . Apparent singularities in these equations are removable coefficientwise. In particular, terms with denominator 1 − y 1-y 1 − y must be combined before setting y = 1 y=1 y = 1 . All constant terms in z z z are zero, and
G C ( z ) = 1 + F C ( 1 ) = 1 + ∑ r ≥ 0 b r ( 1 ) z r + 1 . G_C(z)=1+F_C(1)=1+\sum_{r\ge0}b_r(1)z^{r+1}. G C ( z ) = 1 + F C ( 1 ) = 1 + r ≥ 0 ∑ b r ( 1 ) z r + 1 .
Proof of (9)–(11). The root contributes z x zx z x to each series. For a parent with slack s s s , the new maxima have slacks s − j + 1 s-j+1 s − j + 1 , 1 ≤ j ≤ s 1\le j\le s 1 ≤ j ≤ s , and
∑ j = 1 s x s − j + 1 = x ( x s − 1 ) x − 1 , ∑ j = 1 s x s − j + 1 y j − 1 = x ( x s − y s ) x − y . (12) \sum_{j=1}^{s}x^{s-j+1}=\frac{x(x^s-1)}{x-1},\qquad\sum_{j=1}^{s}x^{s-j+1}y^{j-1}=\frac{x(x^s-y^s)}{x-y}. \tag*{(12)} j = 1 ∑ s x s − j + 1 = x − 1 x ( x s − 1 ) , j = 1 ∑ s x s − j + 1 y j − 1 = x − y x ( x s − y s ) . (12)
The first identity gives J C ( x ) J_C(x) J C ( x ) in F C ( x ) F_C(x) F C ( x ) and P C ( x ) P_C(x) P C ( x ) . Every admissible site at most M M M gives a child with slack s + 1 s+1 s + 1 , so their total contribution to F C ( x ) F_C(x) F C ( x ) is z x H C ( x , 1 ) zxH_C(x,1) z x H C ( x , 1 ) . Among them, only repetition of an admissible M M M has an admissible maximum afterward; it contributes z x P C ( x ) zxP_C(x) z x P C ( x ) to P C ( x ) P_C(x) P C ( x ) . These observations prove (9) and (10) .
For H C ( x , y ) H_C(x,y) H C ( x , y ) , repetition of M M M leaves the one-site word S, so contributes z x P C ( x ) zxP_C(x) z x P C ( x ) . A lower site a a a leaves U k ( a ) U^{k(a)} U k ( a ) , whose polynomial is ( 1 − y k ( a ) ) / ( 1 − y ) (1-y^{k(a)})/(1-y) ( 1 − y k ( a ) ) / ( 1 − y ) . Summing over all sites gives z x ( H C ( x , 1 ) − H C ( x , y ) ) / ( 1 − y ) zx(H_C(x,1)-H_C(x,y))/(1-y) z x ( H C ( x , 1 ) − H C ( x , y )) / ( 1 − y ) : the maximum site, when present, has k ( M ) = 0 k(M)=0 k ( M ) = 0 and contributes zero to this expression. For a new maximum, (7) separates the child’s polynomial into the old-site term and the term independent of the old sites. The old-site term, summed using the second identity in (12) , is z x ( H C ( x , y ) − H C ( y , y ) ) / ( x − y ) zx(H_C(x,y)-H_C(y,y))/(x-y) z x ( H C ( x , y ) − H C ( y , y )) / ( x − y ) . The independent term is ( 2 − y − y j − 1 ) / ( 1 − y ) (2-y-y^{j-1})/(1-y) ( 2 − y − y j − 1 ) / ( 1 − y ) ; its sum is
2 − y 1 − y J C ( x ) − z x ( F C ( x ) − F C ( y ) ) ( 1 − y ) ( x − y ) . \frac{2-y}{1-y}J_C(x)-\frac{zx(F_C(x)-F_C(y))}{(1-y)(x-y)}. 1 − y 2 − y J C ( x ) − ( 1 − y ) ( x − y ) z x ( F C ( x ) − F C ( y )) .
This accounts for every child exactly once and proves (11) . Both identities in (12) are finite geometric sums; thus each displayed quotient, after its indicated combination, is a polynomial at each length. Finally the factor z z z on each child contribution determines the coefficients recursively from the root.
207(3) and a common catalytic form
Here is a direct four-type generating tree for B B B . Let M M M , L L L be the largest and second largest entries, counting multiplicity; for the initial word 0 put L = 0 L=0 L = 0 . Define
D ( w ) = { w i : w i > w j for some j > i } , s = n − M , d = M − L . D(w)=\{w_i:w_i>w_j\text{ for some }j>i\},\qquad s=n-M,\qquad d=M-L. D ( w ) = { w i : w i > w j for some j > i } , s = n − M , d = M − L .
The types are R s R_s R s if M = L M=L M = L , and, when M > L M>L M > L ,
The root is R 1 R_1 R 1 , and the complete succession rule is
R s ⟶ R s + 1 , U s − j + 1 , j ( 1 ≤ j ≤ s ) , U s , d ⟶ R s + 1 , V s + 1 , k ( 1 ≤ k ≤ d ) , U s − j + 1 , j ( 1 ≤ j ≤ s ) , V s , d ⟶ V s + 1 , k ( 1 ≤ k ≤ d ) , W s − j + 1 , j ( 1 ≤ j ≤ s ) , W s , d ⟶ R s + 1 , V s + 1 , k ( 1 ≤ k < d ) , U s − j + 1 , j ( 1 ≤ j ≤ s ) . (13) \begin{aligned}
R_s&\longrightarrow R_{s+1},\quad U_{s-j+1,j}\ (1\le j\le s),\\
U_{s,d}&\longrightarrow R_{s+1},\quad V_{s+1,k}\ (1\le k\le d),\quad U_{s-j+1,j}\ (1\le j\le s),\\
V_{s,d}&\longrightarrow V_{s+1,k}\ (1\le k\le d),\quad W_{s-j+1,j}\ (1\le j\le s),\\
W_{s,d}&\longrightarrow R_{s+1},\quad V_{s+1,k}\ (1\le k<d),\quad U_{s-j+1,j}\ (1\le j\le s). \tag*{(13)}
\end{aligned} R s U s , d V s , d W s , d ⟶ R s + 1 , U s − j + 1 , j ( 1 ≤ j ≤ s ) , ⟶ R s + 1 , V s + 1 , k ( 1 ≤ k ≤ d ) , U s − j + 1 , j ( 1 ≤ j ≤ s ) , ⟶ V s + 1 , k ( 1 ≤ k ≤ d ) , W s − j + 1 , j ( 1 ≤ j ≤ s ) , ⟶ R s + 1 , V s + 1 , k ( 1 ≤ k < d ) , U s − j + 1 , j ( 1 ≤ j ≤ s ) . (13)
To prove the rule, an earlier pair a ≤ b a\le b a ≤ b forbids an appended x < a x<a x < a by 110 or 120; a descent a > b a>b a > b forbids x < b x<b x < b by 210 and x = a x=a x = a by 101. To identify their intersection, the pair consisting of the two largest entries forbids every x < L x<L x < L , while every earlier pair has its smaller entry at most L L L and forbids nothing larger by its inequality condition. The equality exclusions are exactly D ( w ) D(w) D ( w ) . Thus the legal next entries are [ L , n ] ∖ D ( w ) [L,n]\setminus D(w) [ L , n ] ∖ D ( w ) (also for the single-entry root). If M > L M>L M > L , the maximum occurs once. The two endpoints cannot both belong to D ( w ) D(w) D ( w ) : if every L L L occurs after M M M , a descent from L L L gives M , L , v M,L,v M , L , v with v < L v< L v < L , a 210. If some L L L occurs before M M M , a descent from M M M gives a later v < L v<L v < L ; then L , M , v L,M,v L , M , v is 120 when v < L v<L v < L , and 101 when v = L v=L v = L . If M = L M=L M = L and the maximum is repeated, a descent after its second occurrence gives 110, and a descent before that occurrence followed by the second maximum gives 101. Thus the maximum remains admissible. No earlier value lies strictly between L L L and M M M , so only the two endpoints can be excluded from [ L , M ] [L,M] [ L , M ] . Appending M + j M+j M + j has parameters ( s − j + 1 , j ) (s-j+1,j) ( s − j + 1 , j ) and type W W W precisely when the old M M M was excluded. Repeating a legal M M M gives R s + 1 R_{s+1} R s + 1 . Appending M − k < M M-k<M M − k < M gives V s + 1 , k V_{s+1,k} V s + 1 , k in the ranges displayed above. This also proves inductively that the four types exhaust all prefixes. The tree in [8 Table 1, p. 28] gives another enumeration of B B B .
The two explicit systems
For X = B , C X=B,C X = B , C , use the admissible sites of X X X and the definitions of p , h , T p p,h,T_p p , h , T p in Section 2. Define
F X ( x ) = ∑ w ∈ ⋃ n ≥ 1 I n ( X ) z ∣ w ∣ x s ( w ) , P X ( x ) = ∑ w ∈ ⋃ n ≥ 1 I n ( X ) z ∣ w ∣ x s ( w ) h ( w ) , F_X(x)=\sum_{w\in\bigcup_{n\geq1}\mathcal{I}_n(X)}z^{|w|}x^{s(w)},\qquad P_X(x)=\sum_{w\in\bigcup_{n\geq1}\mathcal{I}_n(X)}z^{|w|}x^{s(w)}h(w), F X ( x ) = w ∈ ⋃ n ≥ 1 I n ( X ) ∑ z ∣ w ∣ x s ( w ) , P X ( x ) = w ∈ ⋃ n ≥ 1 I n ( X ) ∑ z ∣ w ∣ x s ( w ) h ( w ) ,
H X ( x , y ) = ∑ w ∈ ⋃ n ≥ 1 I n ( X ) z ∣ w ∣ x s ( w ) T p ( w ) ( y ) , Z X ( x , y ) = H X ( x , y ) − P X ( x ) . H_X(x,y)=\sum_{w\in\bigcup_{n\geq1}\mathcal{I}_n(X)}z^{|w|}x^{s(w)}T_{p(w)}(y),\qquad Z_X(x,y)=H_X(x,y)-P_X(x). H X ( x , y ) = w ∈ ⋃ n ≥ 1 I n ( X ) ∑ z ∣ w ∣ x s ( w ) T p ( w ) ( y ) , Z X ( x , y ) = H X ( x , y ) − P X ( x ) .
Thus Z X ( x , y ) Z_X(x,y) Z X ( x , y ) sums the site polynomials with the maximum site removed: that site, if admissible, has weight y 0 = 1 y^0=1 y 0 = 1 . In both classes x x x marks the slack s = n − M s=n-M s = n − M , and a site’s exponent of y y y counts unused admissible sites strictly to its right. In particular, y y y is a catalytic variable recording the unused sites above a selected site; a prefix contributes a polynomial in y y y , rather than necessarily a single monomial. The unknowns in each system are P X ( x ) P_X(x) P X ( x ) , F X ( x ) F_X(x) F X ( x ) , Z X ( x , y ) Z_X(x,y) Z X ( x , y ) ; H X ( x , y ) = P X ( x ) + Z X ( x , y ) H_X(x,y)=P_X(x)+Z_X(x,y) H X ( x , y ) = P X ( x ) + Z X ( x , y ) is then recovered.
Proposition 2. For X = B X=B X = B , the complete system in ordinary functional-equation form is
P B ( x ) = z x + z x P B ( x ) + z x F B ( x ) − F B ( 1 ) x − 1 , (14) P_B(x)=zx+zxP_B(x)+zx\frac{F_B(x)-F_B(1)}{x-1}, \tag*{(14)} P B ( x ) = z x + z x P B ( x ) + z x x − 1 F B ( x ) − F B ( 1 ) , (14) F B ( x ) = P B ( x ) + z x Z B ( x , 1 ) , (15) F_B(x)=P_B(x)+zxZ_B(x,1), \tag*{(15)} F B ( x ) = P B ( x ) + z x Z B ( x , 1 ) , (15) Z B ( x , y ) = z x [ Z B ( x , 1 ) − Z B ( x , y ) 1 − y + Z B ( x , y ) + P B ( x ) − P B ( y ) x − y + 1 1 − y ( F B ( x ) − F B ( 1 ) x − 1 − F B ( x ) − F B ( y ) x − y ) ] . (16) Z_B(x,y)=zx\left[\frac{Z_B(x,1)-Z_B(x,y)}{1-y}+Z_B(x,y)+\frac{P_B(x)-P_B(y)}{x-y}+\frac{1}{1-y}\left(\frac{F_B(x)-F_B(1)}{x-1}-\frac{F_B(x)-F_B(y)}{x-y}\right)\right]. \tag*{(16)} Z B ( x , y ) = z x [ 1 − y Z B ( x , 1 ) − Z B ( x , y ) + Z B ( x , y ) + x − y P B ( x ) − P B ( y ) + 1 − y 1 ( x − 1 F B ( x ) − F B ( 1 ) − x − y F B ( x ) − F B ( y ) ) ] . (16) For X = C X=C X = C , it is
P C ( x ) = z x + z x P C ( x ) + z x F C ( x ) − F C ( 1 ) x − 1 , (17) P_C(x)=zx+zxP_C(x)+zx\frac{F_C(x)-F_C(1)}{x-1}, \tag*{(17)} P C ( x ) = z x + z x P C ( x ) + z x x − 1 F C ( x ) − F C ( 1 ) , (17) F C ( x ) = P C ( x ) + z x Z C ( x , 1 ) , (18) F_C(x)=P_C(x)+zxZ_C(x,1), \tag*{(18)} F C ( x ) = P C ( x ) + z x Z C ( x , 1 ) , (18) Z C ( x , y ) = z x [ Z C ( x , 1 ) − Z C ( x , y ) 1 − y + Z C ( x , y ) − Z C ( y , y ) x − y + P C ( x ) − P C ( y ) x − y + 1 1 − y ( F C ( x ) − F C ( 1 ) x − 1 − F C ( x ) − F C ( y ) x − y ) ] . (19) Z_C(x,y)=zx\left[\frac{Z_C(x,1)-Z_C(x,y)}{1-y}+\frac{Z_C(x,y)-Z_C(y,y)}{x-y}+\frac{P_C(x)-P_C(y)}{x-y}+\frac{1}{1-y}\left(\frac{F_C(x)-F_C(1)}{x-1}-\frac{F_C(x)-F_C(y)}{x-y}\right)\right]. \tag*{(19)} Z C ( x , y ) = z x [ 1 − y Z C ( x , 1 ) − Z C ( x , y ) + x − y Z C ( x , y ) − Z C ( y , y ) + x − y P C ( x ) − P C ( y ) + 1 − y 1 ( x − 1 F C ( x ) − F C ( 1 ) − x − y F C ( x ) − F C ( y ) ) ] . (19) All constant terms in z z z are zero. The root conditions are
[ z ] P X ( x ) = [ z ] F X ( x ) = x , [ z ] Z X ( x , y ) = 0 , [ z ] H X ( x , y ) = x . [z]P_X(x)=[z]F_X(x)=x,\qquad[z]Z_X(x,y)=0,\qquad[z]H_X(x,y)=x. [ z ] P X ( x ) = [ z ] F X ( x ) = x , [ z ] Z X ( x , y ) = 0 , [ z ] H X ( x , y ) = x . Each system has a unique solution in the coefficient rings stated above, and G X ( z ) = 1 + F X ( 1 ) G_X(z)=1+F_X(1) G X ( z ) = 1 + F X ( 1 ) .
Proof. For either class, a new maximum is admissible and contributes J X ( x ) = z x ( F X ( x ) − F X ( 1 ) ) / ( x − 1 ) J_X(x)=zx(F_X(x)-F_X(1))/(x-1) J X ( x ) = z x ( F X ( x ) − F X ( 1 )) / ( x − 1 ) . Repetition of an admissible maximum leaves a single seen site and contributes z x P X ( x ) zxP_X(x) z x P X ( x ) . A lower choice makes the old maximum inadmissible: it creates a descent ending below that maximum and 101 forbids repeating it. Including the root proves (14) and (17) . Every admissible site gives a child of slack s + 1 s+1 s + 1 , and every new maximum is already counted in J X ( x ) J_X(x) J X ( x ) , so
F X ( x ) = z x + z x H X ( x , 1 ) + J X ( x ) . F_X(x)=zx+zxH_X(x,1)+J_X(x). F X ( x ) = z x + z x H X ( x , 1 ) + J X ( x ) .
Subtracting the equation for P X ( x ) P_X(x) P X ( x ) proves (15) and (18) .
For C C C , use the proved equation (11) and substitute H C ( x , y ) = P C ( x ) + Z C ( x , y ) H_C(x,y)=P_C(x)+Z_C(x,y) H C ( x , y ) = P C ( x ) + Z C ( x , y ) . Its old-site new-maximum term becomes
z x ( P C ( x ) − P C ( y ) ) x − y + z x ( Z C ( x , y ) − Z C ( y , y ) ) x − y . \frac{zx(P_C(x)-P_C(y))}{x-y}+\frac{zx(Z_C(x,y)-Z_C(y,y))}{x-y}. x − y z x ( P C ( x ) − P C ( y )) + x − y z x ( Z C ( x , y ) − Z C ( y , y )) .
The lower-site difference loses its P C ( x ) P_C(x) P C ( x ) terms. Subtracting (17) leaves the independent source
z x 1 − y ( F C ( x ) − F C ( 1 ) x − 1 − F C ( x ) − F C ( y ) x − y ) , \frac{zx}{1-y}\left(\frac{F_C(x)-F_C(1)}{x-1}-\frac{F_C(x)-F_C(y)}{x-y}\right), 1 − y z x ( x − 1 F C ( x ) − F C ( 1 ) − x − y F C ( x ) − F C ( y ) ) ,
which proves (19) .
For B B B , the legal interval is [ L , n ] ∖ D ( w ) [L,n]\setminus D(w) [ L , n ] ∖ D ( w ) , as proved above. A lower choice a a a leaves one seen site at a a a and the k ( a ) k(a) k ( a ) unused sites to its right; the old maximum is forbidden. Its site polynomial is therefore ( 1 − y k ( a ) + 1 ) / ( 1 − y ) (1-y^{k(a)+1})/(1-y) ( 1 − y k ( a ) + 1 ) / ( 1 − y ) . Repetition of M M M leaves one site, the same expression for k ( M ) = 0 k(M)=0 k ( M ) = 0 . A new maximum M + j M+j M + j discards every old site below M M M : the old maximum becomes the second largest entry. The old maximum itself remains admissible exactly when h = 1 h=1 h = 1 . Consequently the child’s polynomial is
h y j − 1 + 1 − y j − 1 1 − y + 1. hy^{j-1}+\frac{1-y^{j-1}}{1-y}+1. h y j − 1 + 1 − y 1 − y j − 1 + 1.
The finite sums (12) now give the full equation
H B ( x , y ) = z x + z x 1 − y ( H B ( x , 1 ) − y H B ( x , y ) ) + z x ( P B ( x ) − P B ( y ) ) x − y + 2 − y 1 − y J B ( x ) − z x ( F B ( x ) − F B ( y ) ) ( 1 − y ) ( x − y ) . (20) H_B(x,y)=zx+\frac{zx}{1-y}\bigl(H_B(x,1)-yH_B(x,y)\bigr)+\frac{zx(P_B(x)-P_B(y))}{x-y}
+\frac{2-y}{1-y}J_B(x)-\frac{zx(F_B(x)-F_B(y))}{(1-y)(x-y)}. \tag*{(20)} H B ( x , y ) = z x + 1 − y z x ( H B ( x , 1 ) − y H B ( x , y ) ) + x − y z x ( P B ( x ) − P B ( y )) + 1 − y 2 − y J B ( x ) − ( 1 − y ) ( x − y ) z x ( F B ( x ) − F B ( y )) . (20)
Inserting H B ( x , y ) = P B ( x ) + Z B ( x , y ) H_B(x,y)=P_B(x)+Z_B(x,y) H B ( x , y ) = P B ( x ) + Z B ( x , y ) and subtracting (14) , the site term left is
Z B ( x , 1 ) − y Z B ( x , y ) 1 − y = Z B ( x , 1 ) − Z B ( x , y ) 1 − y + Z B ( x , y ) . \frac{Z_B(x,1)-yZ_B(x,y)}{1-y}=\frac{Z_B(x,1)-Z_B(x,y)}{1-y}+Z_B(x,y). 1 − y Z B ( x , 1 ) − y Z B ( x , y ) = 1 − y Z B ( x , 1 ) − Z B ( x , y ) + Z B ( x , y ) .
The independent source is the same fraction involving F B F_B F B as in (16) . This proves that equation too.
For completeness, the last fraction in either system is polynomial: for f ( x ) = x a f(x)=x^a f ( x ) = x a with a ≥ 2 a\ge2 a ≥ 2 it is
1 1 − y ( x a − 1 x − 1 − x a − y a x − y ) = ∑ i , j ≥ 0 i + j ≤ a − 2 x i y j , \frac{1}{1-y}\left(\frac{x^a-1}{x-1}-\frac{x^a-y^a}{x-y}\right)=\sum_{\substack{i,j\ge0\\i+j\le a-2}}x^iy^j, 1 − y 1 ( x − 1 x a − 1 − x − y x a − y a ) = i , j ≥ 0 i + j ≤ a − 2 ∑ x i y j ,
and it is zero for a = 0 , 1 a=0,1 a = 0 , 1 . The other divided differences are also polynomial finite sums. Starting with the constant terms zero, compute the coefficient of P X ( x ) P_X(x) P X ( x ) and Z X ( x , y ) Z_X(x,y) Z X ( x , y ) at length n n n from length n − 1 n-1 n − 1 , then obtain that of F X ( x ) F_X(x) F X ( x ) from its displayed equation. This proves uniqueness and the root conditions. The definition of F X ( x ) F_X(x) F X ( x ) proves G X ( z ) = 1 + F X ( 1 ) G_X(z)=1+F_X(1) G X ( z ) = 1 + F X ( 1 ) .
The identity proved below concerns the specialization x = 1 x=1 x = 1 .
Kernel solution for 207(3)
The elimination below uses catalytic variables and iterated kernel roots, as in the generating-tree applications of the kernel method surveyed and developed by Bousquet-Mélou [5 ] . We give the specialized elimination for the present succession rule explicitly.
Write b B = F B ( 1 ) b_B=F_B(1) b B = F B ( 1 ) , β B = b B + ( z − 1 ) / z \beta_B=b_B+(z-1)/z β B = b B + ( z − 1 ) / z , and put
ϕ ( x ) = 1 1 − z x , D ( x ) = z x 2 − x + 1 , A ( x ) = D ( x ) + z x , M ( x ) = z x + z − 1. \phi(x)=\frac{1}{1-zx},\qquad D(x)=zx^2-x+1,\qquad A(x)=D(x)+zx,\qquad M(x)=zx+z-1. ϕ ( x ) = 1 − z x 1 , D ( x ) = z x 2 − x + 1 , A ( x ) = D ( x ) + z x , M ( x ) = z x + z − 1.
Here D D D , A A A , M M M are auxiliary polynomials, distinct from the forbidden set D ( w ) D(w) D ( w ) in the generating tree. Clearing denominators in (14c) gives
( 1 − y + z x y ) Z B ( x , y ) = z x Z B ( x , 1 ) + z x ( 1 − y ) P B ( x ) − P B ( y ) x − y + z x ( F B ( x ) − b B x − 1 − F B ( x ) − F B ( y ) x − y ) . (21) (1-y+zxy)Z_B(x,y)=zxZ_B(x,1)+zx(1-y)\frac{P_B(x)-P_B(y)}{x-y}+zx\left(\frac{F_B(x)-b_B}{x-1}-\frac{F_B(x)-F_B(y)}{x-y}\right). \tag*{(21)} ( 1 − y + z x y ) Z B ( x , y ) = z x Z B ( x , 1 ) + z x ( 1 − y ) x − y P B ( x ) − P B ( y ) + z x ( x − 1 F B ( x ) − b B − x − y F B ( x ) − F B ( y ) ) . (21)
The kernel vanishes at y = ϕ ( x ) y=\phi(x) y = ϕ ( x ) ; this substitution is valid coefficientwise because the catalytic coefficients are polynomials. Solving (14a) first gives
P X ( x ) = z x 1 − z x ( 1 + F X ( x ) − F X ( 1 ) x − 1 ) , X = B , C . (22) P_X(x)=\frac{zx}{1-zx}\left(1+\frac{F_X(x)-F_X(1)}{x-1}\right),\qquad X=B,C. \tag*{(22)} P X ( x ) = 1 − z x z x ( 1 + x − 1 F X ( x ) − F X ( 1 ) ) , X = B , C . (22)
With Y = ϕ ( x ) Y=\phi(x) Y = ϕ ( x ) , the vanishing-kernel condition, multiplied by x − Y x-Y x − Y , is
0 = ( x − Y ) F B ( x ) − P B ( x ) z x + ( 1 − Y ) ( P B ( x ) − P B ( Y ) ) + ( x − Y ) F B ( x ) − b B x − 1 − F B ( x ) + F B ( Y ) . 0=(x-Y)\frac{F_B(x)-P_B(x)}{zx}+(1-Y)(P_B(x)-P_B(Y))+(x-Y)\frac{F_B(x)-b_B}{x-1}-F_B(x)+F_B(Y). 0 = ( x − Y ) z x F B ( x ) − P B ( x ) + ( 1 − Y ) ( P B ( x ) − P B ( Y )) + ( x − Y ) x − 1 F B ( x ) − b B − F B ( x ) + F B ( Y ) .
Inserting (18) and Y = 1 / ( 1 − z x ) Y=1/(1-zx) Y = 1/ ( 1 − z x ) and clearing rational denominators yields the scalar equation
M ( x ) A ( x ) F B ( x ) + z x ( 1 − z x ) 2 F B ( ϕ ( x ) ) = x z 2 D ( x ) β B . (23) M(x)A(x)F_B(x)+zx(1-zx)^2F_B(\phi(x))=xz^2D(x)\beta_B. \tag*{(23)} M ( x ) A ( x ) F B ( x ) + z x ( 1 − z x ) 2 F B ( ϕ ( x )) = x z 2 D ( x ) β B . (23)
These operations are identities over Q ( z , x ) \mathbb{Q}(z,x) Q ( z , x ) with the three series values F B ( x ) F_B(x) F B ( x ) , F B ( Y ) F_B(Y) F B ( Y ) , b B b_B b B treated as independent symbols. More explicitly, after the substitutions the right-hand side of the vanishing-kernel display is − 1 / ( z x ( 1 − z x ) M ( x ) ) -1/(zx(1-zx)M(x)) − 1/ ( z x ( 1 − z x ) M ( x )) times the difference between the left and right sides of (19). This verifies all factors and signs in the reduction.
Define
λ = 1 − 1 − 4 z 2 z , α = 1 − z − 1 − 6 z + z 2 2 z , ρ = ϕ ( α ) , \lambda=\frac{1-\sqrt{1-4z}}{2z},\qquad\alpha=\frac{1-z-\sqrt{1-6z+z^2}}{2z},\qquad\rho=\phi(\alpha), λ = 2 z 1 − 1 − 4 z , α = 2 z 1 − z − 1 − 6 z + z 2 , ρ = ϕ ( α ) ,
where the square roots have constant term 1. Then D ( λ ) = 0 D(\lambda)=0 D ( λ ) = 0 , A ( α ) = 0 A(\alpha)=0 A ( α ) = 0 , and both λ \lambda λ and α \alpha α have constant term 1. For the rational functions
f ( x ) = x z 2 D ( x ) M ( x ) A ( x ) , g ( x ) = − z x ( 1 − z x ) 2 M ( x ) A ( x ) , f(x)=\frac{xz^2D(x)}{M(x)A(x)},\qquad g(x)=-\frac{zx(1-zx)^2}{M(x)A(x)}, f ( x ) = M ( x ) A ( x ) x z 2 D ( x ) , g ( x ) = − M ( x ) A ( x ) z x ( 1 − z x ) 2 ,
put a i = ϕ i ( a ) a_i=\phi^i(a) a i = ϕ i ( a ) and define
Π ( a ) = ∏ i ≥ 0 g ( a i ) , S ( a ) = ∑ i ≥ 0 f ( a i ) ∏ 0 ≤ j < i g ( a j ) . (24) \Pi(a)=\prod_{i\geq0}g(a_i),\qquad\mathcal{S}(a)=\sum_{i\geq0}f(a_i)\prod_{0\leq j<i}g(a_j). \tag*{(24)} Π ( a ) = i ≥ 0 ∏ g ( a i ) , S ( a ) = i ≥ 0 ∑ f ( a i ) 0 ≤ j < i ∏ g ( a j ) . (24)
The empty product is 1. Below these are coefficientwise products and sums, for a = 1 a=1 a = 1 , a = ρ a=\rho a = ρ , or an indeterminate a = x a=x a = x .
Proposition 3. Set
τ = − z 2 α ρ 2 , Q = S ( 1 ) + Π ( 1 ) Π ( ρ ) ( τ − S ( ρ ) ) . \tau=-z^2\alpha\rho^2,\qquad\mathcal{Q}=\mathcal{S}(1)+\frac{\Pi(1)}{\Pi(\rho)}\bigl(\tau-\mathcal{S}(\rho)\bigr). τ = − z 2 α ρ 2 , Q = S ( 1 ) + Π ( ρ ) Π ( 1 ) ( τ − S ( ρ ) ) . The orbit expressions are well-defined formal series, Q = − z 2 + O ( z 3 ) \mathcal{Q}=-z^2+O(z^3) Q = − z 2 + O ( z 3 ) , and
G B ( z ) = 1 + ( 1 − z ) Q z ( Q − 1 ) . (25) G_B(z)=1+\frac{(1-z)\mathcal{Q}}{z(\mathcal{Q}-1)}. \tag*{(25)} G B ( z ) = 1 + z ( Q − 1 ) ( 1 − z ) Q . (25) With b B = G B ( z ) − 1 b_B=G_B(z)-1 b B = G B ( z ) − 1 and β B = b B + ( z − 1 ) / z \beta_B=b_B+(z-1)/z β B = b B + ( z − 1 ) / z , the full slack series is
F B ( x ) = β B [ S ( x ) + Π ( x ) Π ( ρ ) ( τ − S ( ρ ) ) ] . (26) F_B(x)=\beta_B\left[\mathcal{S}(x)+\frac{\Pi(x)}{\Pi(\rho)}\bigl(\tau-\mathcal{S}(\rho)\bigr)\right]. \tag*{(26)} F B ( x ) = β B [ S ( x ) + Π ( ρ ) Π ( x ) ( τ − S ( ρ ) ) ] . (26) The series P B ( x ) P_B(x) P B ( x ) is given by (18). The remaining series is recovered explicitly as
Z B ( x , y ) = 1 1 − y + z x y [ F B ( x ) − P B ( x ) + z x ( 1 − y ) P B ( x ) − P B ( y ) x − y + z x ( F B ( x ) − b B x − 1 − F B ( x ) − F B ( y ) x − y ) ] , (27) Z_B(x,y)=\frac{1}{1-y+zxy}\left[F_B(x)-P_B(x)+zx(1-y)\frac{P_B(x)-P_B(y)}{x-y}+zx\left(\frac{F_B(x)-b_B}{x-1}-\frac{F_B(x)-F_B(y)}{x-y}\right)\right], \tag*{(27)} Z B ( x , y ) = 1 − y + z x y 1 [ F B ( x ) − P B ( x ) + z x ( 1 − y ) x − y P B ( x ) − P B ( y ) + z x ( x − 1 F B ( x ) − b B − x − y F B ( x ) − F B ( y ) ) ] , (27) and H B ( x , y ) = P B ( x ) + Z B ( x , y ) H_B(x,y)=P_B(x)+Z_B(x,y) H B ( x , y ) = P B ( x ) + Z B ( x , y ) .
Proof. The fixed point ϕ ( λ ) = λ \phi(\lambda)=\lambda ϕ ( λ ) = λ and the identity
ϕ ( u ) − λ = z ( u − λ ) ( 1 − z u ) ( 1 − z λ ) \phi(u)-\lambda=\frac{z(u-\lambda)}{(1-zu)(1-z\lambda)} ϕ ( u ) − λ = ( 1 − z u ) ( 1 − z λ ) z ( u − λ )
show that each orbit step raises the z z z -order of u − λ u-\lambda u − λ by one. The initial orders of 1 − λ 1-\lambda 1 − λ and ρ − λ \rho-\lambda ρ − λ are 1 and 2, respectively. Along either orbit M ( a i ) M(a_i) M ( a i ) is a unit and A ( a i ) A(a_i) A ( a i ) has order 1. Also g ( λ ) = 1 g(\lambda)=1 g ( λ ) = 1 and f ( λ ) = 0 f(\lambda)=0 f ( λ ) = 0 . To see the orders explicitly, factor
D ( u ) = ( u − λ ) ( z ( u + λ ) − 1 ) . D(u)=(u-\lambda)\bigl(z(u+\lambda)-1\bigr). D ( u ) = ( u − λ ) ( z ( u + λ ) − 1 ) .
Then the factor z 2 / A ( u ) z^2/A(u) z 2 / A ( u ) in f ( u ) f(u) f ( u ) raises the order by one. For g ( u ) − 1 g(u)-1 g ( u ) − 1 , its numerator is − z u ( 1 − z u ) 2 − M ( u ) A ( u ) -zu(1-zu)^2-M(u)A(u) − z u ( 1 − z u ) 2 − M ( u ) A ( u ) , which vanishes at u = λ u=\lambda u = λ ; division by A ( u ) A(u) A ( u ) can lower the order by at most one. Consequently, on the 1 orbit,
g ( a i ) − 1 = O ( z i ) ( i ≥ 1 ) , f ( a i ) = O ( z i + 2 ) , g(a_i)-1=O(z^i)\ (i\geq1),\qquad f(a_i)=O(z^{i+2}), g ( a i ) − 1 = O ( z i ) ( i ≥ 1 ) , f ( a i ) = O ( z i + 2 ) ,
and on the ρ \rho ρ orbit the respective orders are at least i + 1 i+1 i + 1 and i + 3 i+3 i + 3 . Direct expansion gives g ( 1 ) = 1 / 2 + O ( z ) g(1)=1/2+O(z) g ( 1 ) = 1/2 + O ( z ) and g ( ρ ) = 1 + O ( z ) g(\rho)=1+O(z) g ( ρ ) = 1 + O ( z ) . The products therefore converge and are units, with constant terms 1 / 2 1/2 1/2 and 1 1 1 , and the sums converge. For an indeterminate x x x , the first iterate has constant term 1 1 1 ; A ( ϕ ( x ) ) = z ( 2 − x ) + O ( z 2 ) A(\phi(x)) = z(2-x) + O(z^2) A ( ϕ ( x )) = z ( 2 − x ) + O ( z 2 ) is nonzero over Q ( x ) \mathbb{Q}(x) Q ( x ) . After the second iterate the same order estimates apply, proving convergence over Q ( x ) [ [ z ] ] \mathbb{Q}(x)[[z]] Q ( x ) [[ z ]] as well.
Equation (23) is
F B ( u ) = β B f ( u ) + g ( u ) F B ( ϕ ( u ) ) . F_B(u)=\beta_B f(u)+g(u)F_B(\phi(u)). F B ( u ) = β B f ( u ) + g ( u ) F B ( ϕ ( u )) .
After k k k iterations this is a finite sum plus ∏ i < k g ( a i ) F B ( a k ) \prod_{i<k}g(a_i)F_B(a_k) ∏ i < k g ( a i ) F B ( a k ) . Since each coefficient of F B ( u ) F_B(u) F B ( u ) is polynomial in u u u and a k ⟶ λ a_k\longrightarrow\lambda a k ⟶ λ , its coefficientwise limit is
F B ( a ) = β B S ( a ) + Π ( a ) F B ( λ ) . (28) F_B(a)=\beta_B\mathcal{S}(a)+\Pi(a)F_B(\lambda). \tag*{(28)} F B ( a ) = β B S ( a ) + Π ( a ) F B ( λ ) . (28)
At u = α u=\alpha u = α , the scalar equation is valid before dividing by A ( u ) A(u) A ( u ) . As D ( α ) = − z α D(\alpha)=-z\alpha D ( α ) = − z α , it gives
F B ( ρ ) = − z 2 α ( 1 − z α ) 2 β B = τ β B . F_B(\rho)=-\frac{z^2\alpha}{(1-z\alpha)^2}\beta_B=\tau\beta_B. F B ( ρ ) = − ( 1 − z α ) 2 z 2 α β B = τ β B .
Use (28) at a = ρ a=\rho a = ρ to eliminate F B ( λ ) F_B(\lambda) F B ( λ ) . At a = 1 a=1 a = 1 the result is b B = β B Q b_B=\beta_B\mathcal{Q} b B = β B Q . Solving this linear equation using β B = b B − ( 1 − z ) / z \beta_B=b_B-(1-z)/z β B = b B − ( 1 − z ) / z proves (25) ; using a = x a=x a = x proves (26) . The first terms are S ( 1 ) = − z 2 / 2 + O ( z 3 ) \mathcal{S}(1)=-z^2/2+O(z^3) S ( 1 ) = − z 2 /2 + O ( z 3 ) , S ( ρ ) = O ( z 3 ) \mathcal{S}(\rho)=O(z^3) S ( ρ ) = O ( z 3 ) and τ = − z 2 + O ( z 3 ) \tau=-z^2+O(z^3) τ = − z 2 + O ( z 3 ) , so Q = − z 2 + O ( z 3 ) \mathcal{Q}=-z^2+O(z^3) Q = − z 2 + O ( z 3 ) and Q − 1 \mathcal{Q}-1 Q − 1 is a unit. Finally (22) and (21) prove (27) . Its apparent catalytic denominators are interpreted after cancellation; the recovered coefficients are the polynomials of the unique solution to Proposition 2.
The kernel reduction for 207(2)
Clearing denominators in (15c) gives
κ ( x , y ) Z C ( x , y ) = z x [ ( x − y ) Z C ( x , 1 ) − ( 1 − y ) Z C ( y , y ) + ( 1 − y ) ( P C ( x ) − P C ( y ) ) + ( x − y ) F C ( x ) − F C ( 1 ) x − 1 − F C ( x ) + F C ( y ) ] . (29) \kappa(x,y)Z_C(x,y)=zx\left[(x-y)Z_C(x,1)-(1-y)Z_C(y,y)+(1-y)(P_C(x)-P_C(y))+(x-y)\frac{F_C(x)-F_C(1)}{x-1}-F_C(x)+F_C(y)\right]. \tag*{(29)} κ ( x , y ) Z C ( x , y ) = z x [ ( x − y ) Z C ( x , 1 ) − ( 1 − y ) Z C ( y , y ) + ( 1 − y ) ( P C ( x ) − P C ( y )) + ( x − y ) x − 1 F C ( x ) − F C ( 1 ) − F C ( x ) + F C ( y ) ] . (29)
κ ( x , y ) = ( 1 − y ) ( x − y ) + z x ( x − 1 ) . \kappa(x,y)=(1-y)(x-y)+zx(x-1). κ ( x , y ) = ( 1 − y ) ( x − y ) + z x ( x − 1 ) .
Let b C = F C ( 1 ) b_C=F_C(1) b C = F C ( 1 ) and β C = b C + ( z − 1 ) / z \beta_C=b_C+(z-1)/z β C = b C + ( z − 1 ) / z . Define
W C ( x ) = z x ( 1 − x ) 1 − z x F C ( x ) , R ( y ) = z ( 1 − y ) 2 ( 2 − y ) { 2 − y + z ( y 2 − y − 1 ) } . W_C(x)=\frac{zx(1-x)}{1-zx}F_C(x),\qquad R(y)=\frac{z(1-y)^2}{(2-y)\{2-y+z(y^2-y-1)\}}. W C ( x ) = 1 − z x z x ( 1 − x ) F C ( x ) , R ( y ) = ( 2 − y ) { 2 − y + z ( y 2 − y − 1 )} z ( 1 − y ) 2 .
The following gives a scalar reduction with both kernel roots kept inside legitimate formal compositions.
Proposition 4. For an indeterminate t t t , put
T ( t ) = t ( z t − t + 1 ) z t 2 − t + 1 , x 0 = T ( t ) , x 1 = − t − 1 z t 2 − t + 1 = T ( ϕ ( t ) ) , y 0 = T ( t ) / t . T(t)=\frac{t(zt-t+1)}{zt^2-t+1},\qquad x_0=T(t),\qquad x_1=-\frac{t-1}{zt^2-t+1}=T(\phi(t)),\qquad y_0=T(t)/t. T ( t ) = z t 2 − t + 1 t ( z t − t + 1 ) , x 0 = T ( t ) , x 1 = − z t 2 − t + 1 t − 1 = T ( ϕ ( t )) , y 0 = T ( t ) / t . Then x 0 , x 1 x_0,x_1 x 0 , x 1 are the two roots of κ ( x , y 0 ) = 0 \kappa(x,y_0)=0 κ ( x , y 0 ) = 0 and
W C ( x 0 ) − W C ( x 1 ) = β C ( x 0 − x 1 ) R ( y 0 ) . (30) W_C(x_0)-W_C(x_1)=\beta_C(x_0-x_1)R(y_0). \tag*{(30)} W C ( x 0 ) − W C ( x 1 ) = β C ( x 0 − x 1 ) R ( y 0 ) . (30)
Proof. Substitution into the quadratic verifies κ ( x i , y 0 ) = 0 \kappa(x_i,y_0)=0 κ ( x i , y 0 ) = 0 . The constant terms of x 0 , x 1 , y 0 x_0,x_1,y_0 x 0 , x 1 , y 0 are t , 1 , 1 t,1,1 t , 1 , 1 , respectively; thus compositions with the original prefix series are defined over Q ( t ) [ [ z ] ] \mathbb{Q}(t)[[z]] Q ( t ) [[ z ]] . Rational divisions below may be taken in its Laurent-series field. In (11), set κ ( x , y ) = 0 \kappa(x,y)=0 κ ( x , y ) = 0 and use (9), (10), and (18). The common diagonal boundary is
H C ( y , y ) − F C ( y ) 1 − y = a ( x , y ) F C ( x ) + q ( x , y ) b C + c ( x , y ) . (31) H_C(y,y)-\frac{F_C(y)}{1-y}=a(x,y)F_C(x)+q(x,y)b_C+c(x,y). \tag*{(31)} H C ( y , y ) − 1 − y F C ( y ) = a ( x , y ) F C ( x ) + q ( x , y ) b C + c ( x , y ) . (31)
where
a ( x , y ) = x − y ( x − 1 ) ( 1 − z x ) + x − y − z x z x ( 1 − y ) , q ( x , y ) = − x − y ( x − 1 ) ( 1 − z x ) , c ( x , y ) = x − y 1 − z x − x − y 1 − y . \begin{aligned}
a(x,y)&=\frac{x-y}{(x-1)(1-zx)}+\frac{x-y-zx}{zx(1-y)},\\
q(x,y)&=-\frac{x-y}{(x-1)(1-zx)},\qquad c(x,y)=\frac{x-y}{1-zx}-\frac{x-y}{1-y}.
\end{aligned} a ( x , y ) q ( x , y ) = ( x − 1 ) ( 1 − z x ) x − y + z x ( 1 − y ) x − y − z x , = − ( x − 1 ) ( 1 − z x ) x − y , c ( x , y ) = 1 − z x x − y − 1 − y x − y .
For an explicit derivation, the cleared equation for H C ( x , y ) H_C(x,y) H C ( x , y ) on the kernel is
H C ( y , y ) − F C ( y ) 1 − y = ( x − y ) ( 1 + P C ( x ) ) + x − y 1 − y H C ( x , 1 ) + ( 2 − y ) ( x − y ) z x ( 1 − y ) J C ( x ) − F C ( x ) 1 − y . \begin{aligned}
H_C(y,y)-\frac{F_C(y)}{1-y}
&=(x-y)(1+P_C(x))+\frac{x-y}{1-y}H_C(x,1)\\
&+\frac{(2-y)(x-y)}{zx(1-y)}J_C(x)-\frac{F_C(x)}{1-y}.
\end{aligned} H C ( y , y ) − 1 − y F C ( y ) = ( x − y ) ( 1 + P C ( x )) + 1 − y x − y H C ( x , 1 ) + z x ( 1 − y ) ( 2 − y ) ( x − y ) J C ( x ) − 1 − y F C ( x ) .
Insert z x H C ( x , 1 ) = F C ( x ) − z x − J C ( x ) zxH_C(x,1)=F_C(x)-zx-J_C(x) z x H C ( x , 1 ) = F C ( x ) − z x − J C ( x ) and 1 + P C ( x ) = ( 1 + J C ( x ) ) / ( 1 − z x ) 1+P_C(x)=(1+J_C(x))/(1-zx) 1 + P C ( x ) = ( 1 + J C ( x )) / ( 1 − z x ) ; the displayed a , q , c a,q,c a , q , c result.
In the following root calculations set y = y 0 y=y_0 y = y 0 . On the kernel, ( x − y ) / ( x − 1 ) = − z x / ( 1 − y ) (x-y)/(x-1)=-zx/(1-y) ( x − y ) / ( x − 1 ) = − z x / ( 1 − y ) , which gives
a ( x , y ) 1 − z x z x ( 1 − x ) = − 2 − y ( 1 − y ) 3 . a(x,y)\frac{1-zx}{zx(1-x)}=-\frac{2-y}{(1-y)^3}. a ( x , y ) z x ( 1 − x ) 1 − z x = − ( 1 − y ) 3 2 − y .
The root sum and product of z x 2 + ( 1 − y − z ) x − y ( 1 − y ) zx^2+(1-y-z)x-y(1-y) z x 2 + ( 1 − y − z ) x − y ( 1 − y ) give
( 1 − z x 0 ) ( 1 − z x 1 ) = 2 − y + z ( y 2 − y − 1 ) . (1-zx_0)(1-zx_1)=2-y+z(y^2-y-1). ( 1 − z x 0 ) ( 1 − z x 1 ) = 2 − y + z ( y 2 − y − 1 ) .
Also, writing δ q = q ( x 0 , y ) − q ( x 1 , y ) \delta q=q(x_0,y)-q(x_1,y) δ q = q ( x 0 , y ) − q ( x 1 , y ) , the kernel relation gives
δ q = z ( x 0 − x 1 ) ( 1 − y ) ( 1 − z x 0 ) ( 1 − z x 1 ) , c ( x 0 , y ) − c ( x 1 , y ) = z − 1 z δ q . \delta q=\frac{z(x_0-x_1)}{(1-y)(1-zx_0)(1-zx_1)},\qquad c(x_0,y)-c(x_1,y)=\frac{z-1}{z}\delta q. δ q = ( 1 − y ) ( 1 − z x 0 ) ( 1 − z x 1 ) z ( x 0 − x 1 ) , c ( x 0 , y ) − c ( x 1 , y ) = z z − 1 δ q .
Subtract (27) for the two roots; its left sides are identical. The result is
2 − y ( 1 − y ) 3 ( W C ( x 0 ) − W C ( x 1 ) ) = β C δ q . \frac{2-y}{(1-y)^3}\bigl(W_C(x_0)-W_C(x_1)\bigr)=\beta_C\delta q. ( 1 − y ) 3 2 − y ( W C ( x 0 ) − W C ( x 1 ) ) = β C δ q .
The preceding product formula proves (30) at y = y 0 y=y_0 y = y 0 .
The C C C scalar equation has an additive forcing term, whereas the B B B scalar equation has the convergent product solution above. The formal-iteration warning and the coefficientwise fixed-maximum expansion are recorded in the supplementary material; the Lambert-series calculation below supplies the all-length boundary value used in the equality proof.
The Class 207 equality and its common generating function
The C kernel equation gives a Lambert series quotient, whereas the published B tree gives a difference of two product orbit sums. We evaluate that difference by a cubic limit of the nonterminating q q q -Saalschütz summation. Together with the A–C bijection of Callan–Mansour [8 Section 4.10] , this proves the Class 207 case of their Conjecture 1.
Let q = λ − 1 q=\lambda-1 q = λ − 1 , where λ = ( 1 − 1 − 4 z ) / ( 2 z ) \lambda=(1-\sqrt{1-4z})/(2z) λ = ( 1 − 1 − 4 z ) / ( 2 z ) is the Catalan series, so z = q / ( 1 + q ) 2 z=q/(1+q)^2 z = q / ( 1 + q ) 2 , and set
L = 1 − 2 q − 2 q 2 + q 3 , q + L r + q 2 r 2 = 0 , r = − q + O ( q 2 ) . L=1-2q-2q^2+q^3,\qquad q+Lr+q^2r^2=0,\qquad r=-q+O(q^2). L = 1 − 2 q − 2 q 2 + q 3 , q + L r + q 2 r 2 = 0 , r = − q + O ( q 2 ) .
This specifies r ∈ q Q [ [ q ] ] r\in q\mathbb{Q}[[q]] r ∈ q Q [[ q ]] uniquely; explicitly, r = − 2 q / ( L + L 2 − 4 q 3 ) r=-2q/(L+\sqrt{L^2-4q^3}) r = − 2 q / ( L + L 2 − 4 q 3 ) , with square root 1 + O ( q ) 1+O(q) 1 + O ( q ) . Define
T ( q , r ) = ∑ k ≥ 1 k 2 ( q r ) k 1 − q k , θ = ( 1 − q ) 3 ( 1 + q ) q 2 , H = 1 + θ T ( q , r ( q ) ) . (32) T(q,r)=\sum_{k\geq1}\frac{k^2(qr)^k}{1-q^k},\qquad\theta=\frac{(1-q)^3(1+q)}{q^2},\qquad H=1+\theta T(q,r(q)). \tag*{(32)} T ( q , r ) = k ≥ 1 ∑ 1 − q k k 2 ( q r ) k , θ = q 2 ( 1 − q ) 3 ( 1 + q ) , H = 1 + θ T ( q , r ( q )) . (32)
Theorem 1. For all n ≥ 0 n\geq0 n ≥ 0 , the three classes A A A , B B B , C C C have the same number of inversion sequences of length n n n . Their common generating function satisfies
G A ( q ( 1 + q ) 2 ) = G B ( q ( 1 + q ) 2 ) = G C ( q ( 1 + q ) 2 ) = ( 1 + q ) 2 q + 1 H . (33) G_A\left(\frac{q}{(1+q)^2}\right)=G_B\left(\frac{q}{(1+q)^2}\right)=G_C\left(\frac{q}{(1+q)^2}\right)=\frac{(1+q)^2}{q}+\frac{1}{H}. \tag*{(33)} G A ( ( 1 + q ) 2 q ) = G B ( ( 1 + q ) 2 q ) = G C ( ( 1 + q ) 2 q ) = q ( 1 + q ) 2 + H 1 . (33)
Here H = − q + O ( q 2 ) H=-q+O(q^2) H = − q + O ( q 2 ) ; the two Laurent expressions on the right have canceling negative powers and their sum belongs to Q [ [ q ] ] \mathbb{Q}[[q]] Q [[ q ]] .
The proof first obtains the two counting formulas and then evaluates the orbit difference that connects them. The summation used in the last step is classical [12 Eq. (II.24)] ; see also [21 Eq. 17.7.5] . We give the specialization and cubic limit explicitly.
The C boundary and its Lambert series
Use the C statistics of § 2 and, in this subsection, write P = P C P=P_C P = P C , F = F C F=F_C F = F C and Z = Z C Z=Z_C Z = Z C . In particular, G C = 1 + F ( 1 ) G_C=1+F(1) G C = 1 + F ( 1 ) and deg x [ z n ] P ≤ n \deg_x[z^n]P\leq n deg x [ z n ] P ≤ n , since the slack is at most the prefix length. Equations (15a)–(15c) provide the complete system used below.
Write κ ( x , y ) = ( 1 − y ) ( x − y ) + z x ( x − 1 ) \kappa(x,y)=(1-y)(x-y)+zx(x-1) κ ( x , y ) = ( 1 − y ) ( x − y ) + z x ( x − 1 ) . At a kernel root, clearing (15c) and substituting (15a)–(15b) gives
( 1 − y ) 2 ( Z ( y , y ) + P ( y ) z y ) = ( 1 − x ) ( G C − x ) + ( 2 − y ) ( 1 − x ) 2 1 − y P ( x ) . (34) (1-y)^2\left(Z(y,y)+\frac{P(y)}{zy}\right)=(1-x)(G_C-x)+\frac{(2-y)(1-x)^2}{1-y}P(x). \tag*{(34)} ( 1 − y ) 2 ( Z ( y , y ) + z y P ( y ) ) = ( 1 − x ) ( G C − x ) + 1 − y ( 2 − y ) ( 1 − x ) 2 P ( x ) . (34)
For two roots x , x ′ x,x' x , x ′ , subtraction and x + x ′ = 1 + ( y − 1 ) / z x+x'=1+(y-1)/z x + x ′ = 1 + ( y − 1 ) / z give
( 2 − y ) ( ( 1 − x ) 2 P ( x ) − ( 1 − x ′ ) 2 P ( x ′ ) ) = ( 1 − y ) ( x − x ′ ) ( G C + 1 − y z ) . (35) (2-y)\left((1-x)^2P(x)-(1-x')^2P(x')\right)=(1-y)(x-x')\left(G_C+\frac{1-y}{z}\right). \tag*{(35)} ( 2 − y ) ( ( 1 − x ) 2 P ( x ) − ( 1 − x ′ ) 2 P ( x ′ ) ) = ( 1 − y ) ( x − x ′ ) ( G C + z 1 − y ) . (35)
In particular, for an indeterminate t t t , put
d = t 2 − t + z , X = t ( t − 1 ) d , X ′ = z − t d , Y = ( t − 1 ) ( t − z ) d . d=t^2-t+z,\qquad X=\frac{t(t-1)}{d},\qquad X'=\frac{z-t}{d},\qquad Y=\frac{(t-1)(t-z)}{d}. d = t 2 − t + z , X = d t ( t − 1 ) , X ′ = d z − t , Y = d ( t − 1 ) ( t − z ) .
They satisfy κ ( X , Y ) = κ ( X ′ , Y ) = 0 \kappa(X,Y)=\kappa(X',Y)=0 κ ( X , Y ) = κ ( X ′ , Y ) = 0 and have nonnegative z z z -orders. Substitution in (31) gives
( d + t z ) ( z 2 P ( X ) − t 4 P ( X ′ ) ) = z t ( t 2 − z ) ( d G C + t ) . (36) (d+tz)\left(z^2P(X)-t^4P(X')\right)=zt(t^2-z)(dG_C+t). \tag*{(36)} ( d + t z ) ( z 2 P ( X ) − t 4 P ( X ′ ) ) = z t ( t 2 − z ) ( d G C + t ) . (36)
All substitutions so far are coefficientwise legitimate over Q ( t ) [ [ z ] ] \mathbb{Q}(t)[[z]] Q ( t ) [[ z ]] .
Put D ( u ) = q u 2 + L u + q 2 D(u)=qu^2+Lu+q^2 D ( u ) = q u 2 + Lu + q 2 and define
j G ( u ) = ( u − 1 ) ( u − q ) ( u 2 − q ) ( 1 − q ) 2 u D ( u ) , j 0 ( u ) = ( u − 1 ) 2 ( u − q ) 2 ( u 2 − q ) ( 1 + q ) u 2 D ( u ) , j_G(u)=\frac{(u-1)(u-q)(u^2-q)(1-q)^2}{uD(u)},\qquad
j_0(u)=\frac{(u-1)^2(u-q)^2(u^2-q)(1+q)}{u^2D(u)}, j G ( u ) = u D ( u ) ( u − 1 ) ( u − q ) ( u 2 − q ) ( 1 − q ) 2 , j 0 ( u ) = u 2 D ( u ) ( u − 1 ) 2 ( u − q ) 2 ( u 2 − q ) ( 1 + q ) ,
L ( j ) = ∑ k ≥ 1 k 2 q k 1 − q k [ u k ] j ( u ) , Λ G = L ( j G ) , Λ 0 = L ( j 0 ) . \mathcal{L}(j)=\sum_{k\geq1}\frac{k^2q^k}{1-q^k}[u^k]j(u),\qquad
\Lambda_G=\mathcal{L}(j_G),\qquad
\Lambda_0=\mathcal{L}(j_0). L ( j ) = k ≥ 1 ∑ 1 − q k k 2 q k [ u k ] j ( u ) , Λ G = L ( j G ) , Λ 0 = L ( j 0 ) .
Laurent expansions here are q q q -first: expand in q q q with Laurent-polynomial coefficients in u u u , and then extract [ u k ] [u^k] [ u k ] . Take
t = u − q ( 1 + q ) ( u − 1 ) , d = ( 1 − q ) 2 u ( 1 + q ) 2 ( u − 1 ) 2 , X = 1 − q ( 1 − q ) 2 ( u + u − 1 − 2 ) , Q ( u ) = P ( X ) d 2 . t=\frac{u-q}{(1+q)(u-1)},\qquad
d=\frac{(1-q)^2u}{(1+q)^2(u-1)^2},\qquad
X=1-\frac{q}{(1-q)^2}(u+u^{-1}-2),\qquad
Q(u)=\frac{P(X)}{d^2}. t = ( 1 + q ) ( u − 1 ) u − q , d = ( 1 + q ) 2 ( u − 1 ) 2 ( 1 − q ) 2 u , X = 1 − ( 1 − q ) 2 q ( u + u − 1 − 2 ) , Q ( u ) = d 2 P ( X ) .
(36) becomes, with G ~ C = G C ( q / ( 1 + q ) 2 ) \widetilde{G}_C=G_C(q/(1+q)^2) G C = G C ( q / ( 1 + q ) 2 ) and G ~ B = G B ( q / ( 1 + q ) 2 ) \widetilde{G}_B=G_B(q/(1+q)^2) G B = G B ( q / ( 1 + q ) 2 ) ,
Q ( u ) − Q ( q / u ) = ( 1 + q ) 4 q ( 1 − q ) 3 ( j G ( u ) G ~ C + j 0 ( u ) ) . (37) Q(u)-Q(q/u)=\frac{(1+q)^4}{q(1-q)^3}\bigl(j_G(u)\widetilde{G}_C+j_0(u)\bigr). \tag*{(37)} Q ( u ) − Q ( q / u ) = q ( 1 − q ) 3 ( 1 + q ) 4 ( j G ( u ) G C + j 0 ( u ) ) . (37)
The substitution deserves an order check. Writing w = u + u − 1 − 2 w=u+u^{-1}-2 w = u + u − 1 − 2 , Q Q Q is a unit in Q [ [ q ] ] \mathbb{Q}[[q]] Q [[ q ]] times w 2 P ( z , 1 − q w / ( 1 − q ) 2 ) w^2P(z,1-qw/(1-q)^2) w 2 P ( z , 1 − q w / ( 1 − q ) 2 ) . Since deg x [ z n ] P ≤ n \deg_x[z^n]P\leq n deg x [ z n ] P ≤ n , a term w j + 2 w^{j+2} w j + 2 from P P P has q q q -order at least 2 j 2j 2 j . Consequently, if Q k = [ u k ] Q Q_k=[u^k]Q Q k = [ u k ] Q , then ord q Q k ≥ 2 ∣ k ∣ − 4 \operatorname{ord}_q Q_k\geq2|k|-4 ord q Q k ≥ 2∣ k ∣ − 4 for ∣ k ∣ ≥ 3 |k|\geq3 ∣ k ∣ ≥ 3 . This proves that Q ( q / u ) Q(q/u) Q ( q / u ) and the coefficient sums below are well defined in the q q q -adic Laurent field. Also Q ( u ) = Q ( 1 / u ) Q(u)=Q(1/u) Q ( u ) = Q ( 1/ u ) and Q ′ ′ ( 1 ) = 0 Q''(1)=0 Q ′′ ( 1 ) = 0 , since d − 2 d^{-2} d − 2 supplies a fourth-order zero at u = 1 u=1 u = 1 . Taking positive coefficients in (33) gives
Q k = − ( 1 + q ) 4 q ( 1 − q ) 3 q k 1 − q k [ u k ] ( j G G ~ C + j 0 ) . Q_k=-\frac{(1+q)^4}{q(1-q)^3}\frac{q^k}{1-q^k}[u^k]\bigl(j_G\widetilde{G}_C+j_0\bigr). Q k = − q ( 1 − q ) 3 ( 1 + q ) 4 1 − q k q k [ u k ] ( j G G C + j 0 ) .
Thus 0 = Q ′ ′ ( 1 ) = 2 ∑ k > 0 k 2 Q k 0=Q''(1)=2\sum_{k>0}k^2Q_k 0 = Q ′′ ( 1 ) = 2 ∑ k > 0 k 2 Q k implies
G ~ C = − Λ 0 Λ G . (38) \widetilde{G}_C=-\frac{\Lambda_0}{\Lambda_G}. \tag*{(38)} G C = − Λ G Λ 0 . (38)
To evaluate it, use the two rational identities
j 0 + ( 1 + q ) 2 q j G = 1 + q q ( u − 1 ) ( u − q ) ( u 2 − q ) u 2 . (39) j_0+\frac{(1+q)^2}{q}j_G
=\frac{1+q}{q}\frac{(u-1)(u-q)(u^2-q)}{u^2}. \tag*{(39)} j 0 + q ( 1 + q ) 2 j G = q 1 + q u 2 ( u − 1 ) ( u − q ) ( u 2 − q ) . (39)
j G = ( 1 − q ) 2 q ( u − q u ) + ( 1 − q ) 4 ( 1 + q ) q 2 ( 1 1 − r u − 1 1 − q r / u ) . (40) j_G=\frac{(1-q)^2}{q}\left(u-\frac{q}{u}\right)
+\frac{(1-q)^4(1+q)}{q^2}\left(\frac{1}{1-ru}-\frac{1}{1-qr/u}\right). \tag*{(40)} j G = q ( 1 − q ) 2 ( u − u q ) + q 2 ( 1 − q ) 4 ( 1 + q ) ( 1 − r u 1 − 1 − q r / u 1 ) . (40)
The second follows by D ( u ) = − ( q / r ) ( 1 − r u ) ( u − q r ) D(u)=-(q/r)(1-ru)(u-qr) D ( u ) = − ( q / r ) ( 1 − r u ) ( u − q r ) and the quadratic equation for r r r . Applying L \mathcal{L} L yields
Λ 0 + ( 1 + q ) 2 q Λ G = − ( 1 − q ) , Λ G = ( 1 − q ) H . \Lambda_0+\frac{(1+q)^2}{q}\Lambda_G=-(1-q),\qquad
\Lambda_G=(1-q)H. Λ 0 + q ( 1 + q ) 2 Λ G = − ( 1 − q ) , Λ G = ( 1 − q ) H .
The first coefficients are H = − q + q 2 − q 3 + O ( q 4 ) H=-q+q^2-q^3+O(q^4) H = − q + q 2 − q 3 + O ( q 4 ) , so division is legitimate in Q ( ( q ) ) \mathbb{Q}((q)) Q (( q )) . Therefore
G ~ C = ( 1 + q ) 2 q + 1 H . (41) \widetilde{G}_C=\frac{(1+q)^2}{q}+\frac{1}{H}. \tag*{(41)} G C = q ( 1 + q ) 2 + H 1 . (41)
The published B B B tree and its orbit sums
We use the tree for B B B in Callan–Mansour [8 Table 1, p. 28] . Let a m ( z ) a_m(z) a m ( z ) , b m , j ( z ) b_{m,j}(z) b m , j ( z ) , c m , j ( z ) c_{m,j}(z) c m , j ( z ) count nodes of its three types by length, with root a 1 a_1 a 1 at length one and 1 ≤ j ≤ m 1 \le j \le m 1 ≤ j ≤ m . Writing m ′ = m + 1 − j m' = m+1-j m ′ = m + 1 − j , the rules are
a m ⟶ a m + 1 , b m , 1 , … , b m , m , b m , j ⟶ c m , j , c m − 1 , j − 1 , … , c m ′ , 1 , a m ′ + 1 , b m ′ , 1 , … , b m ′ , m ′ , c m , j ⟶ c m + 1 , j , c m , j − 1 , … , c m ′ + 1 , 1 , a m ′ + 1 , b m ′ , 1 , … , b m ′ , m ′ . \begin{aligned}
a_m &\longrightarrow a_{m+1}, b_{m,1},\ldots,b_{m,m},\\
b_{m,j} &\longrightarrow c_{m,j},c_{m-1,j-1},\ldots,c_{m',1},a_{m'+1},b_{m',1},\ldots,b_{m',m'},\\
c_{m,j} &\longrightarrow c_{m+1,j},c_{m,j-1},\ldots,c_{m'+1,1},a_{m'+1},b_{m',1},\ldots,b_{m',m'}.
\end{aligned} a m b m , j c m , j ⟶ a m + 1 , b m , 1 , … , b m , m , ⟶ c m , j , c m − 1 , j − 1 , … , c m ′ , 1 , a m ′ + 1 , b m ′ , 1 , … , b m ′ , m ′ , ⟶ c m + 1 , j , c m , j − 1 , … , c m ′ + 1 , 1 , a m ′ + 1 , b m ′ , 1 , … , b m ′ , m ′ .
There is exactly one a a a -child per node, and the empty object precedes the root. Hence ∑ m a m = z G B \sum_m a_m=zG_B ∑ m a m = z G B . Define a separate boundary f f f by
a ( x ) = ∑ m ≥ 1 a m x m − 1 = z ( 1 + f ( x ) ) , B ( x , y ) = ∑ m , j b m , j x m − j y j − 1 , C ( x , y ) = ∑ m , j c m , j x m − j y j − 1 . a(x)=\sum_{m\ge1}a_mx^{m-1}=z(1+f(x)),\qquad B(x,y)=\sum_{m,j}b_{m,j}x^{m-j}y^{j-1},\qquad C(x,y)=\sum_{m,j}c_{m,j}x^{m-j}y^{j-1}. a ( x ) = m ≥ 1 ∑ a m x m − 1 = z ( 1 + f ( x )) , B ( x , y ) = m , j ∑ b m , j x m − j y j − 1 , C ( x , y ) = m , j ∑ c m , j x m − j y j − 1 .
In particular f ( 1 ) = G B − 1 f(1)=G_B-1 f ( 1 ) = G B − 1 . This f f f is a boundary of the published tree; it is different from both slack series F B F_B F B and F C F_C F C of Proposition 2. The rules give b m , j = a m + 1 b_{m,j}=a_{m+1} b m , j = a m + 1 , since their parent sets coincide, and therefore
B ( x , y ) = z f ( x ) − f ( y ) x − y , B(x,y)=z\frac{f(x)-f(y)}{x-y}, B ( x , y ) = z x − y f ( x ) − f ( y ) ,
( 1 − y + z x y ) C ( x , y ) = z ( B ( x , 1 ) − y B ( x , y ) ) + z x C ( x , 1 ) , (1-y+zxy)C(x,y)=z(B(x,1)-yB(x,y))+zxC(x,1), ( 1 − y + z x y ) C ( x , y ) = z ( B ( x , 1 ) − y B ( x , y )) + z x C ( x , 1 ) ,
a ( x ) = z + z x a ( x ) + z x ( B ( x , 1 ) + C ( x , 1 ) ) . (42) a(x)=z+zxa(x)+zx(B(x,1)+C(x,1)). \tag*{(42)} a ( x ) = z + z x a ( x ) + z x ( B ( x , 1 ) + C ( x , 1 )) . (42)
At y = ( 1 − z x ) − 1 y=(1-zx)^{-1} y = ( 1 − z x ) − 1 , eliminate C ( x , 1 ) C(x,1) C ( x , 1 ) to obtain ( 1 − z x ) f ( x ) − z x = ( x − 1 ) B ( x , 1 ) + y B ( x , y ) (1-zx)f(x)-zx=(x-1)B(x,1)+yB(x,y) ( 1 − z x ) f ( x ) − z x = ( x − 1 ) B ( x , 1 ) + y B ( x , y ) . Inserting B B B and clearing denominators proves
z f ( 1 1 − z x ) = ( 1 − z x ) ( 1 − x + z x + z x 2 ) f ( x ) + z ( 1 − x + z x 2 ) ( f ( 1 ) − x ) . (43) zf\left(\frac{1}{1-zx}\right)=(1-zx)(1-x+zx+zx^2)f(x)+z(1-x+zx^2)(f(1)-x). \tag*{(43)} z f ( 1 − z x 1 ) = ( 1 − z x ) ( 1 − x + z x + z x 2 ) f ( x ) + z ( 1 − x + z x 2 ) ( f ( 1 ) − x ) . (43)
Thus the scalar equation determines the total of the B B B class through f ( 1 ) = G B − 1 f(1)=G_B-1 f ( 1 ) = G B − 1 , without identifying f f f with the slack series F B F_B F B .
Put
x ( v ) = ( 1 + q ) ( 1 − v ) 1 − q v , E ( v ) = q + L v + q 2 v 2 , A ( v ) = ( 1 − q 2 v ) E ( v ) q ( 1 − q v ) 3 , b ( v ) = ( 1 − q ) 2 v ( 1 − q v ) 2 . x(v)=\frac{(1+q)(1-v)}{1-qv},\qquad E(v)=q+Lv+q^2v^2,\qquad\mathcal{A}(v)=\frac{(1-q^2v)E(v)}{q(1-qv)^3},\qquad b(v)=\frac{(1-q)^2v}{(1-qv)^2}. x ( v ) = 1 − q v ( 1 + q ) ( 1 − v ) , E ( v ) = q + Lv + q 2 v 2 , A ( v ) = q ( 1 − q v ) 3 ( 1 − q 2 v ) E ( v ) , b ( v ) = ( 1 − q v ) 2 ( 1 − q ) 2 v .
For F ( v ) = f ( x ( v ) ) \mathcal{F}(v)=f(x(v)) F ( v ) = f ( x ( v )) and g = G B − 1 g=G_B-1 g = G B − 1 , equation (39) is
F ( q v ) = A ( v ) F ( v ) + b ( v ) ( g − x ( v ) ) . (44) \mathcal{F}(qv)=\mathcal{A}(v)\mathcal{F}(v)+b(v)(g-x(v)). \tag*{(44)} F ( q v ) = A ( v ) F ( v ) + b ( v ) ( g − x ( v )) . (44)
With ( a ; q ) ∞ = ∏ j ≥ 0 ( 1 − a q j ) (a;q)_\infty=\prod_{j\ge0}(1-aq^j) ( a ; q ) ∞ = ∏ j ≥ 0 ( 1 − a q j ) and products of several arguments denoting products of these factors, define
U ( v ) = ( q v / r , q 2 r v ; q ) ∞ ( q v ; q ) ∞ 2 , W ( v ) = ( 1 − q ) 2 v 1 − q 2 v U ( v ) , J ( v ) = ( v / r , q r v ; q ) ∞ ( 1 − q v ) ( q v ; q ) ∞ 2 . (45) U(v)=\frac{(qv/r,q^2rv;q)_\infty}{(qv;q)_\infty^2},\qquad W(v)=\frac{(1-q)^2v}{1-q^2v}U(v),\qquad J(v)=\frac{(v/r,qrv;q)_\infty}{(1-qv)(qv;q)_\infty^2}. \tag*{(45)} U ( v ) = ( q v ; q ) ∞ 2 ( q v / r , q 2 r v ; q ) ∞ , W ( v ) = 1 − q 2 v ( 1 − q ) 2 v U ( v ) , J ( v ) = ( 1 − q v ) ( q v ; q ) ∞ 2 ( v / r , q r v ; q ) ∞ . (45)
Set
M a = ∑ k ≥ 0 W ( a q k ) , N a = ∑ k ≥ 0 W ( a q k ) x ( a q k ) , D = M 1 − M r , N = N 1 − N r . M_a=\sum_{k\ge0}W(aq^k),\qquad N_a=\sum_{k\ge0}W(aq^k)x(aq^k),\qquad\mathcal{D}=M_1-M_r,\qquad\mathcal{N}=N_1-N_r. M a = k ≥ 0 ∑ W ( a q k ) , N a = k ≥ 0 ∑ W ( a q k ) x ( a q k ) , D = M 1 − M r , N = N 1 − N r .
Cancellation of product factors, using E ( r ) = 0 E(r)=0 E ( r ) = 0 , gives
J ( q v ) A ( v ) = J ( v ) , J ( q v ) b ( v ) = W ( v ) . J(qv)\mathcal{A}(v)=J(v), \qquad J(qv)b(v)=W(v). J ( q v ) A ( v ) = J ( v ) , J ( q v ) b ( v ) = W ( v ) .
Multiplying (44) by J ( q v ) J(qv) J ( q v ) and summing on an orbit therefore telescopes. On the orbit from 1 1 1 , use F ( 1 ) = f ( 0 ) = 0 \mathcal{F}(1)=f(0)=0 F ( 1 ) = f ( 0 ) = 0 ; on the orbit from r r r , use J ( r ) = 0 J(r)=0 J ( r ) = 0 without dividing by A ( r ) = 0 \mathcal{A}(r)=0 A ( r ) = 0 . Since type a m a_m a m first occurs at length m m m , deg x [ z n ] f ≤ n \deg_x[z^n]f\le n deg x [ z n ] f ≤ n . Thus F ( a q k ) → F ( 0 ) \mathcal{F}(aq^k)\to\mathcal{F}(0) F ( a q k ) → F ( 0 ) and J ( a q k ) → 1 J(aq^k)\to1 J ( a q k ) → 1 q q q -adically. Since J ( 0 ) = 1 J(0)=1 J ( 0 ) = 1 , the result in either case is F ( 0 ) = g M a − N a \mathcal{F}(0)=gM_a-N_a F ( 0 ) = g M a − N a . Thus
G ~ B = 1 + N D . (46) \widetilde{G}_B=1+\frac{\mathcal{N}}{\mathcal{D}}. \tag*{(46)} G B = 1 + D N . (46)
The formal limits exist: W ( q k ) = O ( q k ) W(q^k)=O(q^k) W ( q k ) = O ( q k ) , W ( r q k ) = O ( q k + 1 ) W(rq^k)=O(q^{k+1}) W ( r q k ) = O ( q k + 1 ) , and D = 2 + O ( q ) \mathcal{D}=2+O(q) D = 2 + O ( q ) . For K = ( 1 + q + q 2 ) / q K=(1+q+q^2)/q K = ( 1 + q + q 2 ) / q , finite product cancellation also gives
J ( q v ) − J ( v ) = W ( v ) ( x ( v ) − K ) . (47) J(qv)-J(v)=W(v)(x(v)-K). \tag*{(47)} J ( q v ) − J ( v ) = W ( v ) ( x ( v ) − K ) . (47)
Indeed, after division by U ( v ) U(v) U ( v ) , the required polynomial identity is
( 1 − q v ) 3 − ( 1 − q 2 v ) ( 1 − v / r ) ( 1 − q r v ) = − ( 1 − q ) 2 q v ( 1 − q 3 v ) . (1-qv)^3-(1-q^2v)(1-v/r)(1-qrv)=-\frac{(1-q)^2}{q}v(1-q^3v). ( 1 − q v ) 3 − ( 1 − q 2 v ) ( 1 − v / r ) ( 1 − q r v ) = − q ( 1 − q ) 2 v ( 1 − q 3 v ) .
Since J ( 0 ) = 1 J(0)=1 J ( 0 ) = 1 and J ( r ) = 0 J(r)=0 J ( r ) = 0 , summing (47) yields N − K D = − J ( 1 ) \mathcal{N}-K\mathcal{D}=-J(1) N − K D = − J ( 1 ) . Equation (46) becomes
G ~ B = ( 1 + q ) 2 q − J ( 1 ) D . (48) \widetilde{G}_B=\frac{(1+q)^2}{q}-\frac{J(1)}{\mathcal{D}}. \tag*{(48)} G B = q ( 1 + q ) 2 − D J ( 1 ) . (48)
It remains to prove D = − J ( 1 ) H \mathcal{D}=-J(1)H D = − J ( 1 ) H .
A two-parameter summation
Lemma 2. For independent real parameters 0 < q < 1 0<q<1 0 < q < 1 and − 1 < r < 0 -1<r<0 − 1 < r < 0 , define U , W , J , M U,W,J,M U , W , J , M by (41) and the orbit sums above. Then
M 1 − M r = − J ( 1 ) ( 1 − β T ( q , r ) ) , β = ( 1 − q ) ( 1 − r ) ( 1 − q r ) q r . (49) M_1-M_r=-J(1)(1-\beta T(q,r)), \qquad\beta=\frac{(1-q)(1-r)(1-qr)}{qr}. \tag*{(49)} M 1 − M r = − J ( 1 ) ( 1 − β T ( q , r )) , β = q r ( 1 − q ) ( 1 − r ) ( 1 − q r ) . (49) The quadratic relation between q q q and r r r is not assumed here.
Proof. For ( a ; q ) n = ∏ j = 0 n − 1 ( 1 − a q j ) (a;q)_n=\prod_{j=0}^{n-1}(1-aq^j) ( a ; q ) n = ∏ j = 0 n − 1 ( 1 − a q j ) , use the convention
3 ϕ 2 ( a , b , c e , f ; q , q ) = ∑ n ≥ 0 ( a , b , c ; q ) n ( q , e , f ; q ) n q n . {}_3\phi_2\left(\begin{matrix}a,b,c\\e,f\end{matrix};q,q\right)
=\sum_{n\geq0}\frac{(a,b,c;q)_n}{(q,e,f;q)_n}q^n. 3 ϕ 2 ( a , b , c e , f ; q , q ) = n ≥ 0 ∑ ( q , e , f ; q ) n ( a , b , c ; q ) n q n .
The nonterminating q q q -Saalschütz identity [12 Eq. (II.24)] , in the form of [21 Eq. 17.7.5] , holds for 0 < ∣ q ∣ < 1 0<|q|<1 0 < ∣ q ∣ < 1 and e f = a b c q ef=abcq e f = ab c q , with denominator factors nonzero. It states
3 ϕ 2 ( a , b , c e , f ; q , q ) + ( q / e , a , b , c , q f / e ; q ) ∞ ( e / q , a q / e , b q / e , c q / e , f ; q ) ∞ 3 ϕ 2 ( a q / e , b q / e , c q / e q 2 / e , q f / e ; q , q ) = ( q / e , f / a , f / b , f / c ; q ) ∞ ( a q / e , b q / e , c q / e , f ; q ) ∞ . (50) {}_3\phi_2\left(\begin{matrix}a,b,c\\e,f\end{matrix};q,q\right)
+\frac{(q/e,a,b,c,qf/e;q)_\infty}{(e/q,aq/e,bq/e,cq/e,f;q)_\infty}
{}_3\phi_2\left(\begin{matrix}aq/e,bq/e,cq/e\\q^2/e,qf/e\end{matrix};q,q\right)
=\frac{(q/e,f/a,f/b,f/c;q)_\infty}{(aq/e,bq/e,cq/e,f;q)_\infty}. \tag*{(50)} 3 ϕ 2 ( a , b , c e , f ; q , q ) + ( e / q , a q / e , b q / e , c q / e , f ; q ) ∞ ( q / e , a , b , c , q f / e ; q ) ∞ 3 ϕ 2 ( a q / e , b q / e , c q / e q 2 / e , q f / e ; q , q ) = ( a q / e , b q / e , c q / e , f ; q ) ∞ ( q / e , f / a , f / b , f / c ; q ) ∞ . (50)
Set
a = b = q r , c = q 2 r , e = q 3 r s , f = q 2 r 2 / s , h = 1 − 1 / s , t = 1 − h . a=b=qr,\qquad c=q^{2}r,\qquad e=q^{3}rs,\qquad f=q^{2}r^{2}/s,\qquad h=1-1/s,\qquad t=1-h. a = b = q r , c = q 2 r , e = q 3 r s , f = q 2 r 2 / s , h = 1 − 1/ s , t = 1 − h .
The balance is exact. Denote the first series by Φ ( s ) \Phi(s) Φ ( s ) , the multiplier of the second by A ( s ) A(s) A ( s ) , and its terms by b n ( s ) b_n(s) b n ( s ) ; explicitly,
b n ( s ) = ( t / q , t / q , t ; q ) n ( q , t / ( q r ) , r t 2 ; q ) n q n , b_n(s)=\frac{(t/q,t/q,t;q)_n}{(q,t/(qr),rt^{2};q)_n}q^n, b n ( s ) = ( q , t / ( q r ) , r t 2 ; q ) n ( t / q , t / q , t ; q ) n q n ,
A ( s ) = ( t / ( q 2 r ) , q r , q r , q 2 r , r t 2 ; q ) ∞ ( q 2 r / t , t / q , t / q , t , q 2 r 2 t ; q ) ∞ . A(s)=\frac{(t/(q^{2}r),qr,qr,q^{2}r,rt^{2};q)_\infty}{(q^{2}r/t,t/q,t/q,t,q^{2}r^{2}t;q)_\infty}. A ( s ) = ( q 2 r / t , t / q , t / q , t , q 2 r 2 t ; q ) ∞ ( t / ( q 2 r ) , q r , q r , q 2 r , r t 2 ; q ) ∞ .
At s = 1 s=1 s = 1 , the first series is Φ ( 1 ) = M r / W ( r ) \Phi(1)=M_r/W(r) Φ ( 1 ) = M r / W ( r ) , as follows by comparing the n = 0 n=0 n = 0 terms and successive ratios. The multiplier has a triple pole:
( t / q ; q ) ∞ 2 ( t ; q ) ∞ = ( 1 − t / q ) 2 h 3 ( q t ; q ) ∞ 3 . (t/q;q)_\infty^{2}(t;q)_\infty=(1-t/q)^{2}h^{3}(qt;q)_\infty^{3}. ( t / q ; q ) ∞ 2 ( t ; q ) ∞ = ( 1 − t / q ) 2 h 3 ( q t ; q ) ∞ 3 .
Write A − 3 = lim h → 0 h 3 A ( s ) A_{-3}=\lim_{h\to0}h^{3}A(s) A − 3 = lim h → 0 h 3 A ( s ) . Finite shifts give
A − 3 = q 2 ( q − 2 / r ; q ) ∞ ( q r ; q ) ∞ 2 ( r ; q ) ∞ ( 1 − q ) 2 ( q 2 r 2 ; q ) ∞ ( q ; q ) ∞ 3 , A_{-3}=\frac{q^{2}(q^{-2}/r;q)_\infty(qr;q)_\infty^{2}(r;q)_\infty}{(1-q)^{2}(q^{2}r^{2};q)_\infty(q;q)_\infty^{3}}, A − 3 = ( 1 − q ) 2 ( q 2 r 2 ; q ) ∞ ( q ; q ) ∞ 3 q 2 ( q − 2 / r ; q ) ∞ ( q r ; q ) ∞ 2 ( r ; q ) ∞ ,
W ( r ) A − 3 = β J ( 1 ) . (51) W(r)A_{-3}=\beta J(1). \tag*{(51)} W ( r ) A − 3 = β J ( 1 ) . (51)
For clarity, the last cancellation reduces to
W ( r ) A − 3 J ( 1 ) = q 2 r ( 1 − q ) ( 1 − r ) 1 − q 2 r ( 1 − q − 2 / r ) ( 1 − q − 1 / r ) = β . \frac{W(r)A_{-3}}{J(1)}=\frac{q^{2}r(1-q)(1-r)}{1-q^{2}r}(1-q^{-2}/r)(1-q^{-1}/r)=\beta. J ( 1 ) W ( r ) A − 3 = 1 − q 2 r q 2 r ( 1 − q ) ( 1 − r ) ( 1 − q − 2 / r ) ( 1 − q − 1 / r ) = β .
For every n ≥ 2 n\ge2 n ≥ 2 ,
lim h → 0 A ( s ) b n ( s ) = − W ( q n − 2 ) W ( r ) . (52) \lim_{h\to0}A(s)b_n(s)=-\frac{W(q^{n-2})}{W(r)}. \tag*{(52)} h → 0 lim A ( s ) b n ( s ) = − W ( r ) W ( q n − 2 ) . (52)
A base case and ratio prove this for all indices. At n = 2 n=2 n = 2 ,
lim h → 0 b 2 h 3 = ( 1 − q − 1 ) 2 q 2 ( 1 − q 2 ) ( 1 − ( q r ) − 1 ) ( 1 − r − 1 ) ( 1 − r ) ( 1 − q r ) ; \lim_{h\to0}\frac{b_2}{h^{3}}=\frac{(1-q^{-1})^{2}q^{2}}{(1-q^{2})(1-(qr)^{-1})(1-r^{-1})(1-r)(1-qr)}; h → 0 lim h 3 b 2 = ( 1 − q 2 ) ( 1 − ( q r ) − 1 ) ( 1 − r − 1 ) ( 1 − r ) ( 1 − q r ) ( 1 − q − 1 ) 2 q 2 ;
multiplication by W ( r ) A − 3 / W ( 1 ) W(r)A_{-3}/W(1) W ( r ) A − 3 / W ( 1 ) gives − 1 -1 − 1 by finite product shifts. The common successive ratio for (48) is
q ( 1 − q n − 1 ) 2 ( 1 − q n ) ( 1 − q n + 1 ) ( 1 − q n − 1 / r ) ( 1 − r q n ) . q\frac{(1-q^{n-1})^{2}(1-q^{n})}{(1-q^{n+1})(1-q^{n-1}/r)(1-rq^{n})}. q ( 1 − q n + 1 ) ( 1 − q n − 1 / r ) ( 1 − r q n ) ( 1 − q n − 1 ) 2 ( 1 − q n ) .
In particular the n = 2 n=2 n = 2 term retains the orbit endpoint W ( 1 ) W(1) W ( 1 ) .
Divide the right side of (46) by A ( s ) A(s) A ( s ) and call it
P ( h ) = ( q r t ; q ) ∞ 2 ( r t ; q ) ∞ ( q 2 r / t ; q ) ∞ ( q r ; q ) ∞ 2 ( q 2 r ; q ) ∞ ( r t 2 ; q ) ∞ . P(h)=\frac{(qrt;q)_\infty^{2}(rt;q)_\infty(q^{2}r/t;q)_\infty}{(qr;q)_\infty^{2}(q^{2}r;q)_\infty(rt^{2};q)_\infty}. P ( h ) = ( q r ; q ) ∞ 2 ( q 2 r ; q ) ∞ ( r t 2 ; q ) ∞ ( q r t ; q ) ∞ 2 ( r t ; q ) ∞ ( q 2 r / t ; q ) ∞ .
The two exceptional terms are b 0 = 1 b_0=1 b 0 = 1 and
b 1 = − r h ( 1 − q − h ) 2 ( 1 − q ) ( 1 − q r − h ) ( 1 − r ( 1 − h ) 2 ) 2 . b_1=-\frac{rh(1-q-h)^{2}}{(1-q)(1-qr-h)(1-r(1-h)^{2})^{2}}. b 1 = − ( 1 − q ) ( 1 − q r − h ) ( 1 − r ( 1 − h ) 2 ) 2 r h ( 1 − q − h ) 2 .
Let
R ( h ) = ( 1 − r + r h ) ( 1 − q r ) ( 1 − h ) ( 1 − q r − h ) ( 1 − r ( 1 − h ) 2 ) . R(h)=\frac{(1-r+rh)(1-qr)(1-h)}{(1-qr-h)(1-r(1-h)^2)}. R ( h ) = ( 1 − q r − h ) ( 1 − r ( 1 − h ) 2 ) ( 1 − r + r h ) ( 1 − q r ) ( 1 − h ) .
The following two identities isolate the finite part:
R − 1 − b 1 = r q h 3 ( 1 − q ) ( 1 − q r − h ) ( 1 − r ( 1 − h ) 2 ) . (53) R-1-b_1=\frac{rqh^3}{(1-q)(1-qr-h)(1-r(1-h)^2)}. \tag*{(53)} R − 1 − b 1 = ( 1 − q ) ( 1 − q r − h ) ( 1 − r ( 1 − h ) 2 ) r q h 3 . (53)
P R = ( q r t ; q ) ∞ 3 ( q r / t ; q ) ∞ ( q r ; q ) ∞ 3 ( q r t 2 ; q ) ∞ . (54) \frac{P}{R}=\frac{(qrt;q)_\infty^3(qr/t;q)_\infty}{(qr;q)_\infty^3(qrt^2;q)_\infty}. \tag*{(54)} R P = ( q r ; q ) ∞ 3 ( q r t 2 ; q ) ∞ ( q r t ; q ) ∞ 3 ( q r / t ; q ) ∞ . (54)
The first is a polynomial identity after clearing denominators; the second uses four single-step product shifts. Put a = q r a=qr a = q r , λ = log t \lambda=\log t λ = log t and L j ( a ) = ( a ∂ a ) j log ( a ; q ) ∞ L_j(a)=(a\partial_a)^j\log(a;q)_\infty L j ( a ) = ( a ∂ a ) j log ( a ; q ) ∞ . Taking logarithms of (54) gives
log ( P / R ) = ∑ j ≥ 1 3 + ( − 1 ) j − 2 j j ! L j ( a ) λ j . \log(P/R)=\sum_{j\geq1}\frac{3+(-1)^j-2^j}{j!}L_j(a)\lambda^j. log ( P / R ) = j ≥ 1 ∑ j ! 3 + ( − 1 ) j − 2 j L j ( a ) λ j .
The linear and quadratic coefficients vanish, the cubic coefficient is − L 3 ( a ) -L_3(a) − L 3 ( a ) , and
L 3 ( a ) = − ∑ k ≥ 1 k 2 a k 1 − q k = − T ( q , r ) , λ 3 = − h 3 + O ( h 4 ) . L_3(a)=-\sum_{k\geq1}\frac{k^2a^k}{1-q^k}=-T(q,r),\qquad\lambda^3=-h^3+O(h^4). L 3 ( a ) = − k ≥ 1 ∑ 1 − q k k 2 a k = − T ( q , r ) , λ 3 = − h 3 + O ( h 4 ) .
Consequently P − R = − T h 3 + O ( h 4 ) P-R=-Th^3+O(h^4) P − R = − T h 3 + O ( h 4 ) , and (53) proves
[ h 3 ] ( P − 1 − b 1 ) = 1 β − T . (55) [h^3](P-1-b_1)=\frac{1}{\beta}-T. \tag*{(55)} [ h 3 ] ( P − 1 − b 1 ) = β 1 − T . (55)
Now (50) reads Φ ( s ) = A ( s ) ( P − 1 − b 1 − ∑ n ≥ 2 b n ) \Phi(s)=A(s)(P-1-b_1-\sum_{n\geq2}b_n) Φ ( s ) = A ( s ) ( P − 1 − b 1 − ∑ n ≥ 2 b n ) . Using (52) and (55) gives
M r W ( r ) = A − 3 ( 1 / β − T ) + M 1 W ( r ) . \frac{M_r}{W(r)}=A_{-3}(1/\beta-T)+\frac{M_1}{W(r)}. W ( r ) M r = A − 3 ( 1/ β − T ) + W ( r ) M 1 .
Equation (51) proves (49) .
To justify the limit through the infinite tail, for n ≥ 2 n\geq2 n ≥ 2 extract the three zeros explicitly:
b n h 3 = ( 1 − t / q ) 2 ( q t ; q ) n − 2 2 ( q t ; q ) n − 1 q n ( q ; q ) n ( t / ( q r ) ; q ) n ( r t 2 ; q ) n . \frac{b_n}{h^3}=\frac{(1-t/q)^2(qt;q)_{n-2}^2(qt;q)_{n-1}q^n}{(q;q)_n(t/(qr);q)_n(rt^2;q)_n}. h 3 b n = ( q ; q ) n ( t / ( q r ) ; q ) n ( r t 2 ; q ) n ( 1 − t / q ) 2 ( q t ; q ) n − 2 2 ( q t ; q ) n − 1 q n .
For fixed 0 < q < 1 0<q<1 0 < q < 1 , − 1 < r < 0 -1<r<0 − 1 < r < 0 , on a sufficiently small closed complex neighborhood of h = 0 h=0 h = 0 the denominator products are bounded away from zero uniformly in n n n , and the numerator products are bounded. Therefore ∣ b n / h 3 ∣ ≤ C q n |b_n/h^3|\leq Cq^n ∣ b n / h 3 ∣ ≤ C q n . The two 3 ϕ 2 {}_3\phi_2 3 ϕ 2 series have argument q q q , so they converge, and this bound justifies termwise passage to the limit. All product shifts and logarithmic derivatives above are then valid there.
Formal specialization and completion of the proof
On the branch q + L r + q 2 r 2 = 0 q+Lr+q^2r^2=0 q + L r + q 2 r 2 = 0 , elementary algebra gives
β = − θ , J ( 1 ) = 1 − q 2 q U ( 1 ) . \beta=-\theta,\qquad J(1)=\frac{1-q^2}{q}U(1). β = − θ , J ( 1 ) = q 1 − q 2 U ( 1 ) .
The implicit function theorem makes r ( q ) r(q) r ( q ) analytic near zero; moreover, q / r = − L − q 2 r q/r=-L-q^{2}r q / r = − L − q 2 r removes the apparent singularity in U U U . The functions U ( 1 ) U(1) U ( 1 ) , M 1 M_{1} M 1 , M r M_{r} M r and q J ( 1 ) qJ(1) q J ( 1 ) are analytic germs, since their nonconstant factors and orbit tails converge uniformly on sufficiently small disks. In q J ( 1 ) qJ(1) q J ( 1 ) the prefactor q q q removes its simple pole. In particular,
D ( 0 ) = 2 , ( q J ( 1 ) ) ( 0 ) = 2. \mathcal{D}(0)=2,\qquad(qJ(1))(0)=2. D ( 0 ) = 2 , ( q J ( 1 )) ( 0 ) = 2.
For sufficiently small positive q q q , the branch has − 1 < r ( q ) < 0 -1<r(q)<0 − 1 < r ( q ) < 0 . Lemma 2 thus gives
q D + ( q J ( 1 ) ) H = 0 q\mathcal{D}+(qJ(1))H=0 q D + ( q J ( 1 )) H = 0
on a real interval. Both sides are analytic at zero, so the identity theorem proves the corresponding formal identity. It gives H = − q + O ( q 2 ) H=-q+O(q^{2}) H = − q + O ( q 2 ) and D = − J ( 1 ) H \mathcal{D}=-J(1)H D = − J ( 1 ) H . Equations (37) and (44) coincide. Since z = q + O ( q 2 ) z=q+O(q^{2}) z = q + O ( q 2 ) is formally invertible, G B = G C G_{B}=G_{C} G B = G C as length series. The published bijection G A = G C G_{A}=G_{C} G A = G C completes Theorem 1.
A common counting formula for Class 152
An inversion sequence of length n n n is e = ( e 0 , … , e n − 1 ) e=(e_{0},\ldots,e_{n-1}) e = ( e 0 , … , e n − 1 ) with 0 ≤ e i ≤ i 0\le e_{i}\le i 0 ≤ e i ≤ i . A pattern occurs on three increasing indices when both inequalities and equalities agree with the pattern. Write I n ( B 152 ) \mathcal{I}_{n}(B_{152}) I n ( B 152 ) for the sequences avoiding every pattern in B 152 B_{152} B 152 , and put
A 152 = { 010 , 100 , 102 , 210 } , B 152 = { 011 , 201 , 210 } . A_{152}=\{010,100,102,210\},\qquad B_{152}=\{011,201,210\}. A 152 = { 010 , 100 , 102 , 210 } , B 152 = { 011 , 201 , 210 } .
Theorem 3. For every n ≥ 0 n\ge0 n ≥ 0 , ∣ I n ( A 152 ) ∣ = ∣ I n ( B 152 ) ∣ |\mathcal{I}_{n}(A_{152})|=|\mathcal{I}_{n}(B_{152})| ∣ I n ( A 152 ) ∣ = ∣ I n ( B 152 ) ∣ . The common count is 1 at n = 0 n=0 n = 0 ; for every n ≥ 1 n\ge1 n ≥ 1 it is
a n = 1 + 1 2 ∑ j = 1 n − 1 ( 2 j j ) . a_{n}=1+\frac{1}{2}\sum_{j=1}^{n-1}\binom{2j}{j}. a n = 1 + 2 1 j = 1 ∑ n − 1 ( j 2 j ) .
For n ≥ 1 n\ge1 n ≥ 1 , the number a n a_{n} a n is OEIS A024718( n − 1 ) (n-1) ( n − 1 ) [22 ] . That entry already records the partial central-binomial sum and its generating function
∑ k ≥ 0 A 024718 ( k ) z k = 1 + ( 1 − 4 z ) − 1 / 2 2 ( 1 − z ) . \sum_{k\ge0}\mathrm{A024718}(k)z^{k}=\frac{1+(1-4z)^{-1/2}}{2(1-z)}. k ≥ 0 ∑ A024718 ( k ) z k = 2 ( 1 − z ) 1 + ( 1 − 4 z ) − 1/2 .
the latter attributed to Michael Somos (14 February 2006). The new contribution is the enumeration of the two specified inversion-sequence avoidance classes and the proof of their Wilf equivalence. This is Class 152 of Conjecture 1 in Callan–Mansour, Inversion sequences avoiding quadruple length-3 patterns [8 ] , Section 1. We use ordinary length n n n throughout, including the empty sequence. The triple-avoidance class B 152 B_{152} B 152 appears as class 73 in Table 7 of Callan, Jelínek and Mansour [7 ] , where its initial counting sequence is recorded. The theorem above gives its closed counting formula and its equality with the quadruple-avoidance class A 152 A_{152} A 152 .
The first-descent decomposition
If a value a a a follows a larger value, any second occurrence of a a a gives 010 or 100. Thus a a a occurs exactly once. If an adjacent descent M > a M>a M > a has a larger value elsewhere, that value forms 210 when it is earlier and 102 when it is later. Consequently every adjacent descent starts at the global maximum. A nonmonotone avoider has a unique cut p s p\,s p s at its first adjacent descent: p p p is a nondecreasing inversion sequence ending in the global maximum M M M , and s s s begins below M M M . Its entries other than M M M are distinct and increasing (a decrease between two of them gives 210 with the preceding M M M ). They avoid all values of p p p . Moreover they lie in one gap ( u , v ) (u,v) ( u , v ) between successive distinct values of p p p : crossing a prefix value v v v gives the triple v , a , b v,a,b v , a , b of type 102. If v < M v<M v < M , no M M M can occur in s s s , since v , a , M v,a,M v , a , M would give 102. Conversely these conditions exclude all four forbidden patterns. The bounds e i ≤ i e_i\le i e i ≤ i are automatic in s s s , since its entries are at most M ≤ ∣ p ∣ − 1 M\le|p|-1 M ≤ ∣ p ∣ − 1 .
Let m = ∣ p ∣ m=|p| m = ∣ p ∣ , r = ∣ s ∣ ≥ 1 r=|s|\ge1 r = ∣ s ∣ ≥ 1 , and let g 1 , … , g k g_1,\ldots,g_k g 1 , … , g k be the positive jumps between consecutive distinct values of p p p (starting from 0). An internal gap of size g g g contributes ( g − 1 r ) \binom{g-1}{r} ( r g − 1 ) . The top gap contributes
∑ b ≥ 1 ( g k − 1 b ) ( r − 1 b − 1 ) = ( g k + r − 2 r ) . (56) \sum_{b\ge1}\binom{g_k-1}{b}\binom{r-1}{b-1}=\binom{g_k+r-2}{r}. \tag*{(56)} b ≥ 1 ∑ ( b g k − 1 ) ( b − 1 r − 1 ) = ( r g k + r − 2 ) . (56)
Here b b b is the number of smaller entries and the second factor chooses their positions, with the first position required to be smaller. Empty sums contribute zero; a gap of size 1 contributes zero.
Encode p p p as a Dyck path by requiring exactly p i p_i p i down-steps in total before its ( i + 1 ) (i+1) ( i + 1 ) st up-step and completing with down-steps. Nondecreasing inversion sequences of length m m m are thereby in bijection with Dyck paths of semilength m m m . Their positive jumps are precisely the lengths of the nonfinal down-runs; the top jump is the penultimate down-run. This translates (52) into the weighted path series below.
Weighted Dyck paths and the left generating function
Work in formal power series over Q \mathbb{Q} Q . Set
C = ∑ m ≥ 0 1 m + 1 ( 2 m m ) z m , t = z C , C = 1 + z C 2 = 1 1 − t , z = t ( 1 − t ) . (57) C=\sum_{m\ge0}\frac{1}{m+1}\binom{2m}{m}z^m,\qquad t=zC,\qquad C=1+zC^2=\frac{1}{1-t},\qquad z=t(1-t). \tag*{(57)} C = m ≥ 0 ∑ m + 1 1 ( m 2 m ) z m , t = z C , C = 1 + z C 2 = 1 − t 1 , z = t ( 1 − t ) . (57)
For a weight w w w with w ( 0 ) = 0 w(0)=0 w ( 0 ) = 0 , let D w D_w D w count paths weighted by their final down-run, H w H_w H w count the sum of weights of all nonfinal down-runs, and J w J_w J w count the weight of the penultimate down-run (zero if absent). All series include the factor z m z^m z m for semilength m m m . Then
( 2 − C ) H w = ( C − 1 ) D w , ( 1 − z ) J w = t D w . (58) (2-C)H_w=(C-1)D_w,\qquad(1-z)J_w=tD_w. \tag*{(58)} ( 2 − C ) H w = ( C − 1 ) D w , ( 1 − z ) J w = t D w . (58)
Here is a derivation that also checks the marked-run multiplicities. Reflect a Dyck path to exchange final down-runs and initial up-runs. A path whose initial up-run has length k k k has a unique factorization U k D P 1 D P 2 ⋯ D P k U^kDP_1DP_2\cdots DP_k U k D P 1 D P 2 ⋯ D P k , with k k k arbitrary Dyck paths P i P_i P i . Thus paths with that initial run contribute t k t^k t k . Let S w S_w S w count the sum of weights of all up-runs. The factorization gives
S w = D w + S w ∑ k ≥ 1 k z k C k − 1 = D w + t C S w . S_w=D_w+S_w\sum_{k\ge1}kz^kC^{k-1}=D_w+tCS_w. S w = D w + S w k ≥ 1 ∑ k z k C k − 1 = D w + tC S w .
Since t C = C − 1 tC=C-1 tC = C − 1 and reflection gives H w = S w − D w H_w=S_w-D_w H w = S w − D w , the first identity in (54) follows. For the second up-run, select the first nonempty P i P_i P i ; factors before it are empty, and factors after it are arbitrary. Hence
J w = D w ∑ k ≥ 1 z k ∑ j = 0 k − 1 C j = z C 1 − z D w . J_w=D_w\sum_{k\ge1}z^k\sum_{j=0}^{k-1}C^j=\frac{zC}{1-z}D_w. J w = D w k ≥ 1 ∑ z k j = 0 ∑ k − 1 C j = 1 − z z C D w .
Reflection gives the asserted identity for the penultimate down-run.
For q q q of constant term 1, use w q ( ℓ ) = q ℓ − 1 − 1 w_q(\ell)=q^{\ell-1}-1 w q ( ℓ ) = q ℓ − 1 − 1 for ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 and w q ( 0 ) = 0 w_q(0)=0 w q ( 0 ) = 0 , and write D q , H q , J q D_q,H_q,J_q D q , H q , J q .
The same run factorization yields
D q = ∑ ℓ ≥ 1 ( q ℓ − 1 − 1 ) t ℓ = C t 2 ( q − 1 ) 1 − q t . (59) D_q=\sum_{\ell\ge1}(q^{\ell-1}-1)t^\ell=\frac{Ct^2(q-1)}{1-qt}. \tag*{(59)} D q = ℓ ≥ 1 ∑ ( q ℓ − 1 − 1 ) t ℓ = 1 − q t C t 2 ( q − 1 ) . (59)
With q 1 = 1 + z q_1=1+z q 1 = 1 + z and q 2 = ( 1 − z ) − 1 q_2=(1-z)^{-1} q 2 = ( 1 − z ) − 1 , binomial expansion gives [ z r ] w q 1 ( g ) = ( g − 1 r ) [z^r]w_{q_1}(g)=\binom{g-1}{r} [ z r ] w q 1 ( g ) = ( r g − 1 ) and [ z r ] w q 2 ( g ) = ( g + r − 2 r ) [z^r]w_{q_2}(g)=\binom{g+r-2}{r} [ z r ] w q 2 ( g ) = ( r g + r − 2 ) for r ≥ 1 r\ge1 r ≥ 1 . The first-descent decomposition therefore gives the left series
L = ∑ n ≥ 0 ∣ I n ( A 152 ) ∣ z n = C + H q 1 + J q 2 − J q 1 . (60) L=\sum_{n\ge0}|\mathcal{I}_n(A_{152})|z^n=C+H_{q_1}+J_{q_2}-J_{q_1}. \tag*{(60)} L = n ≥ 0 ∑ ∣ I n ( A 152 ) ∣ z n = C + H q 1 + J q 2 − J q 1 . (60)
In (60) , H q 1 H_{q_1} H q 1 initially weights every nonfinal down-run as an internal gap; the difference of the two J J J terms replaces the top-gap weight. The path’s power of z z z records prefix length, and the weight’s power records suffix length.
Equations (57) –(59) give, directly,
D q 1 = t 3 ( 1 − t ) ( 1 − t 2 ) , D q 2 = t 3 ( 1 − t ) 2 = ( 1 + t ) D q 1 , D_{q_1}=\frac{t^3}{(1-t)(1-t^2)},\qquad D_{q_2}=\frac{t^3}{(1-t)^2}=(1+t)D_{q_1}, D q 1 = ( 1 − t ) ( 1 − t 2 ) t 3 , D q 2 = ( 1 − t ) 2 t 3 = ( 1 + t ) D q 1 ,
H q 1 + J q 2 − J q 1 = D q 1 ( t 1 − 2 t + t 2 1 − z ) = C t 4 ( 1 − z ) ( 1 − 2 t ) . (61) H_{q_1}+J_{q_2}-J_{q_1}=D_{q_1}\left(\frac{t}{1-2t}+\frac{t^2}{1-z}\right)=\frac{Ct^4}{(1-z)(1-2t)}. \tag*{(61)} H q 1 + J q 2 − J q 1 = D q 1 ( 1 − 2 t t + 1 − z t 2 ) = ( 1 − z ) ( 1 − 2 t ) C t 4 . (61)
All denominators used here have nonzero constant term, so these operations are valid in formal power series.
The last-zero decomposition and the right generating function
Avoiding 011 means that all positive entries are distinct, since e 0 = 0 e_0=0 e 0 = 0 . Cut a nonempty avoider uniquely as p 0 s p\,0\,s p 0 s at its last zero, with m = ∣ p ∣ m=|p| m = ∣ p ∣ and M = max ( p ) M=\max(p) M = max ( p ) (take M = 0 M=0 M = 0 for empty p p p ). Positive entries of p p p are increasing: a positive descent followed by the last zero gives 210. Every entry of s s s exceeds M M M : equality is excluded by 011, and a positive entry below M M M gives M , 0 , a M,0,a M , 0 , a of type 201. Thus s s s consists of distinct entries above M M M , avoids 201, 210, and satisfies s j ≤ m + 1 + j s_j\le m+1+j s j ≤ m + 1 + j . Conversely these conditions suffice: a forbidden triple crossing the cut would contradict either the increasing positive prefix or the separation of prefix and suffix values.
The running-maximum map sends p p p bijectively to a nondecreasing inversion sequence: the inverse retains strict increases and replaces other entries by zero (retaining the first entry 0). It preserves M M M . Its Dyck path has final down-run length h = m − M h=m-M h = m − M ; the empty prefix corresponds to the empty path with h = 0 h=0 h = 0 .
A distinct-entry word avoiding 201, 210 has a unique decomposition into rotated increasing blocks: sort its entries, partition into nonempty consecutive blocks, and move the minimum of each block to its end. Indeed, at the position of the global minimum, the preceding entries must increase (otherwise 210), and must be below every following entry (otherwise 201). Remove this first block and repeat; this also proves uniqueness and the converse. For example, sorted blocks ( 3 , 4 ) ∣ ( 6 ) (3,4)\mid(6) ( 3 , 4 ) ∣ ( 6 ) become the suffix 4, 3, 6: the entry 4 moves one place to the left and 3 moves to the end of its block, while the singleton 6 stays in place.
For the sorted entries a i a_i a i , put λ i = a i − M − ( i + 1 ) \lambda_i=a_i-M-(i+1) λ i = a i − M − ( i + 1 ) , with i i i starting at 0. These labels are weakly increasing and nonnegative. The bounds on the rotated word are exactly 0 ≤ λ i ≤ h 0\le\lambda_i\le h 0 ≤ λ i ≤ h , with labels in block tails strictly below h h h . Here the tail of a block consists of all entries other than its minimum in the unrotated increasing block; each such entry moves one place earlier, whereas the minimum moves to the end of its block. A singleton can have label h h h ; in a longer block its minimum is bounded by its tail labels. For the example above, take M = 1 M=1 M = 1 , m = 3 m=3 m = 3 , so h = 2 h=2 h = 2 . The labels of 3 , 4 , 6 3,4,6 3 , 4 , 6 are 1 , 1 , 2 1,1,2 1 , 1 , 2 : the tail label 1 1 1 is strictly below h h h , and the singleton label is h h h . Adding back M + i + 1 M+i+1 M + i + 1 reverses this encoding.
For each label 0 , … , h − 1 0,\ldots,h-1 0 , … , h − 1 , an occurrence may start a block or continue one, giving two choices; the first occurrence overall must start a block. Every occurrence of h h h must start a singleton. Words containing a lower label therefore have half the unrestricted binary choices, while words containing only h h h have one choice. The suffix series (including the empty suffix) is consequently
S h = 1 1 − z + ( 1 − 2 z ) − h − 1 2 ( 1 − z ) = 1 + ( 1 − 2 z ) − h 2 ( 1 − z ) . (62) S_h=\frac{1}{1-z}+\frac{(1-2z)^{-h}-1}{2(1-z)}=\frac{1+(1-2z)^{-h}}{2(1-z)}. \tag*{(62)} S h = 1 − z 1 + 2 ( 1 − z ) ( 1 − 2 z ) − h − 1 = 2 ( 1 − z ) 1 + ( 1 − 2 z ) − h . (62)
The last zero contributes z z z . The final-run factorization in the preceding subsection, now with weight r h r^h r h , gives ∑ P z ∣ P ∣ r h ( P ) = ( 1 − r t ) − 1 \sum_P z^{|P|}r^h(P)=(1-rt)^{-1} ∑ P z ∣ P ∣ r h ( P ) = ( 1 − r t ) − 1 . Using r = ( 1 − 2 z ) − 1 r=(1-2z)^{-1} r = ( 1 − 2 z ) − 1 in (58), we obtain
R = ∑ n ≥ 0 ∣ I n ( B 152 ) ∣ z n = 1 + z 2 ( 1 − z ) ( C + 1 1 − t / ( 1 − 2 z ) ) = 1 + z ( 1 − t ) ( 1 − z ) ( 1 − 2 t ) = L , (63) R=\sum_{n\ge0}|\operatorname{I\!n}(B_{152})|z^n=1+\frac{z}{2(1-z)}\left(C+\frac{1}{1-t/(1-2z)}\right)=1+\frac{z(1-t)}{(1-z)(1-2t)}=L, \tag*{(63)} R = n ≥ 0 ∑ ∣ I n ( B 152 ) ∣ z n = 1 + 2 ( 1 − z ) z ( C + 1 − t / ( 1 − 2 z ) 1 ) = 1 + ( 1 − z ) ( 1 − 2 t ) z ( 1 − t ) = L , (63)
where the last two simplifications use z = t ( 1 − t ) z=t(1-t) z = t ( 1 − t ) and (57). Finally 1 − 2 t = 1 − 4 z 1-2t=\sqrt{1-4z} 1 − 2 t = 1 − 4 z , so
L = R = 1 + z 2 ( 1 − z ) ( 1 + 1 1 − 4 z ) . L=R=1+\frac{z}{2(1-z)}\left(1+\frac{1}{\sqrt{1-4z}}\right). L = R = 1 + 2 ( 1 − z ) z ( 1 + 1 − 4 z 1 ) .
Extracting coefficients proves the theorem. For n = 0 , … , 10 n=0,\ldots,10 n = 0 , … , 10 , the counts are
1 , 1 , 2 , 5 , 15 , 50 , 176 , 638 , 2354 , 8789 , 33099 1,1,2,5,15,50,176,638,2354,8789,33099 1 , 1 , 2 , 5 , 15 , 50 , 176 , 638 , 2354 , 8789 , 33099 .
Formal verification record. The formal record uses Lean 4 [11 ] and mathlib [18 ] . The source theorem InversionSeqClass152.result states the all-length equality of the finite avoider counts. Its pinned source is InversionSeqClass152.lean. The closed coefficient formula above follows by the displayed generating-function calculation. The mathematical proof here is complete independently of this verification record. The supplementary material gives the pinned Lean and mathlib versions and a command to check this source theorem.
Conclusion
The two enumeration problems have explicit solutions. For Class 152, the common count is a partial central-binomial sum. For Class 207, Theorem 1 proves equality of all three counting series and gives their common Lambert-series expression. The C kernel and the published B tree lead to different scalar formulas; the cubic limit of the nonterminating q q q -Saalschütz summation is the identity that connects them, while the A–C step is the published bijection of Callan–Mansour.
The expanded supplement preserves the fixed-maximum rational expansion (Section ??), finite computations (Section ??–??), refined generating functions and analytic obstruction theorems (Sections ??–??), the signed catalytic identity (Section ??), and the Python verification program (??). The pole calculations there are related to the orbit-residue viewpoint of rational q q q -summability in Chen and Singer [9 Proposition 2.10] . Those results provide additional structure and reproducibility without interrupting the two complete proof paths in the main text.
Declarations
Funding. This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.
Declaration of competing interest. The authors declare that they have no competing interests.
Data availability. The data and verification code supporting the finite computations are available with reproduction instructions in the companion code and data repository. The accompanying supplementary PDF contains the expanded proofs and the recurrence program; its Section ?? describes the finite checks. The ordinary proofs are contained in this article.
Declaration of generative AI and AI-assisted technologies in the manuscript preparation process. Haobo Ma and Wenlin Zhang used AI tools, namely ChatGPT Pro (GPT-6 Pro), Codex (gpt-6.1-sol) and Claude Opus 5.5 (via Claude Code), for literature search, computation and double-checking, including formal verification of the results in Lean. All proofs can be checked by hand, and the computations can be reproduced from the verification package. H. Ma and W. Zhang take full responsibility for their contributions.
Fixed-maximum expansion for 207(2)
Let c n , m c_{n,m} c n , m count the C C C -avoiding inversion sequences of maximum exactly m m m , and write R m ( z ) = ∑ n ≥ 1 c n , m z n R_m(z)=\sum_{n\ge1}c_{n,m}z^n R m ( z ) = ∑ n ≥ 1 c n , m z n . Fix the alphabet { 0 , … , m } \{0,\ldots,m\} { 0 , … , m } . A state q = ( M , S , D ) q=(M,S,D) q = ( M , S , D ) records the maximum, the seen values still admissible, and the forbidden values. Start at q 0 = ( 0 , { 0 } , ∅ ) q_0=(0,\{0\},\varnothing) q 0 = ( 0 , { 0 } , ∅ ) . For x ∉ D x\notin D x ∈ / D , set
D ′ = { D , x > M , D ∪ { 0 , … , M − 1 } , x = M , D ∪ { 0 , … , x } ∪ { a ∈ S : a > x } , x < M , q x = ( max ( M , x ) , ( S ∪ { x } ) ∖ D ′ , D ′ ) . (64) D' =
\begin{cases}
D, & x>M,\\
D\cup\{0,\ldots,M-1\}, & x=M,\\
D\cup\{0,\ldots,x\}\cup\{a\in S:a>x\}, & x<M,
\end{cases}
\qquad q_x=\left(\max(M,x),(S\cup\{x\})\setminus D',D'\right). \tag*{(64)} D ′ = ⎩ ⎨ ⎧ D , D ∪ { 0 , … , M − 1 } , D ∪ { 0 , … , x } ∪ { a ∈ S : a > x } , x > M , x = M , x < M , q x = ( max ( M , x ) , ( S ∪ { x }) ∖ D ′ , D ′ ) . (64)
Let Q m Q_m Q m be the closure of q 0 q_0 q 0 under these children, and define
( T m ) q , t = # { x ∈ { 0 , … , m } ∖ D ( q ) : q x = t } , r m ( q ) = 1 { M ( q ) = m } . (T_m)_{q,t}=\#\{x\in\{0,\ldots,m\}\setminus D(q):q_x=t\},\qquad r_m(q)=\mathbf{1}_{\{M(q)=m\}}. ( T m ) q , t = # { x ∈ { 0 , … , m } ∖ D ( q ) : q x = t } , r m ( q ) = 1 { M ( q ) = m } .
Let p m ( q ) p_m(q) p m ( q ) count legal inversion prefixes of length m + 1 m+1 m + 1 at q q q : start at q 0 q_0 q 0 at length one and, at length n ≤ m n\le m n ≤ m , allow only 0 ≤ x ≤ n 0\le x\le n 0 ≤ x ≤ n in (A.1). Regard p m , r m p_m,r_m p m , r m as column vectors.
Proposition 5. For every $m\ge 0,
det ( I − z T m ) = ( 1 − z ) m + 1 , \det(I-zT_m)=(1-z)^{m+1}, det ( I − z T m ) = ( 1 − z ) m + 1 , R m ( z ) = z m + 1 p m T ( I − z T m ) − 1 r m = P m ( z ) ( 1 − z ) m + 1 . (65) R_m(z)=z^{m+1}p_m^{\mathsf{T}}(I-zT_m)^{-1}r_m=\frac{P_m(z)}{(1-z)^{m+1}}. \tag*{(65)} R m ( z ) = z m + 1 p m T ( I − z T m ) − 1 r m = ( 1 − z ) m + 1 P m ( z ) . (65) G C ( z ) = 1 + ∑ m ≥ 0 P m ( z ) ( 1 − z ) m + 1 . (66) G_C(z)=1+\sum_{m\ge0}\frac{P_m(z)}{(1-z)^{m+1}}. \tag*{(66)} G C ( z ) = 1 + m ≥ 0 ∑ ( 1 − z ) m + 1 P m ( z ) . (66) Here P m ( z ) = z m + 1 p m T adj ( I − z T m ) r m P_m(z)=z^{m+1}p_m^{\mathsf{T}}\operatorname{adj}(I-zT_m)r_m P m ( z ) = z m + 1 p m T adj ( I − z T m ) r m is an integer polynomial, z m + 1 ∣ P m z^{m+1}\mid P_m z m + 1 ∣ P m , deg P m ≤ 4 m + 2 \deg P_m\le4m+2 deg P m ≤ 4 m + 2 , and P m ( 1 ) = 1 P_m(1)=1 P m ( 1 ) = 1 . For fixed m m m , c n , m c_{n,m} c n , m is polynomial in n n n of degree m m m and leading coefficient 1 / m ! 1/m! 1/ m ! for n ≥ 3 m + 2 n\ge3m+2 n ≥ 3 m + 2 .
Proof. The pair exclusions used in § 2 give (A.1). Seen forbidden values can be forgotten because their subsequent exclusions are already forbidden. Every non-loop step increases M M M or strictly enlarges D D D . The only self-loops, each of multiplicity one, are L j = ( j , { j } , { 0 , … , j − 1 } ) L_j=(j,\{j\},\{0,\ldots,j-1\}) L j = ( j , { j } , { 0 , … , j − 1 }) , 0 ≤ j ≤ m 0\le j\le m 0 ≤ j ≤ m . Each is reachable by introducing and repeating j j j (with L 0 = q 0 L_0=q_0 L 0 = q 0 ). Ordering states by ( M , ∣ D ∣ ) (M,|D|) ( M , ∣ D ∣ ) makes the matrix upper triangular and gives the determinant. After length m + 1 m+1 m + 1 , every value in the fixed alphabet satisfies the inversion bound, so subsequent walks give (A.2).
Remove self-loops from a walk. Its remaining path has at most m m m steps increasing M M M and at most m m m other steps, since each of the latter forbids a new value below m m m . Its contribution has the form z m + 1 + d / ( 1 − z ) ℓ z^{m+1+d}/(1-z)^\ell z m + 1 + d / ( 1 − z ) ℓ , with d ≤ 2 m d \le2m d ≤ 2 m and ℓ ≤ m + 1 \ell\le m+1 ℓ ≤ m + 1 , including prefix multiplicity. Bringing this finite sum to the common denominator proves the degree bound. Exactly one contribution visits all m + 1 m+1 m + 1 loops: the prefix is 0 m + 1 0^{m+1} 0 m + 1 , followed between L j L_j L j and L j + 1 L_{j+1} L j + 1 by j + 1 , j + 1 j+1,j+1 j + 1 , j + 1 . It contributes z 3 m + 1 / ( 1 − z ) m + 1 z^{3m+1}/(1-z)^{m+1} z 3 m + 1 / ( 1 − z ) m + 1 , proving P m ( 1 ) = 1 P_m(1)=1 P m ( 1 ) = 1 . If P m ( z ) = ∑ i u i z i P_m(z)=\sum_i u_i z^i P m ( z ) = ∑ i u i z i , then for n ≥ 3 m + 2 n \ge3m+2 n ≥ 3 m + 2 the coefficient is the polynomial ∑ i u i ( n − i + m m ) \sum_i u_i \binom{n-i+m}{m} ∑ i u i ( m n − i + m ) . Terms with i > n i>n i > n vanish in its polynomial interpretation by the degree bound. Its leading coefficient is P m ( 1 ) / m ! P_m(1)/m! P m ( 1 ) / m ! . Finally z m + 1 ∣ P m z^{m+1}\mid P_m z m + 1 ∣ P m makes (A.3) coefficientwise convergent.
The first four summands are
R 0 ( z ) = z 1 − z , R 1 ( z ) = z 2 + z 3 − z 4 ( 1 − z ) 2 , R 2 ( z ) = 2 z 3 + 4 z 4 − 7 z 5 + z 6 + z 7 ( 1 − z ) 3 , R 3 ( z ) = 6 z 4 + 12 z 5 − 34 z 6 + 11 z 7 + 11 z 8 − 4 z 9 − z 10 ( 1 − z ) 4 . \begin{aligned}
R_0(z) &= \frac{z}{1-z}, \\
R_1(z) &= \frac{z^2+z^3-z^4}{(1-z)^2}, \\
R_2(z) &= \frac{2z^3+4z^4-7z^5+z^6+z^7}{(1-z)^3}, \\
R_3(z) &= \frac{6z^4+12z^5-34z^6+11z^7+11z^8-4z^9-z^{10}}{(1-z)^4}.
\end{aligned} R 0 ( z ) R 1 ( z ) R 2 ( z ) R 3 ( z ) = 1 − z z , = ( 1 − z ) 2 z 2 + z 3 − z 4 , = ( 1 − z ) 3 2 z 3 + 4 z 4 − 7 z 5 + z 6 + z 7 , = ( 1 − z ) 4 6 z 4 + 12 z 5 − 34 z 6 + 11 z 7 + 11 z 8 − 4 z 9 − z 10 .
This is an all-length rational expansion for G C G_C G C , with a finite definition of every numerator. Section 6 gives a Lambert series expression for the same generating function.
Finite checks and reproducibility record
The finite checks below are supporting evidence for the displayed formulas; the all-length conclusions follow from the proofs in the main text. The recurrence in Proposition 1 , an independent implementation of the four-type B B B tree, and a literal site-word implementation reproduce the Class 207 counts through length 12:
Table 1.
Literal pattern checks through length 8 verify the initial counts for both Class 152 sets and both Class 207 sets, and verify every legal-site transition in that range. The same enumeration checks the first four fixed-maximum rational functions through length 8. Exact-integer expansion of the two product orbits gives a zero residual for the summation identity through internal order 136 (hence through degree 129 after the stated normalization), and the common Lambert formula agrees with the C C C recurrence and the four-type B B B tree through length 128. These checks are independent of, and are not premises for, Theorem 1.
The checks are implemented in Python [23 ] ; exact symbolic certificates use SymPy [19 ] , and an optional numerical audit uses mpmath [20 ] . The complete recurrence program, independent generators, literal checker, exact symbolic certificates, fixed-maximum expansion, and refined analytic arguments are in the supplementary material. Its README records the finite ranges, software versions, commands, and expected outputs.