Generating functions for permutations which avoid consecutive patterns with multiple descents
Quang T. Bach Jeffrey B. Remmel


Tensor Balancing on Statistical Manifold
    
  Mahito Sugiyama 

  National Institute of Informatics 

  JST, PRESTO 

   

  Hiroyuki Nakahara 

  RIKEN Brain Science Institute 

   

  Koji Tsuda 

  The University of Tokyo 

  RIKEN AIP; NIMS 

   


    December 30, 2023
=====================================================================================================================================================================================================================









§ INTRODUCTION



Let S_n denote the group all permutations of n. That is,
S_n is the set of all one-to-one maps :{1, …, n}→{1, …, n} under composition.  If = _1 …_n ∈ S_n, 
then we let Des() = {i: _i >_i+1} and 
() =|Des()|. We say that _j is 
left-to-right minima of  if _i > _j for all i < j. 
For example the left-to-right minima of σ=938471625 are 
9, 3 and 1. 
Given a sequence τ = τ_1 ⋯τ_n of distinct positive integers,
we define the reduction of τ, (τ), to be the permutation 
of S_n that results by replacing the i-th smallest element 
of τ by i. For example 
(53962) = 32541. If Γ is a set of permutations, 
we say that a permutation = _1 …_n ∈ S_n has 
a Γ-match starting at position i if there is a i < j such 
that (_i _i+1…_j) ∈Γ. 
We let () denote the number of Γ-matches in .
We let 𝒩ℳ_n(Γ) be the set of ∈ S_n such 
that () =0. 

The main goal of this paper is to study generating functions 
of the form 

    _Γ(t,x,y)=∑_n ≥ 0t^n/n!_Γ,n(x,y)

where _Γ,n(x,y) =∑_∈𝒩ℳ_n(Γ)x^y^1+().  
In the special case where Γ = {τ} is a set with a 
single permutation τ, we shall write () for 
(), _τ(t,x,y) for _Γ(t,x,y),  
and  _τ,n(x,y) for _Γ,n(x,y). 


 

There is a considerable literature on the 
generating function _Γ(t,1,1) of 
permutations that consecutively avoid a pattern 
or set of patterns. See for example, <cit.>. For the most part, these papers do not  
consider generating functions of the form 
τ(t,1,y) or τ(t,x,y). An exception 
is the work on enumeration schemes of Baxter <cit.> who gave 
general methods to enumerate pattern avoiding vincular patterns according 
to various permutations statistics. Our approach is 
to use the reciprocity method of Jones and Remmel. 


Jones and Remmel <cit.> 
developed what they called the reciprocity method 
to compute the generating function 
τ(t,x,y) for certain families of 
permutations τ such that τ starts with 
1 and (τ) =1. 





The basic idea of their approach 
is as follows. First it follows from results in <cit.> that if 
all the permutations in Γ start with 1, then we 
can write _Γ(t,x,y) in the form 

    _Γ(t,x,y) = ( 1/U_Γ(t,y))^x

 where U_Γ(t,y) = ∑_n≥ 0U_Γ,n(y) t^n/n!.  
Next one writes 

    U_τ(t,y) = 
    1/1+∑_n ≥ 1_τ,n(1,y) t^n/n!.
 One can then use the homomorphism method 
to give a combinatorial   
interpretation of the right-hand side of (<ref>) which can 
be used to find simple recursions for  
the coefficients U_τ,n(y). 
The homomorphism method derives generating functions for 
various permutation statistics by 
applying a ring homomorphism defined on the 
ring of symmetric functions Λ  
in infinitely many variables x_1,x_2, … 
to simple symmetric function identities such as 

    H(t) = 1/E(-t)

where H(t) and E(t) are the generating functions for the homogeneous and elementary 
symmetric functions, respectively. That is, 

    H(t) = ∑_n≥ 0 h_n t^n = ∏_i≥ 11/1-x_it  E(t) = ∑_n≥ 0 e_n t^n = ∏_i≥ 1 1+x_it.

In their case, Jones and Remmel
 defined a homomorphism θ_τ on 
Λ by setting 
θ_τ(e_n) = (-1)^n/n! _τ,n(1,y).
Then 
θ_τ(E(-t)) = ∑_n≥0 _τ,n(1,y) t^n/n! = 1/U_τ(t,y).
Hence 

    U_τ(t,y) = 1/θ_τ(E(-t)) = θ_τ(H(t))

which implies that 

    n!θ_τ(h_n) = U_τ,n(y).

Thus if we can compute n!θ_τ(h_n) for all n ≥ 1, then we can 
compute the polynomials U_τ,n(y) and the generating function 
U_τ(t,y), which in turn allows us to compute 
the generating function _τ(t,x,y). 
Jones and Remmel <cit.> showed that one can interpret 
n!θ_τ(h_n) as a certain signed sum of weights of filled labeled brick tabloids when τ starts with 1 
and (τ)=1. They then defined a weight-preserving sign-reversing 
involution I on the set of such filled labeled brick tabloids which 
allowed them to give a relatively simple combinatorial interpretation 
for n!θ_τ(n_n). They also showed how such a  
combinatorial interpretation allowed them to prove  
that the polynomials U_τ,n(y) satisfy simple recursions
for certain families of such permutations τ. 

For example, in <cit.>, Jones and Remmel  studied  the generating functions _τ(t,x,y) for permutations τ of the form τ = 1324⋯ p where p ≥ 4.  Using the reciprocity method, they proved that U_1324,1(y)=-y and for n ≥ 2, 

    U_1324,n(y) = (1-y)U_1324,n-1(y)+ ∑_k=2^⌊ n/2 ⌋ 
    (-y)^k-1 C_k-1 U_1324,n-2k+1(y)
 where C_k = 1/k+12kk is the k-th Catalan number. They also proved that for  any p ≥ 5,  U_1324 ⋯ p,n(y) =-y and for n ≥ 2, 

    U_1324⋯ p,n(y)=(1-y)U_1324⋯ p,n-1(y)+∑_k=2^⌊n-2/p-2⌋+1(-y)^k-1U_1324⋯ p,n-((k-1)(p-2)+1)(y).



Bach and Remmel <cit.> extended this reciprocity method to 
study the polynomials 
U_Γ,n(y) in the case where Γ is a set of permutations 
such that for all τ∈Γ, τ starts with 1 and 
(τ) ≤ 1. For example, 
suppose that k_1, k_2 ≥ 2, p = k_1 + k_2, 
and  

    Γ_k_1,k_2 = {σ∈ S_p: σ_1=1, σ_k_1+1=2, σ_1 < σ_2< ⋯<σ_k_1 & σ_k_1+1 < σ_k_1+2< ⋯<σ_p}.
 
That is, Γ_k_1,k_2 consists of all permutations  of length p where 1 is in position 1, 2 is in position k_1+1, and  consists of two increasing sequences, one starting at 1 and the other starting at 2. In <cit.>, 
we proved that for Γ = Γ_k_1,k_2, 
U_Γ,1(y)=-y, and for n ≥ 2,

    U_Γ,n(y)    = (1-y)U_Γ,n-1(y) -yn-2k_1-1( U_Γ,n-M(y) +y∑_i=1^m-1U_Γ,n-M-i(y) )
 where m = min{k_1, k_2}, and M = max{k_1,k_2}. 

Furthermore, in <cit.>, we investigated a new phenomenon that arises when we add the identity permutation 12 … k to the family Γ. 
 For example, if Γ = {1324,123}, then we proved 
that  U_Γ,1(y)=-y, and for n ≥ 2,

    U_Γ,n(y) = -yU_Γ,n-1(y) -yU_Γ,n-2(y)
    + ∑_k=2^(-y)^kC_k-1U_Γ, n-2k(y).
 
When Γ = {1324… p,123… p-1} where p ≥ 5, then 
we proved that U_Γ,1(y)=-y, and for n ≥ 2,

    U_Γ,n(y) = ∑_k=1^p-2(-y)U_Γ,n-k(y) + ∑_k=1^p-2∑_m=2^⌊n-k/p-2⌋(-y)^mU_Γ, n-k-(m-1)(p-2)(y).
 
While on the surface, 
the recursions (<ref>) and (<ref>) do not 
seem to be simpler than the corresponding recursions 
(<ref>) and (<ref>), they are easier to analyze because 
adding an identity permutation 12 … k to Γ ensures 
that all the bricks in the filled brick tabloids used to interpret 
n!θ_τ(h_n) have length less than k. For 
example, we were able to prove the following explicit formula 
for the polynomials U_{1324,123},n(y). 

 
Let Γ = {1324,123}. Then for all 
n ≥ 0, 

    U_Γ,2n(y) = 
    ∑_k=0^n (2k+1)2nn-k/n+k+1(-y)^n+k+1

and 

    U_Γ,2n+1(y) = 
    ∑_k=0^n 2(k+1)2n+1n-k/n+k+2(-y)^n+k.



Another example in <cit.> where we could find 
an explicit formula is the following. Let Γ_k_1,k_2,s = Γ_k_1,k_2∪{1 ⋯ s(s+1)} for some s ≥max(k_1,k_2). Bach and Remmel showed that U_Γ_2,2,s,1(y)=-y, and for n ≥ 2,

    U_Γ_2,2,s,n(y)   = -yU_Γ_2,2,s,n-1(y) - 
          ∑_k=0^s-2((n-k-1) yU_Γ_2,2,s,n-k-2(y)+(n-k-2)
    y^2 U_Γ_2,2,s,n-k-3(y)).
 
Using these recursions, we proved that 

    U_Γ_2,2,2,2n(y) =    ∑_i=0^n (2n-1)↓↓_n-i (-y)^n+i 
    
    U_Γ_2,2,2,2n+1(y) =   ∑_i=0^n (2n) ↓↓_n-i (-y)^n+1+i
 where for any x, (x)↓↓_0 =1 and (x)↓↓_k =x(x-2)(x-4) ⋯ (x-2k -2) for k ≥ 1. 



The two assumptions on Γ that allow the reciprocity  
method to work are that (A) all τ in Γ start with 
1 and (B) all τ in Γ have at most 
one descent. First, assumption (A) ensures that we 
can write _Γ(x,y,t) in the form (<ref>). 
Second, assumption (B) ensures that the involution I used to 
simplify the weighted sum over all filled, labeled brick tabloids 
that equals n!θ_τ(h_n) is actually an involution and to 
ensure that the elements in any brick of a filled, labeled 
brick tabloids which is a fixed point of I 
must be increasing. Finally, (A) is used again to ensure that the minimal 
elements in bricks of any fixed point of I are 
increasing when read from left to right.



The main goal of this paper is to study how we can 
apply the reciprocity method in the case 
where we no longer insist that all the 
τ∈Γ have at most one descent. We shall 
show  that we can modify the definition of the involution  
used by Jones and Remmel <cit.> and Bach and Remmel <cit.> 
to simplify the weighted sum over all filled, labeled brick tabloids 
that equals n!θ_τ(h_n).  However, the set of fixed points 
in such cases will be more complicated than 
in the case where Γ contains only permutations 
with at most one descent in that it will no longer be the 
case that for fixed points of the involution, 
the fillings will be increasing in bricks and 
the minimal elements of the brick increase, reading from left 
to right.  Nevertheless, we shall show that there 
still are a number of 
cases where we can successfully analyze the fixed points 
to prove that the polynomials U_Γ,n(y) satisfy some simple recursions. 




In this paper, we shall prove three main theorems. 
That is, we will compute the generating functions 
_Γ(t,x,y) when 
Γ = {14253,15243}, Γ = {142536}, 
and when Γ = {τ_a} for any 
a ≥ 2 where τ_a ∈ S_2a is 
the permutation such that 
τ_1 τ_3 …τ_2a-1 = 12 … a and 
τ_2 τ_4 …τ_2a= (2a) (2a-1) … (a+1). 
In each case, the permutations have at least two descents.  
In <cit.>. we studied the generating functions of the form 
_τ(t,x,y) where τ is a minimal overlapping 
permutation that starts with 1.  Here τ∈ S_j is a minimal 
overlapping permutation if the smallest j such that 
there exists an ∈ S_n such that () =2 is 2j-1. 
This means that any two consecutive τ-matches can share 
at most one letter. When τ is a minimally 
overlapping permutations, the recursions for U_τ,n(y) are generally much 
simpler than the ones considered in this paper because in each case 
we are dealing with permutations which are not minimally overlapping. 


The main results of this paper are the following theorems. 

 
Let Γ = {14253,15243}. Then 

    _Γ(t,x,y)=(1/U_Γ(t,y))^x  where U_Γ(t,y)=1+∑_n≥1U_Γ,n(y)t^n/n!,
 with U_Γ,1(y)=-y, and for n ≥ 2,

    U_Γ,n(y)     = (1-y)U_Γ,n-1(y)  -y^2(n-3)(U_Γ, n-4(y) +(1-y)(n-5)U_Γ, n-5(y)  )
                            -y^3(n-3)(n-5)(n-6)U_Γ,n-6(y).

 

Let C_n = 1/n+12nn be the n-th Catalan number. 
Let M_n be the n× n matrix whose elements on 
the main diagonal equals C_2, whose elements on j-th diagonal above 
the main diagonal are C_3j+2, whose elements on the sub-diagonal 
are -1, and whose elements in diagonal below the sub-diagonal are 0. 
Thus, 

    M_k = 
    C_2     C_5     C_8     C_11   ⋯    C_3k-4    C_3k-1
     
    -1     C_2     C_5     C_8    ⋯    C_3k-7    C_3k-4
     
    0     -1     C_2     C_5    ⋯    C_3k-10    C_3k-7
     
    0     0     -1     C_2    ⋯    C_3k-13    C_3k-10
    ⋮   ⋮   ⋮   ⋮      ⋮   ⋮
     
    0     0     0     0    ⋯    C_2     C_5 
     
    0     0     0     0    ⋯    -1     C_2
    .

Let P_k be the matrix obtained from M_k by replacing each 
C_m in the last column by C_m-1. Thus, 

    P_k = 
    C_2     C_5     C_8     C_11   ⋯    C_3k-4    C_3k-2
     
    -1     C_2     C_5     C_8    ⋯    C_3k-7    C_3k-5
     
    0     -1     C_2     C_5    ⋯    C_3k-10    C_3k-8
     
    0     0     -1     C_2    ⋯    C_3k-13    C_3k-11
    ⋮   ⋮   ⋮   ⋮      ⋮   ⋮
     
    0     0     0     0    ⋯    C_2     C_4 
     
    0     0     0     0    ⋯    -1     C_1
    .






 
Let τ = 142536. Then 

    _τ(t,x,y)=(1/U_τ(t,y))^x  where U_τ(t,y)=1+∑_n≥1U_τ,n(y)t^n/n!,
 with U_τ,1(y)=-y, and for n ≥ 2,

    U_τ,n(y) =         (1-y)U_Γ,n-1(y) +  ∑_k=0^[(n-8)/6]det(M_k+1) y^3k+3U_n-6k-7(y) 
                + ∑_k=0^[n-6/6]det(P_k+1)(-y^3k+2)
    [U_τ,n-6k-4(y) +yU_τ,n-6k-5(y) ].







 
For any n ≥ 2, let τ=τ_1 …τ_2a∈ S_2a where 
τ_1 τ_3 …τ_2a-1 = 123 … a and τ_2τ_4 …τ_2a = (2a) (2a-1) … (a+1).
Then 

    _τ(t,x,y)=(1/U_τ(t,y))^x  where U_τ(t,y)=1+∑_n≥1U_τ,n(y)t^n/n!,
 with U_τ,1(y)=-y, and for n ≥ 2,

    U_τ,n(y)  =       (1-y)U_τ,n-1(y)  - 
    ∑_k=0^⌊ (n-2a)/(2a)⌋n-(k+1)a-1(k+1)a-1 y^(k+1)a-1
    U_τ_a,n-(2(k+1)a)+1(y) 
              +∑_k=0^⌊ (n-2a-2)/(2a)⌋n-(k+1)a-2(k+1)a 
    y^(k+1)a U_τ_a,n-(2(k+1)a)-1(y).





We note that our results allows us to compute _τ(t,x,y) in two cases where  
τ = τ_1 …τ_6 and 
τ_1 =1, τ_3 =2, and τ_5 =3.  Namely, the case where 
τ = 162534 is consider in Theorem <ref> and the 
the case where τ = 142536 is a special case of 
Theorem <ref>.  All such 
permutations have (τ) =2. In fact, the first author in his thesis 
has computed 
_τ(t,x,y) in the other 4 cases where  τ = τ_1 …τ_6 and 
τ_1 =1, τ_3 =2, and τ_5 =3 which we will not present 
here due to lack of space.  






The outline of this paper is the following. In Section <ref>, 
we shall provide the necessary background on symmetric functions 
for our applications. In section <ref>, 
we shall recall the basic reciprocity method of 
<cit.> and <cit.> in the case 
where the permutations of Γ are allowed to have more than 
one descent.  In Section <ref>, we shall prove Theorem <ref>. In Section <ref>, 
we shall prove Theorem <ref>. Finally, in Section 
<ref>, we shall prove Theorem <ref>. 





§ SYMMETRIC FUNCTIONS



In this section, we give the necessary background on 
symmetric functions that will be used in our proofs. 


A partition of n is a sequence of positive integers 
= (_1, …,_s) such that 
0 < _1 ≤⋯≤_s and n=_1+ ⋯ +_s. We shall write λ⊢ n to denote that λ is 
partition of n and we let ℓ(λ) denote the number of parts 
of λ. When a partition of n involves repeated parts, 
we shall often use exponents in the partition notation to indicate 
these repeated parts. For example, we will write 
(1^2,4^5) for the partition (1,1,4,4,4,4,4). 



Let Λ denote the ring of symmetric functions in infinitely  
many variables x_1,x_2, …. The  elementary symmetric function e_n = e_n(x_1,x_2, …)  and  homogeneous 
 symmetric function h_n = h_n(x_1,x_2, …) are defined by the generating functions given in (<ref>). 
For any partition = (_1,…,_ℓ), let e_= e__1 
⋯e__ℓ and h_= h__1 
⋯h__ℓ.  It is well known that e_0,e_1, … is 
an algebraically independent set of generators for , and hence, 
a ring homomorphism θ on Λ can be defined  
by simply specifying θ(e_n) for all n. 


If λ =(λ_1, …, λ_k) is a partition of n, 
then a λ-brick tabloid of shape (n) is a filling 
of a rectangle consisting of n cells with bricks of sizes 
λ_1, …, λ_k in such a way that no 
two bricks overlap. For example, Figure 
<ref> shows the six (1^2,2^2)-brick tabloids of 
shape (6). 




DIMfig1The six (1^2,2^2)-brick tabloids of shape (6).


Let ℬ_,n denote the set of -brick tabloids 
of shape (n) and let B_,n be the number of -brick 
tabloids of shape (n).  If B ∈ℬ_,n, we 
will write B =(b_1, …, b_ℓ()) if the lengths of 
the bricks in B, reading from left to right, are 
b_1, …, b_ℓ(). For example, the brick 
tabloid in the top right position in Figure <ref> is 
denoted as (2,1,1,2). 
Eğecioğlu and the second author  <cit.> proved that 

    h_n = ∑_⊢ n (-1)^n - ℓ() B_,n  e_.

This interpretation of the expansion of 
h_n in terms of the e_λs will aid us in describing the coefficients of θ_Γ(H(t))=_Γ(t,y) described 
in the next section, 
which will in turn allow us to compute the coefficients 
_Γ,n(t,x,y).





§ EXTENDING THE RECIPROCITY METHOD
 


Let Γ be the set of permutations that all start with 1 and 
there is a k ≥ 1 such that all ∈Γ have 
() ≤ k and there is at least one τ∈Γ 
such that (τ) =k. We want to give a combinatorial interpretation to 
    U_Γ(t,y)=1/_Γ(t,1,y)  = 1/1+ ∑_n ≥ 1t^n/n!_Γ,n(1,y)

where 

    _Γ,n(1,y) = ∑_∈𝒩ℳ_n(Γ) y^1+().
 

We define a ring homomorphism θ_Γ on the ring of symmetric functions Λ by setting θ_Γ(e_0) = 1 and, for n ≥ 1, 
    θ_Γ(e_n) = (-1)^n/n!_Γ,n(1,y).

It then follows that 

    θ_Γ(H(t))    =   ∑_n ≥ 0θ_Γ(h_n)t^n  = 1/θ_τ(E(-t)) = 1/1 + ∑_n ≥ 1 (-t)^n θ_Γ(e_n)
       =   1/1 + ∑_n ≥ 1t^n/n!_Γ,n(1,y) = 
    U_Γ(t,y).



Thus U_Γ,n(y) = n! θ_Γ(h_n).  
Using (<ref>), we can compute 
    n! θ_Γ(h_n)    =    n! ∑_⊢ n (-1)^n-ℓ() 
    B_,n θ_Γ(e_) 
       =    n! ∑_⊢ n (-1)^n-ℓ()∑_(b_1, …, 
    b_ℓ()) ∈ℬ_,n∏_i=1^ℓ()(-1)^b_i/b_i!_Γ,b_i(1,y) 
       =   ∑_⊢ n (-1)^ℓ()∑_(b_1, …, b_ℓ()) ∈ℬ_,nnb_1, …, b_ℓ()∏_i=1^ℓ()_Γ,b_i(1,y).


To give combinatorial interpretation to the right hand side of (<ref>), we select a brick tabloid B = (b_1, b_2, …, b_ℓ() ) of shape (n) filled with bricks whose sizes induce the partition . We interpret the multinomial coefficient nb_1, …, b_ℓ() as the number of ways to choose an ordered set partition 𝒮 =(S_1, S_2, …, S_ℓ()) of {1,2, …, n} such that |S_i| = b_i, for i = 1, …, ℓ(). For each brick b_i, we then fill the cells of b_i with numbers from S_i such that the entries in the brick reduce to a permutation ^(i) = _1 ⋯_b_i in 𝒩ℳ_b_i(Γ). We label each descent of  that occurs within each brick as well as the last cell of each brick by y.  This accounts for the factor y^(^(i))+1 within each brick. Finally, we use the factor (-1)^ℓ() to change the label of the last cell of each brick from y to -y. We will denote the filled labeled brick tabloid constructed in this way as ⟨ B,𝒮,(^(1), …, ^(ℓ()))⟩. 

For example, when n = 17, Γ = {1324, 1423, 12345}, and 
B = (9,3,5,2), consider the ordered set partition 𝒮=(S_1,S_2,S_3,S_4) of {1,2,…, 17} where S_1={2,5,6,9,11,15,16,17,19}, S_2 = {7,8,14}, S_3 = {1,3,10,13,18}, S_4 = {4,12} and the permutations 
^(1) = 1 2 4 6 5 3 7 9 8 ∈𝒩ℳ_9(Γ), ^(2) = 1 3 2 ∈𝒩ℳ_7(Γ), ^(3) = 5 1 2 4 3 ∈𝒩ℳ_5(Γ), and ^(4) = 2 1 ∈𝒩ℳ_2(Γ).  
Then the construction of 
⟨ B,𝒮,(^(1), …, ^(4))⟩ is 
pictured in Figure <ref>.









It is easy to see that we can recover 
the triple ⟨ B, (S_1, …, S_ℓ()), (^(1), …,^(ℓ())  ) ⟩ from B and the permutation 
 which is obtained by reading the entries in the 
cells from right to left.  We let 𝒪_Γ, n denote the set of all filled labeled brick tabloids created this way. That is, 𝒪_Γ, n consists of all pairs O = (B,  ) where 


  * B = (b_1, b_2, …, b_ℓ()) is a brick tabloid of shape n,  

  * = _1  ⋯_n is a permutation in S_n such that there is no Γ-match of  which 
lies entirely in a single brick of B, and 

  * if there is a cell c such that a brick b_i contains both cells c and c+1 and _c > _c+1, then cell c is labeled with a y and the last cell of any brick is labeled with -y.


We define the sign of each O to be sgn(O) = (-1)^ℓ(). The weight W(O) of O is defined to be the product of all the labels y used in the brick. For example, 
the labeled brick tabloid pictured  Figure <ref> has 
W(O) = y^11 and sgn(O) =(-1)^4 =1. It follows that 

    n!θ_Γ(h_n) = ∑_O ∈𝒪_Γ,n sgn(O) W(O).
  



Next we define a sign-reversing, weight-preserving mapping J_Γ: 𝒪_Γ, n→𝒪_Γ, n as 
follows.  Let (B,) ∈𝒪_Γ, n where 
B=(b_1, …, b_k) and = _1 …_n. 
Then for any i, we let 
(b_i) be the element in the left-most cell of b_i and 
(b_i) be the element in the right-most cell of b_i.
Then we read the cells of (B,) from left to right, looking for the first cell c such that either 

 

Case I.  cell c is labeled with a y in some brick b_j and 
either (a) j=1 or (b) j > 1 and either 
(b.1) (b_j-1) < (b_j) or  (b.2) 
 (b_j-1) > (b_j) and there 
is τ-match contained in the cells of b_j-1 and 
the cells b_j that end weakly to the left of cell c for 
some τ∈Γ or 
 
 

Case II. cell c is at the end of brick b_i where _c > _c+1 and there is no Γ-match of  that lies entirely in the cells of the bricks b_i and b_i+1.
 
  


In Case I, we define J_Γ((B,)) to be the filled labeled brick tabloid obtained from (B,) by breaking the brick b_j that contains cell c into two bricks b_j' and b_j” where b_j' contains the cells of b_j up to and including the cell c while b_j” contains the remaining cells of b_j. In addition, we change the label of cell c from y to -y. In Case II, 
J_Γ((B,)) is obtained by combining the two 
bricks b_i and b_i+1 
into a single brick b and changing the label of cell c from -y to y. If neither case occurs, then we let J_Γ((B,)) = (B,). 





For example, suppose Γ = {τ} where τ =14253 and 
(B,) ∈𝒪_Γ,18 pictured at 
the top of Figure <ref>. 
We cannot use cell c=4 to define J_Γ(B,), 
because if we combined bricks b_1 and b_2, 
then (9 15 11 16 13) = τ would be a τ-match 
contained in the resulting brick.  Similarly, 
we cannot use  cell c=6 to apply the involution because it fails to meet 
condition (b.2). In fact the first c for which either Case I or 
Case II applies is cell c=8 so that J_Γ(B,) is 
equal to the (B',) pictured on the bottom of 
Figure <ref>.

We now prove that J_Γ is an involution by showing J_Γ^2 is the identity mapping. Let (B,) ∈𝒪_Γ,n where B=(b_1, …, b_k) and = _1 …_n. The key observation here is that applying the mapping J_Γ to a brick in Case I will produce one in Case II, and vice versa. 

Suppose the filled, labeled brick tabloid (B,) is in Case I and its image J_Γ((B,)) is obtained  by splitting some brick b_j after cell c into two bricks b_j' and b_j”.  There are now two possibilities. 


  (a) c is in the first brick b_1. In this case, c must be the first cell which is labeled with y so that the elements in b_1' will be increasing. Furthermore, since we are assuming there is no Γ-match in the cells of brick b_1 in (B,), there cannot be any Γ-match that involves the cells of bricks b_1' and b_1” in J_Γ((B,)). Hence, when we consider J_Γ((B,)), the first possible cell where we can apply J_Γ will be cell c because we can now combine b_1' and b_1”.  Thus, 
when we apply J_Γ to J_Γ((B,)), we will be 
in Case II using cell c so that we will recombine bricks b_1' and b_1” into b_1 and replace the label of -y on cell c by y. Hence J_Γ(J_Γ((B,))) =(B,) in this case. 


  (b) c is in brick b_j, where j > 1. Note that our definition of when a cell labeled y can be used in Case I to define J_Γ depends only on the cells and the brick structure to the left of that cell. Hence, we can not use any of the cells labeled y to the left of c to define J_Γ(J_Γ((B,))). Similarly, if we have two bricks b_s and b_s+1 which lie entirely to the left of cell c such that (b_s) = _d > (b_s+1) =_d+1, the criteria to use cell d in the definition of J_Γ on J_Γ((B,)) depends only on the elements in bricks b_s and b_s+1. Thus, the only cell d which we could possibly use to define J_Γ on J_Γ((B,)) that lies to the left of c is the last cell of b_j-1. However, our conditions that either (b_j-1) < (b_j) = (b_j') or  (b_j-1) > (b_j) = (b_j') with a Γ-match contained in the cells of b_j-1 and b_j' force the first cell that can be used to define J_Γ on J_Γ((B,)) to be cell c. Thus, when we  apply J_Γ to J_Γ((B,)), we will be in Case II using cell c and we will recombine bricks b_j' and b_j” into b_j and replace the label of -y on cell c by y. Thus J_Γ(J_Γ((B,))) =(B,) in this case. 


Suppose (B,) is in Case II and we define J_Γ((B,)) at cell c, where c is last cell of b_j and _c > _c+1. Then by the same arguments that we used in Case I, there can be no cell labeled y to the left of this cell c in either (B,) or J(B,) which 
can be used to define the involution J_Γ. This follows from the fact that the brick structure before cell c is unchanged between (B,) and J(B,). Similarly, there can be no two bricks that lie entirely to the left of cell c in J_Γ((B,)) that can be combined under J_Γ. Thus, the first cell that we can use to define J_Γ to J_Γ((B,)) is cell c and it is easy to check that it satisfies the conditions of Case I.  Thus, when we apply J_Γ to J_Γ((B,)), 
we will be in Case I using cell c and  we will combine bricks b_j and b_j+1 into a single brick b and replaced the label on cell c by y. Then it is easy to see that when applying J_Γ to J_Γ((B,)), we will split b back into bricks b_j and b_j+1 and change the label on cell c back to -y. Thus  J_Γ(J_Γ((B,))) =(B,) in this case.


Hence J_Γ is an involution. It is clear that if J_Γ(B,) ≠ (B,),  then sgn(B,)W(B,) = -sgn(J_Γ(B,))W(J_Γ(B,)). Thus, it follows from (<ref>) that 

    U_Γ,n(y) = n!θ_Γ(h_n) =  ∑_O ∈𝒪_Γ,nO W(O) = ∑_O ∈𝒪_Γ,n, J_Γ(O) =OO W(O).

Thus, to compute U_Γ,n(y), we must analyze the fixed points of J_Γ. Our next lemma characterizes the fixed points of J_Γ. 










  Let B=(b_1, …, b_k) be 
a brick tabloid of shape (n) and = _1 …_n ∈ S_n. 
Then (B,) is a fixed point of J_Γ if and only if it satisfies the following properties: 


  (a) if i=1 or i > 1 and (b_i-1) < (b_i), then b_i can have no cell labeled y so that  must be increasing in b_i, 


  (b) if i > 1 and _e = (b_i-1) > (b_i)=_e+1, then there must be a Γ-match contained in the cells of b_i-1 and b_i which must necessarily involve _e and _e+1 and there can be at most k-1 cells labeled y in b_i, and 




  (c) if Γ has the property that, for all τ∈Γ such that (τ) = j ≥ 1, the bottom elements [If  is a permutation with _i > _i+1, i.e. there is a descent in  at position i, then we shall refer to _i+1 as the bottom element of this descent.] of the descents in τ are 2, …, j+1,  when reading from left to right, 
then 

    first(b_1) < first(b_2) < ⋯ < first(b_k).
 




 Suppose (B,) is a fixed point of J_Γ. Then it must be the case that in (B,), there is no cell c to which either 
Case I or Case II applies. That is, when attempting to apply the involution J_Γ to (B,), we cannot split any brick at a cell labeled y  and 
we cannot combine two consecutive bricks where the last cell of 
the first brick is larger than the first cell of the second brick. 




For (a), note that if there is a cell labeled y in b_i and  c is the left-most cell of b_i labeled with y, then c satisfies the conditions of Case I. Thus, there can be no cell labeled y in b_i. 


For (b), note that if there is no Γ-match contained in the cells of b_i-1 and b_i, then e satisfies the conditions of Case II.  Thus, there must be a Γ-match contained in the cells of b_i-1 and b_i. If there are k or more cells labeled y in b_i, then let c be the k^th cell, reading from left to right, which is labeled with y. Then we know there is τ-match contained in the cells of b_i-1 and b_i which must necessarily involve _e and _e+1 for some τ∈Γ. But this τ-match must end weakly before cell c since otherwise τ would have at least k+1 descents. Thus c would satisfy the conditions to apply Case I of our 
involution. Hence there can be no such c which means that 
each such brick can contain at most k-1 descents. 






To prove (c), suppose for a contradiction that 
there exist two consecutive bricks b_i and b_i+1 
such that _e = first(b_i) > first(b_i+1) =_f. There are two cases. 

 

Case A.   is increasing in b_i. 

Then _f-1 = last(b_i).  If _f-1 < _f, then we know that _e ≤_f-1 < _f which contradicts our choice of _e and _f. Thus it must be the case that _f-1 > _f.  But then there is τ∈Γ such that (τ) =j ≥ 1 and there is a τ-match in the cells of b_i and b_i+1 involving the _f-1 and _f. By our assumptions, _f can only play the role of 2 in such a τ-match. Hence there must be some _g with e ≤ g ≤ f-2 which plays the role of 1 in this τ-match. But then we would have _e ≤_g  < _f which contradicts our choice of _e and _f. Thus  cannot be increasing in b_i. 

 

Case B.  is not increasing in b_i. 

In this case, by part (a), we know that it must be the case that _e-1 = (b_i-1) > _e = (b_i) and, by (b), there is τ∈Γ such that (τ) =j ≥ 1 and there is a τ-match in the cells of b_i-1 and b_i involving the cells _e-1 and _e. Call this τ-match α and suppose that cell h is the bottom element of the last descent in α. It cannot be that _e =_h.  That is, there can be no cell labeled y that occurs after cell h in b_i since otherwise the left-most such cell c would satisfy the conditions of Case I of the definition of J_Γ. But this would mean that  is increasing in b_i starting at _h so that if _e =_h, then  would be increasing in b_i which contradicts our assumption in this case. Thus there is some 2 ≤ i ≤ j such that _e plays the role of i in the τ-match α and _h plays the role of j+1 in the τ-match α. But this means that _e is the smallest element in brick b_i. That is, let _c be the smallest element in  b_i. If _e ≠_c, then _c must be the bottom of some descent in b_i which implies that c ≤ h. But then _c is part of the τ-match α which means that _c must be playing the role of one of i+1, …, j+1 in the τ-match α and _e is playing the role of i in the τ-match α which is impossible if _e ≠_c. It follows that _e ≤_f-1. Hence, it can not be that case that _f-1 < _f since otherwise _e < _f. Thus it must be the case that _f-1 > _f. But this means that there exists some δ∈Γ such that (δ) =p ≥ 1 and there is a δ-match in the cells of b_i and b_i+1 involving the _f-1 and _f.  Call this δ-match β. By assumption, the bottom elements of the descents in δ are 2,3, …, p+1 so that _f must be playing the role of 2,3, … ,p+1 in the δ-match β. Let _g be the element that plays the role of 1 in the δ-match β. _g must be in b_i since δ must start with 1. But then we would have that _e ≤_g < _f since _e is the smallest element in b_i. 


Thus, both Case A and Case B are impossible. 
Hence we must have that 

    first(b_1) < first(b_2) < ⋯ < first(b_k).
  



We note that if condition (3) of the Lemma fails, 
it may be that the first elements 
of the bricks do not form an increasing sequence.
For  example, it is easy to check that if Γ = {15342}, 
then the (B,) pictured in Figure <ref> is 
such a fixed point of J_Γ. 









§ THE PROOF OF THEOREM <REF>  



In this section, we shall prove Theorem <ref> which is the simplest case 
of our three examples. For convenience, 
we first restate the statement of Theorem <ref>.

 
Let Γ = {14253,15243}. Then 

    _Γ(t,x,y)=(1/U_Γ(t,y))^x  where U_Γ(t,y)=1+∑_n≥1U_Γ,n(y)t^n/n!,
 with U_Γ,1(y)=-y, and for n ≥ 2,

    U_Γ,n(y)     = (1-y)U_Γ,n-1(y)  -y^2(n-3)(U_Γ, n-4(y) +(1-y)(n-5)U_Γ, n-5(y)  )
                            -y^3(n-3)(n-5)(n-6)U_Γ,n-6(y).




Proof. Let Γ = {14253,15243}, we need to show that the polynomials 
    U_Γ,n (y) = ∑_O ∈𝒪_Γ,n, J_Γ(O) =OO W(O)
 satisfy the following properties: 

  * U_τ,1(y)=-y, and 

  * for n ≥ 2, 
    U_Γ,n(y)     = (1-y)U_Γ,n-1(y)  -y^2(n-3)(U_Γ, n-4(y) +(1-y)(n-5)U_Γ, n-5(y)  )
                            -y^3(n-3)(n-5)(n-6)U_Γ,n-6(y).
 
  

It is easy to see when n=1, the only fixed point comes from 
brick tabloid that has a single brick of size 1 which contains 1 and 
the label on cell 1 is -y. Thus 
U_τ,1(y)=-y.

For n ≥ 2, let O=(B,) be a fixed point of J_Γ where 
B=(b_1, …, b_k) and =_1 ⋯_n. 
First we show that 1 must be in the first cell of B.  That is, if 
1 = _c where c > 1, then _c-1 > _c. We claim 
that whenever we have a descent _i > _i+1 in , then 
_i and _i+1 must be part of a Γ-match in . That is, 
it is either the case that (i) there are bricks b_s and b_s+1 such that 
_i is the last cell of b_s and _i+1 
is the first cell of b_s+1 or (ii) there is a 
brick b_s that contains both _i and _i+1. In case (i), condition 
3 of Lemma <ref> ensures that _i and _i+1 must 
be part of Γ-match. In case (ii), we know that cell i is 
labeled with y.  It follows from condition (2) of Lemma <ref> 
that it can not be that either s =1 so that b_s =b_1 or that 
s > 1 and last(b_s-1) < first(b_s) because  
those conditions force  that  is increasing in b_s.  
Thus we must have that s > 1 and 
last(b_s-1) > first(b_s). 
Since (B,) is a fixed point of J_Γ, it cannot 
be that there is a Γ-match in  
which includes last(b_s-1) 
and  first(b_s) that ends weakly to the left of _i because 
then cell i would satisfy Case I of our definition of J_Γ and, 
hence, (B,) would not be a fixed point of J_Γ. 
Thus the Γ-match which includes last(b_s-1) 
and  first(b_s) must involve _i and _i+1. 
However, there can be no Γ-match that involves _c-1 and 
_c since _c=1 can only play the role of 1 in a Γ-match 
and each element of Γ starts with 1. Thus we must have _1 =1. 
   


Next we claim that 2 must be in either cell 2 or cell 3 in O. 
For a contradiction, assume that 2 is in cell c for c > 3. 
Then once again _c-1 > _c so that there must be a Γ-match 
in  that involves the two cells c-1 and c in (B,). 
However, In this case, the number which is in cell c-2 must be greater than 
_c so that the only possible Γ-match that involves 2 must start from cell c where 2 plays the role of 1 in the match. Thus there is no Γ-match in 
 that involves _c-1 and _c. 


We now have 
have two cases.

 

Case 1. 2 is in cell 2 of O.

 

In this case there are two possibilities, namely, either (i) 1 and 2 are both in the first brick b_1 of (B,) or (ii) brick b_1 is a single cell filled with 1, and 2 is in the first cell of the second brick b_2 of O.  In either case, we know that 1 is not part of a 
Γ-match in . So if we remove cell 1 from O and subtract 1 from the elements in the remaining cells, we will obtain a fixed point O' of J_Γ in 𝒪_Γ,n-1. 

Moreover, we can create a fixed point O=(B,) ∈𝒪_n of J_Γ satisfying the three conditions of Lemma <ref> where _2 =2 by starting with a fixed point (B',') ∈𝒪_Γ,n-1 of J_Γ, where B' =(b_1', …, b_r') and ' =_1' ⋯_n-1', and then letting = 1 (_1'+1) ⋯ (_n-1' +1), and setting  B = (1,b_1', …, b_r') or setting B = (1+b_1', …, b_r').

It follows that fixed points in Case 1 will contribute (1-y)U_Γ,n-1(y) to  U_Γ,n(y).

 

Case 2. 2 is in cell 3 of O=(B,). 

 

Since there is no decrease within the first brick b_1 of O=(B,), it must be the case that 2 is in the first cell of brick b_2 and there must be either a 14253-match or a 15243-match that involves the cells of the first two bricks. Therefore, we know that brick b_2 has at least 3 cells. In addition, we claim that 3 is in cell 5 of O since otherwise, 3 must be in some cell c for c > 6 and there must be a Γ-match between the two cells c-1 and c in O. By the previous argument, we can see that if 3 is too far away from 1 and 2, then it must play the role of 1 in any match that involves cell c. Thus, the only possible Γ-match that contains cell c must also start at c and can never involve both cells c-1 and c. Also, 3 cannot be in cell 2 nor 4 in O since both _2 and _4 are greater than 3, due to the Γ-match starting from cell 1. We now have two subcases depending on whether or not there is a Γ-match in O starting at cell 3.  

 

Subcase 2.a. There is no Γ-match in O starting at cell 3. 

 
  
In this case, we first choose a number x to fill in cell 2 of O. There are n-3 choices
for x.
 For each choice of _2 =x, we let d be the smallest of the remaining numbers, that is, 

    d = min( {1,2, …,n} - {1,2,3,_2}).
 
We claim that d must be either in cell 4 or cell 6 in (B,). First, d cannot 
be in cell 7 since otherwise there would be a Γ-match in  starting 
at cell 3.  Next d cannot be a cell c where c >7 since otherwise 
_c-1 >_c =d which means that there must be a Γ-match in  which 
includes both _c-1 and _c.  However, in the case, we would 
also have _c-2> _c which implies the only role that _c can play 
in a Γ-match is 1. 

This leaves us with three possibilities which are pictured in Figure 
<ref>. That is, either (i) d is in cell 4, (ii) d is in 
cell 6 and is in brick b_2 or (iii) d is in cell 6, but is the 
first element of brick b_3. In case (i), we can remove that first four 
cells from B, reduce the remaining elements of  to obtain a 
permutation α∈ S_n-4, and let B'=(b_2-2,b_3, …,b_k) to 
obtain a fixed point (B',α) of J_Γ of size n-4. 
Such fixed points will contribute -y^2U_Γ,n-4(y) to U_Γ,n(y). 
In case (ii), we have (n-5) ways to choose the element z in 
cell 4. Then we can remove that first five cells  
cells from B, reduce the remaining elements of  to obtain a 
permutation α∈ S_n-5, and let B'=(b_2-3,b_3, …,b_k) to 
obtain a fixed point (B',α) of J_Γ of size n-5. 
Such fixed points will contribute -y^2U_Γ,n-5(y) to U_Γ,n(y). 
In case (iii), we have (n-5) ways to choose the element z in 
cell 4. Then we can remove that first five cells  
cells from B, reduce the remaining elements of  to obtain a 
permutation α∈ S_n-5, and let B'=(b_2-3,b_3, …,b_k) to 
obtain a fixed point (B',α) of J_Γ of size n-5. 
Such fixed points will contribute y^3U_Γ,n-5(y) to U_Γ,n(y). 
Therefore, the total contribution of the fixed points from Subcase 2.a. is 
    -y^2(n-3)( U_Γ, n-4(y) +(1-y)(n-5)U_Γ, n-5(y)  ).















Subcase 2.b. There is a Γ-match in O starting at cell 3. 

 
 
In this case, we first choose a number x to fill in cell 2 of O. There are n-3 choices
for x. For each choice of _2, let 

    d = min( {1, …,n}- {1,2,3,_2}).

Then we claim that d must be in cell 7.  That is, we can argue as in 
Subcase 2a that it cannot be that d in cell c for c >7.  But 
since there is a Γ-match starting at cell 3 we know 
_4 > _7 and _6 > _7 so that d cannot be in cells 4 or 6. 
We then have (n-5)(n-6) ways to choose _4 =z and _6 =a. 

Next by condition (b) of Lemma <ref>, we 
know that each brick in b in B can contain at most one descent. Since 
we know that b_2 must have size at least 3 because there is a Γ-match in 
starting at cell 1 which is contained in b_1 and b_2, this means that either 
b_2 =3 or b_2=4. We claim that b_2 is of size 4.  That is, 
if b_2 =3, then either (I) a > d are in b_3 or (II) brick b_3 contains 
a single cell containing a and d is the first cell of b_4.  Case (I) 
cannot happen because then last(b_2) =3 < first(b_3) =a which 
implies that the elements in b_3 must be increasing by  
condition (a) of Lemma <ref>.  Case (II) cannot happen 
because that  last(b_3) =a > first(b_4) =d which implies 
there must be a Γ-match contained in the cells of b_3 and b_4 
which involves both _6 =a and _7 =d which is impossible since 
a > d.  Thus we are in the situation pictured in Figure <ref>.



Then we can remove that first six cells  
cells from B, reduce the remaining elements of  to obtain a 
permutation α∈ S_n-6, and let B'=(b_3, …,b_k) to 
obtain a fixed point (B',α) of J_Γ of size n-6. 
Such fixed points will contribute (n-3)(n-5)(n-6)y^3U_Γ,n-6(y) to U_Γ,n(y). 





In total, we obtain the recursion for U_Γ,n(y) as follows. 
    U_Γ,n(y)     = (1-y)U_Γ,n-1(y)  -y^2(n-3)(U_Γ, n-4(y) +(1-y)(n-5)U_Γ, n-5(y)  )+ 
                            y^3(n-3)(n-5)(n-6)U_Γ,n-6(y).
 
This proves Theorem <ref>. 


Using Theorem <ref>, we computed the initial values of 
the U_Γ,n(y)s which are given in Table 1.





Using these initial values of 
the U_Γ,n(y)s, one can then compute the initial values of 
NM_Γ,n(x,y) which are given in Table 2. 


















§ THE GENERATING FUNCTION U_142536(T,Y).
 


 In this section, we shall study the generating function 
U_τ(t,y) where τ = 142536. We let J_τ denote the 
involution J_Γ from Section 3 where Γ ={τ}.




We claim that the polynomials 

    U_τ,n (y) = ∑_O ∈𝒪_τ,n, J_τ(O) =OO W(O)
 
satisfy the following properties: 

  * U_τ,1(y)=-y, and 

  * for n ≥ 2,  

    U_τ,n(y) =         (1-y)U_Γ,n-1(y) +  ∑_k=0^[(n-8)/6]det(M_k+1) y^3k+3U_n-6k-7(y) 
                + ∑_k=0^[(n-6)/6]det(P_k+1)(-y^3k+2)
    [U_τ,n-6k-4(y) +yU_τ,n-6k-5(y) ].

  

It is easy to see when n=1, the only fixed point comes from 
brick tabloid that has a single brick of size 1 which contains 1 and 
the label on cell 1 is -y. Thus 
U_τ,1(y)=-y.

For n ≥ 2, let O=(B,) be a fixed point of I_Γ where B=(b_1, …, b_k) and =_1 ⋯_n. 
First we show that 1 must be in the first cell of B.  That is, if 
1 = _c where c > 1, then _c-1 > _c. We claim 
that whenever we have a descent _i > _i+1 in , then 
_i and _i+1 must be part of a τ-match in . That is, 
it is either the case that (i) there are bricks b_s and b_s+1 such that 
_i is the last cell of b_s and _i+1 
is the first cell of b_s+1 or (ii) there is a 
brick b_s that contains both _i and _i+1. In case (i), condition 
3 of Lemma <ref> ensures that _i and _i+1 must 
be part of τ-match. In case (ii), we know that cell i is 
labeled with y.  It follows from condition (2) of Lemma <ref> 
that it can not be that either s =1 so that b_s =b_1 or that 
s > 1 and last(b_s-1) < first(b_s) because  
those conditions force  that  is increasing in b_s.  
Thus we must have that s > 1 and 
last(b_s-1) > first(b_s). 
Since (B,) is a fixed point of J_τ, it cannot 
be that there is a τ-match in  
which includes last(b_s-1) 
and  first(b_s) that ends weakly to the left of _i because 
then cell i would satisfy Case I of our definition of J_τ and, 
hence, (B,) would not be a fixed point of J_τ. 
Thus the τ-match which includes last(b_s-1) 
and  first(b_s) must involve _i and _i+1. 
However, there can be no τ-match that involves _c-1 and 
_c since _c=1 can only play the role of 1 in τ-match 
and τ starts with 1. Thus we must have _1 =1. 
   


Next we claim that 2 must be in either cell 2 or cell 3 in O. 
For a contradiction, assume that 2 is in cell c for c > 3. 
Then once again _c-1 > _c so that there must be a τ-match 
in  that involves the two cells c-1 and c in (B,). However, since 2 is too far from 1 in B, the only possible 142536-match that involves 2 must start from cell c where 2 plays the role of 1 in the match. We then 
have two cases.

 

Case 1. 2 is in cell 2 of O.

 

In this case, there are two possibilities, namely, either (i) 1 and 2 are both in the first brick b_1 of (B,) or (ii) brick b_1 is a single cell filled with 1 and 2 is in the first cell of the second brick b_2 of (B,).  In either case, we know that 1 is not part of a τ-match in (B,). So if we remove cell 1 from (B,) and subtract 1 from the elements in the remaining cells, we will obtain a fixed point (B',') of J_Γ in 𝒪_Γ,n-1. 

Moreover, we can create a fixed point O=(B,) ∈𝒪_n satisfying the three conditions of Lemma <ref> where _2 =2 by starting with a fixed point (B',') ∈𝒪_Γ,n-1 of J_Γ, where B' =(b_1', …, b_r') and ' =_1' ⋯_n-1', and then letting = 1 (_1'+1) ⋯ (_n-1' +1), and setting  B = (1,b_1', …, b_r') or setting B = (1+b_1', …, b_r').


It follows that fixed points in Case 1 will contribute 
(1-y)U_Γ,n-1(y) to U_Γ,n(y). 

 

Case 2. 2 is in cell 3 of O=(B,). 

 

Since there is no decrease within the first brick b_1 of O=(B,), it must be the case that 2 is in the first cell of brick b_2 and there must be a 142536-match that involves the cells of the first two bricks. Therefore, we know that brick b_2 has at least 4 cells. 



To analyze this case, it will be useful to picture O=(B,) as a 2-line array A(O) where the elements in the i-th column are _2i-1 
and _2i reading from bottom to top.  In A(O), imagine 
the we draw an directed arrow from the cell containing i to the cell 
containing i+1.  Then it is easy to see that a τ-match 
correspond to block of points as pictured in Figure <ref>




Now imagine that A(0) starts with series of τ-matches starting 
at positions 1,3,5, …. We have pictured this situation at 
the top of Figure <ref>. Now consider the brick 
structure of O=(B,). Since the elements of b_1 must be 
increasing and _2 > _3, it must be the case that b_1 =2 and 
b_2 ≥ 4. We claim that b_2 =4 because if b_2 > 4, 
then _6 < _7 would be a descent in b_2. 
Thus cell 6 would be labeled with a y. The τ-match 
starting at cell 1 ends a cell 6 so that cell 6 would satisfy  Case I of our definition of J_τ which 
contracts that the fact that  O=(B,) is a fixed point of J_τ. 
Now the fact that _6 > _7 implies that b_3 ≥ 2 since 
there must be a τ-match that involves _6 and _7. Now if 
there is a τ-match starting at cell 7, then we can see 
that _8 > _9.  It cannot be that _8 and _9 are 
both in b_3 because it would follow that cell 8 would be labeled 
with a y and the τ-match starting at _3 would 
end at cell 8. Thus cell 8  would be in Case I of our definition of J_τ 
which contracts that the fact that  O=(B,) is a fixed point of J_τ. 
Thus it must be the case that b_3 =2. But the τ-match 
starting at cell 7 forces _8 > _9 so that there 
is a decrease between last(b_3) and first(b_4) which 
implies that there is τ contained in b_3 and b_4, which then means 
that b_4 ≥ 4. Now if there is a τ-matches starting 
at _9, then it must be the case that _12 > _13. Hence, 
it cannot be b_4 > 4 since otherwise cell 12 is labeled with a y. 
Since the τ-match starting a cell 7 ends at cell 12, then cell 12  
would be in Case I of our definition of J_τ 
which contracts that the fact that  O=(B,) is a fixed point of J_τ. 
Thus it must be the case that b_4 =4.  We can continue 
to reason in this way to conclude that if 
there are τ-matches starting at cells 1,3,7,9, …, 6k+1,6k+3, 
then b_2i-1 =2 for i =1, ,2k+1 and b_2i=4 for i =1, 
…, 2k. Similarly, if there  are τ-matches starting at cells 
1,3,7,9, …, 6k+1 but no τ-match starting at cell 6k+3, 
then b_2i-1 =2 for i =1, ,2k and b_2i=4 for i =1, 
…, 2k-1 and b_2k≥ 4. 






Note that our arguments above did not use the fact that there 
were τ-matches starting at cells 5, 11, ….  Indeed, 
these matches are not necessary to force the brick structure described 
above. For example, suppose that there were no τ-match 
starting at cell 5 but there where τ-matches starting at 
cell 7.  We have pictured this situation on the second 
line of Figure <ref> where we have written 
τ below the position corresponding to cell 5 to indicate 
that there is not a τ-match starting a cell 5. 
Then one can from the diagram pictured in the second line 
of Figure <ref>, that it must be the case that 
_6 < _9. It follows that if one looks at the requirements 
on  to start with such a series of τ-matches, then 
 must be a linear extension of poset whose Hasse diagram is 
pictured at the bottom of Figure <ref>.


There are now two cases depending on where the sequence 
of τ-matches starting at positions 1,3,7,9, … ends. 

 

Case 2.1.  There are τ-matches in  starting 
at positions 1,3,7,9, … , 6k+3, but there is no τ-match 
starting at position 6k+7. This situation is pictured 
in Figure <ref> in the case where k=2. 

In this case, we claim that {_1, …, _6k+8} = {1, 2, …, 6k+8}.  If not, then i be the least element in 
{1, 2, …, 6k+8} -{_1, …, _6k+8}. The question then 
becomes for which j is _j =i. It easy to see from the diagram at 
the top of  Figure <ref>, that _6k+8 > _r for 
r =1, …, 6k+7. This implies that _6k+8≥  6k+8. But since 
i ∈{1, 2, …, 6k+8} -{_1, …, _6k+8}, it must 
be the case that _6k+8 > 6k+8 ≥ i. 

We claim that j cannot equal 6k+9.  That is, if 
i = 6k+9, then _6k+8 > _6k+9.  It cannot be 
that _6k+8 and _6k+9 are in brick b_2k+3 because 
then _6k+8 is labeled with y and there is a τ-match 
contained in bricks b_2k+2 and b_2k+3 that ends before 
cell 6k+8 which means that cell 6k+8 satisfies Case 1 of our 
definition of J_τ which violates our assumption that (B,) is 
fixed point of J_τ.  If _6k+9 starts brick 
b_2k+4, then brick b_2k+3 must be of size 2 and 
there must be a τ-match contained in 
bricks b_2k+3 and b_2k+4 that involves  _6k+8 and _6k+9. 
But since _2k+8> _2k+9, that τ-match can only start at cell 6k+7 
which violates our assumption in this case. 

Next we claim that j cannot be ≥ 6k+10.  That is, if 
j ≥  6k+10, then both _j-2 and _j-1 are greater than 
_j =i. Thus 
_j-1 and _j must be part of τ-match in . 
But then  
the elements in two cells before cell j are bigger than 
that in cell j which means that the only 
role that _j can play in a τ-match
is 1. Thus there can be no τ-match that includes 
_j-1 and _j. 


 






Let α be the permutation 
that is obtained from  by removing the elements 1, …, 6k+7 and 
subtracting 6k+7 from the remaining elements. Let B' be the 
brick structure (b_2k+3-1,b_2k+4,…, b_k). Then it is easy to 
see that (B',α) is a fixed point of J_τ is size 
n-6k-7. 

Vice versa, suppose we 
start with a fixed point (B',α) of J_τ whose size 
n-6k-7 where 
B' =(d_1,d_2, …, d_s). Then we can obtain 
a fixed point (B,) of size n which 
has τ-matches in  starting 
at positions 1,3,7,9, … , 6k+3, but no τ-match 
starting at position 6k+7 by letting _1 …_6k+7 be any 
permutation of 1, …, 6k+7 which is a linear extension of 
the poset whose Hasse diagram is pictured at the bottom of 
Figure <ref> and letting _6k+8…_n be the sequence that 
results by adding  6k+7 to each element of α.  Then let 
B=(b_1, …, b_2k+2, d_1+1,d_2, …, d_s) where b_2i+1 =2 for 
i =0, …, k and b_2i=4 for i =1, …, k+1. 




It follows that contribution to U_τ,n(y) from the fixed points in Case 2.1 equal 

    ∑_k=0^⌊n-8/6⌋ 
    G_6k+7 y^3k+3U_τ,n-6k-7,

where G_6k+7 is the number of linear extensions of the poset pictured 
at the bottom of Figure <ref> of size 6k+7. 


Next we want to compute the number of linear extensions of G_6k+7. 
It is easy to see that the left-most two elements at the bottom of 
the Hasse diagram of G_6k+7 must be first two elements of the linear 
extension and the right-most element at the top of the Hasse diagram must be 
the largest element in any linear extension of 
G_6k+7. Thus the number of linear extensions of G̅_6k+4 which 
is the Hasse diagram of  G_6k+7 with those three elements removed, equals 
the number of linear extension of G_6k+7.  
We have pictured the Hasse diagrams of G̅_4, G̅_10 and G̅_16 in 
Figure <ref>. 





Now let A_0=1 and 
A_k+1 be the number of linear extensions of G̅_6k+4 for k ≥ 0. 
It is easy to see that A_1 =2.  There is a natural recursion satisfied 
by the A_k, namely, for k > 1, 

    A_k+1= ∑_j=0^k C_2+3j A_k-j

where C_n = 1/n+12nn is the n-th Catalan number. 
First, consider the number of linear extensions of the Hasse diagram 
of the poset D_n with n columns of the type pictured in Figure <ref>. 
It is easy to see that this is the number of standard tableaux of 
shape (n^2) which is well known to equal to C_n.

 




Next if we look at the Hasse diagram of G̅_6k+4 it is easy to see 
that there are no relation that is forced between 
the elements in columns 3i for i =1, …, k.  Now suppose 
that we partition the set of linear extensions of  G̅_6k+4 by 
saying the bottom element in column 3i is less than the top element 
in column 3i for i =1, …, j and the top element of column 
3j+3 is less than the bottom elements of column 3j+3.  Then we will have a situation as 
pictured in Figure <ref> in the case where k =6 and j=2. 
One can see that when one straightens out the resulting Hasse diagram, it 
starts with the Hasse diagram of D_2+3j and all those elements must be 
less than the elements in the top part of Hasse diagram which is a copy of 
the Hasse diagram of G̅_6(k-j-1)+4. 









Now consider the determinant of the n × n matrix M_n whose elements 
on the main diagonal are C_2, the elements on the j-diagonal above 
the main are C_2+3j for j ≥ 1, the elements on the sub-diagonal are -1, and 
the elements below the sub-diagonal are 0. For example we have pictured 
in M_7 in Figure <ref>. It is then easy to see that 
det(M_1) = C_2 =2. For n >1 if we expand the determinant by minors 
about the first row, then we see that we have the recursion 


    det(M_k)= ∑_j=0^k-1 C_2+3jdet(M_k-j-1),

where we set det(M_0)=1. 


For example, suppose that we expand the determinant M_7 pictured 
in Figure <ref> about the element of 
C_8 in the first row. Then in the next two rows, we are forced to 
expand about the -1's.  It is easy to see that the total sign of 
these expansion is always +1 so that in this case, we would get a 
contribution of 
C_8 det(M_4) to det(M_7). 





Thus it follows that A_n = det(M_n) for all n. 


Hence the contribution to U_τ,n from the fixed points in Case 1 equals 

    ∑_k=0^⌊n-8/6⌋det(M_k+1) y^3k+3U_τ,n-6k-7.

 

Case 2.2  There are τ-matches in  starting 
at positions 1,3,7,9, … , 6k+1, but there is no τ-match 
starting at position 6k+3. This situation is pictured 
in Figure <ref> in the case where k=3. 






In this case, we claim that {_1, …, _6k+5} = {1, 2, …, 6k+5}.  If not, then let i be the least element in 
{1, 2, …, 6k+5} -{_1, …, _6k+5}. The question then 
becomes for which j is _j =i.  It easy to see from the diagram at 
the top of  Figure <ref>, that _6k+6 > _r for 
r =1, …, 6k+5 and that _6k+5 > _r for 
r =1, …, 6k+5. This implies that _6k+5≥ 6k+5, but since 
i ∈{1, 2, …, 6k+5} -{_1, …, _6k+5}, it follows 
that 6k+5 < _6k+5 < _6k+6. 
  
It cannot be that i =_6k+7 because then _6k+6>_6k+7. 
Note that _6k+3,_6k+4,_6k+5,_6k+6 are elements 
of brick b_2k+2. If _6k+7 was also and element of 
brick b_2k+2, then _6k+6 would be marked with a y and there 
is a τ-match contained in bricks b_2k+1 and b_2k+2 that 
ends at cell 6k+6 so that we could apply Case 1 of the involution 
J_τ at cell 6k+6, which violates our assumption 
that (B,) was a fixed point of J_τ.  If _6k+7 starts 
brick b_2k+3, then there must be a τ-match that involves  
_6k+6 and _6k+7 and is contained in bricks b_2k+2 and b_2k+3.
Since we are assuming that there is no 
 τ-match cannot starting at _6k+3, it must be the case that there 
is a τ-match starting at 
_6k+5.  But then we have that situation pictured in Figure 
<ref>. In Figure <ref>, the 
 dark arrows are forced by the τ-matches starting 
at _6k+1 and _6k+5.  However the top two elements 
in brick b_2k+2 are _6k+5 and _6k+6, which are both 
greater than i. This means that the dotted arrow is forced which implies 
that there is a τ-match starting at cell _6k+3. 

Finally, it cannot be the case that j > 6k+7, because then 
it must be the case that _j-1 > _j so that _j-1 and 
_j must be part of a τ-match in . But in this situation, the 
elements 1, …, i-1 lie in cells that are more than 2 cells away 
from the cell containing i.  This means that in any τ-match in  
containing the element i, i can only play the role of 1 in that τ-match.  Thus, there 
could not  be a τ-match containing _j-1 and _j. 








Next, consider the possible j such that _j = 6k+6.  It cannot 
be that j > 6k+7, because then 
it must be the case that _j-1 > _j so that _j-1 and 
_j must be part of a τ-match in . But in this situation, the 
elements 1, …, 6k+5 lie in cells that are more than 2 cells away 
from the cell containing 6k+6.  This means that in any τ-match containing the 
element 6k+6 in , 6k+6 can only play the role of 1 in that τ-match.  Thus there 
could not be a  τ-match in  containing _j-1 and _j. It follows 
that 6k+6 = _6k+6 or _6k+7. Let α be the permutation 
that is obtained from  by removing the elements 1, …, 6k+4, setting 
α_1=1,  and letting α_2 …,α_n-(6k+4) be the result of 
subtracting 6k+5 from _6k+6…_n.  Let B' be the 
brick structure (b_2k+2-2,b_2k+3,…, b_k). Then it is easy to 
see that (B',α) is a fixed point of J_τ is size 
n-6k-4 that starts with a brick of size at least 2. 

Vice versa, suppose we 
start with a fixed point (B',α) of J_τ whose size 
n-6k-4 that starts with a brick of size at least 2 where 
B' =(d_1,d_2, …, d_s). Then we can obtain 
a fixed point (B,) of size n which 
has τ-matches in  starting 
at positions 1,3,7,9, … , 6k+1, but no τ-match 
starting at position 6k+3, by letting _1 …_6k+5 be any 
permutation of 1, …, 6k+5 which is a linear extension of 
the poset whose Hasse diagram is pictured at the bottom of 
Figure <ref> and letting _6k+6…_n be the sequence that 
results by adding  6k+5 to each element of α_2 …α_n-(6k+4).  We let 
B=(b_1, …, b_2k+1, d_1+2,d_2, …, d_s) where b_2i+1 =2 for 
i =0, …, k and b_2k=4 for i =1, …, k. 


Note that for any n, our arguments above show that 
the only fixed points (D,γ) of J_τ of size n where D=(d_1, …, 
d_k) and = _1 …_n which do not start with a brick of size at least 2 are 
the ones that start with a brick b_1=1 where _1 =1 and _2 =2. Clearly 
such fixed points are counted by -yU_n-1,y because d_1 would have weight -y 
and ((d_2, …, d_k),(_2-1) (_3-1) … (_n-1)) could be any 
fixed point of J_τ of size n-1. It follows that sum of the weights of 
all fixed points of J_τ of size n which start with a brick of size at least 2 is 
equal to 

    U_τ,n-(-yU_n-1,τ) =U_τ,n+yU_n-1,τ.
 


It follows that contribution to U_τ,n from the fixed points in Case 2.2 equal 

    -∑_k=0^⌊n-6/6⌋ 
    G_6k+4y^3k+2(U_τ,n-6k-4+yU_τ,n-6k-5),

where G_6k+4 is the number of linear extensions of the poset pictured 
at the bottom of Figure <ref> of size 6k+4. 








Next we want to compute the number of linear extensions of G_6k+4. 
It is easy to see that the left-most two elements at the bottom of 
the Hasse diagram of G_6k+4 must be first two elements of the linear 
extension. Thus the number of linear extensions of G̅_6k+2 which 
is the Hasse diagram of  G_6k+4 with those two elements removed, equals 
the number of linear extension of G_6k+4. 
We have pictured the Hasse diagrams of G̅_2, G̅_8 and G̅_14 in 
Figure <ref>. 





Now let B_0=1 and 
B_k+1 be the number of linear extensions of G̅_6k+2 for k ≥ 0. 
It is easy to see that B_1 =1.  Again there is a natural recursion satisfied 
by the B_ks, namely, for k > 1, 

    B_k+1=  C_3k+1 +∑_j=0^k-1 C_2+3j B_k-j-1,

where C_n = 1/n+12nn is the n-th Catalan number. 

As in the case of the posets G̅_6k+4, 
there is no relations that is forced between the elements of 
the elements in columns 3i for i =1, …, k.  Now suppose 
that we partition the set of linear extensions of  G̅_6k+2 by 
saying the bottom element in column 3i is less than the top element 
in column 3i for i =1, …, j and the top element of column 
3j+3 is less than the bottom elements of column 3j+3.  First if j=k, 
then we will have a copy of D_3k+1 which gives a contribution 
of C_3k+1 to the number of linear extensions of G̅_6k+4. 
If j < k, then we will have a situation as 
pictured in Figure <ref> in the case where k =6 and j=2. 
One can see that when one straightens out the resulting Hasse diagram, one obtains a diagram that 
starts with the Hasse diagram of D_2+3j and all those elements must be 
less than the elements in the top part of Hasse diagram which is a copy of 
the Hasse diagram of G̅_6(k-j-1)+2. 








Let P_n be the matrix that is obtained from the matrix M_n by 
replacing the elements C_m in the last 
column by C_m-1. For example we have pictured 
in P_7 in Figure <ref>. It is then easy to see that 
det(P_1) = 1. For n >1 if we expand the determinant by minors 
about the first row, then we see that we have the recursion 


    det(P_k)= C_3k-2+∑_j=0^k-2 C_2+3jdet(P_k-j-1),

where we set det(P_0)=1. 


For example, suppose that we expand the determinant P_7 pictured 
in Figure <ref> about the element of 
C_19 in the first row. Then in the next five rows, we would be forced to 
expand about the -1's.  It is easy to see that the total sign of 
these expansion is always +1 so that in this case, we would get a 
contribution of 
C_19 to the det(P_7). Expanding the determinant about the 
other elements in the first row gives the remaining terms of the recursion 
just like it did in the expansion of the determinant of M_n. 





Thus it follows that B_n = det(P_n) for all n.

Hence the contribution of fixed points of J_τ to U_τ,n(y) 
in the Case 2.2 equals 

    -∑_k=0^⌊n-6/6⌋det(P_k+1) y^3k+2(U_τ,n-6k-4+yU_τ,n-6k-5).




Therefore, we obtain the recursion for U_τ,n(y) for τ = 142536 is as follows.

    U_τ,n(y) =         (1-y)U_τ,n-1(y) +  
    ∑_k=0^⌊(n-8)/6 ⌋det(M_k+1) y^3k+3 U_τ,n-6k-7(y) 
                - ∑_k=0^[(n-6)/6]det(P_k+1)y^3k+2[U_τ,n-6k-4(y) +yU_τ,n-6k-5(y) ].






In Table <ref>, we computed U_142536,n(y) for n ≤ 14.  









§ THE PROOF OF THEOREM <REF>  



Let τ_a = τ = τ_1 …, τ_2a where 
τ_1, τ_3, …, τ_2a-1 = 12 … a and 
τ_2 τ_4 …τ_2a = (2a) (2a-1) … (a+1). If we picture 
τ_a in a 2-line array like we did in the last section, then we will get a diagram 
as pictured in Figure <ref>







The key property that τ_a has is that if = _1 …_2m is 
permutation where we have marked some of the τ_a-matches 
by placing an x at the start of a τ so that every element 
of  is contained in some τ_a-match and any two consecutive marked 
τ_a in  share at least one element, then it must 
be the case that 
_1_3 …_2m-1 = 12 … m and _2_4 …_2m = 
(2m) (2m-1) … (m+1). That is, it must be the case that 
= τ_m.  This can easily be seen from the picture of 
overlapping τ_a-matches like the one pictured in 
Figure <ref> where a =4 and m=12. Note that 
in such a situation, we will in fact have τ_a matches starting 
at positions 1,3,5, …, 2(m-a)+2 in . 





We need to show that the polynomials 
    U_τ_a,n (y) = ∑_O ∈𝒪_τ_a,n, J_τ_a(O) =OO W(O)
 satisfy the following properties: 

  * U_τ,1(y)=-y, and 

  * for n ≥ 2, 

    U_τ,n(y)  =       (1-y)U_τ,n-1(y)  - 
    ∑_k=0^⌊ (n-2a)/(2a)⌋n-(k+1)a-1(k+1)a-1 y^(k+1)a-1
    U_τ_a,n-(2(k+1)a)+1(y) 
              +∑_k=0^⌊ (n-2a-2)/(2a)⌋n-(k+1)a-2(k+1)a 
    y^(k+1)a U_τ_a,n-(2(k+1)a)-1(y).

  

Again, it is easy to see that when n = 1, U_τ_a,1(y)=-y. For n ≥ 2, let O=(B,) be a fixed point of J_τ_a where B=(b_1, …, b_t) and =_1 ⋯_n. By the same argument as the previous sections, it must be the case that 1 is in the first cell of O and 2 must be in either cell of 2 or cell 3 in O. Thus, we now have two cases. 

 

Case 1. 2 is in cell 2 of O.

 

Similar to Case 1 in the proof of Theorem <ref>, there are two possibilities, namely, either (i) 1 and 2 are both in the first brick b_1 of (B,) or (ii) brick b_1 is a single cell filled with 1 and 2 is in the first cell of the second brick b_2 of O.  In either case, we can remove cell 1 from O and subtract 1 from the elements in the remaining cells, we will obtain a fixed point O' of J_τ_a in 𝒪_τ_a,n-1. So the fixed points in this case will contribute (1-y)U_τ_a,n-1(y) to  U_τ_a,n(y).

 

Case 2. 2 is in cell 3 of O=(B,). 

 

In this case, _2 > _3 =2. Since  must be increasing in b_1, it 
follows that 2 is in the first cell of brick b_2 and there must be a τ_a 
match in the cells of b_1 and b_2 which can only start at cell 1. 
Thus it must be the case that brick b_2 has at least 2a-2 cells. 

Again, we shall think of O=(B,) as a two line array A(0) where 
column i consists of _2i-1 and _2i, reading from bottom 
to top. Now imagine that A(0) starts with series of τ-matches starting 
at positions 1,3,5, …. Our observation above shows that if this sequence 
of consecutive τ_a-matches covers cells 1, … ,2k for some 
k, then in the two line array A(O), all in entries in the first 
row of the first k columns are less than all the entries in top row 
of the first k columns, the cells in the bottom row of the first 
k columns are increasing, reading from left to right, and the cells 
in top row are increasing, reading from right to left. 


Next we consider the possible brick structures of O=(B,). We claim 
that we are in one of two subcases:  Subcase (2.A) where there is a  k ≥ 0 such 
that there are τ_a-matches in  starting at cells 
1, 3, 2a+1, 2a+3, … ,2(k-1)a+1,2(k-1)a+3,2ka+1, there is no τ_a-match
in  starting at cell 2ka+3, 2 =b_1 =b_3 = ⋯ = b_2k-1, 
2a-2 = b_2 =b_4 = ⋯ = b_2k, and b_2k+1 =2 and b_2k+2≥ 2a-2 or 
Subcase (2.B) where there is a  k ≥ 0 such 
that there are τ_a-matches in  starting at cells 
1, 3, 2a+1, 2a+3, … ,2(k-1)a+1,2(k-1)a+3,2ka+1,2ka+3,  there is no τ_a-match
in  starting at cell 2(k+1)a+1, 2 =b_1 =b_3 = ⋯ = b_2k-1=b_2k+1, 
2a-2 = b_2 =b_4 = ⋯ = b_2k+2, and b_2k+3≥ 2. Subcase (2.A) is pictured 
at the top of Figure <ref> and Subcase (2.B) is pictured at the 
bottom of Figure <ref> in the case where a=4 and k=2. 
Note that by our remarks above, we also 
know the relative order of the elements involved in these τ_a-matches in  
which is indicated by the poset whose Hasse diagram is pictured in Figure <ref>.
We can prove this by induction. That is, suppose k =0 and we are in Subcase (2.A). 
Then there is a τ_a-match in  
starting a cell 1 but no τ_a-match in  starting at cell 3. 
Our argument above shows that b_1=2 and b_2 ≥ 2a-2. 
Next suppose that k =0 and we are in Subcase (2.B)
so that there are τ_a-matches in  starting in cells 1 and 3 but there 
is no τ_a-match in  starting at cell 2a+1. Then we claim 
we claim that b_2 =2a-2.  That is, in such a situation 
we would know that _2a > _2a+1. Thus, 
if b_2 > 2a-2, then 2a would be labeled with a y. The τ_a-match 
starting at cell 1 ends at cell 2a so that cell 2a would satisfy 
Case I of our definition of J_τ_a which 
contracts that the fact that  O=(B,) is a fixed point of J_τ_a.  
Thus, brick b_3 must start at cell 2a+1. 
Now the fact that _2a > _2a+1 implies that b_3 ≥ 2 since 
there must be a τ_a-match that involves _2a and _2a+1 and lies in cells of b_2 and b_3. 





Now assume by induction that for k ≥ 1, 
there are τ_a-matches in  starting at cells 
1, 3, 2a+1, 2a+3, … ,2(k-1)a+1,2(k-1)a+3, 2 =b_1 =b_3 = ⋯ = b_2k-1,
2a-2 = b_2 =b_4 = ⋯ = b_2k-2, and b_2k≥ 2a-2. Suppose we are in Subcase (2.A) so that there is τ_a-match 
starting at cell 2ka+1 but there is no τ_a starting at cell 2ka+3.  
Then we know that _2ka > _2ka+1 due to the τ_a-match 
in  starting at cell 2(k-1)a+1. It cannot be the case that b_2k > 2a-2 since 
then cells 2ka and 2ka+1 are contained in brick b_2k so that cell 2ka would 
be marked with a y.  However, the τ_a-match staring at cell 2(k-1)a+1, which is 
the first cell of b_2k, ends at cell 2ka so that cell 2ka would 
satisfy Case I of our definition of J_τ_a which violates our assumption 
that (B,) is a fixed point of J_τ_a.  This means 
that b_2k=2a-2 and b_2k+1 starts at cell 2ka+1. Since _2ak > _2ak+1 
due to the τ_a-match in  starting at cell 2(k-1)a+3, we know 
that there must be a τ_a-match contained in the cells of b_2k and b_2k+1 
so that b_2k+1≥ 2. But then because of the τ_a-match in  starting 
at cell 2ka+1, we know that _2ka+2 > _2ka+3. It cannot be 
that cell 2ka+3 is in brick b_2k+1 because then cell 2k+2 would be marked 
with a y and there is a τ_a-match in  starting at cell 2(k-1)a+3 which 
ends at cell 2k+2 which is contained in the bricks b_2k and b_2k+1 which 
means that cell 2ka+2 would 
satisfy Case 1 of our definition of J_τ_a which violates our assumption 
that (B,) is a fixed point of J_τ_a. Thus it must be the case 
that b_2k+1 =2 and brick b_2k+2 starts at cell 2ka+3. But this 
means that there must be a τ_a-match in  contained in the cells 
of b_2k+1 and b_2k+2 so that b_2k+2≥ 2a-2. 
Now if there is also a τ_a-match in  starting at cell 2ka+3, 
then we claim that b_2k+2=2a-2.  That is, we know 
that _2(k+1)a > _2(k+1)a+1. It cannot be that  b_2k+2 > 2a-2 because 
then cell 2(k+1)a would be labeled with a y and the τ_a-match in  starting 
at cell 2ka+1 ends at cell 2(k+1)a and is contained in the bricks 
b_2k+1 and b_2k+2 so that cell 2(k+1)a would satisfy Case 1 of our 
definition of J_τ_a which would violate our assumption that 
(B,) is fixed point of J_τ_a.  Thus b_2k+2=2a-2. But 
then due to the τ_a-match in  starting at cell 
2(k+1)a+3, we know that _2(k+1)a > _2(k+1)a+1 which means 
that there must be a τ_a match contained in bricks b_2k+2 and b_2k+3. 
This means that b_2k+3≥ 2.




Thus we have two cases to consider. 

 

Subcase (2.A) There is a  k ≥ 0 such 
that there are τ_a-matches in  starting at cells 
1, 3, 2a+1, 2a+3, … ,2(k-1)a+1,2(k-1)a+3,2ka+1, there is no τ_a-match
in  starting at cell 2ka+3, 2 =b_1 =b_3 = ⋯ = b_2k-1, 
2a-2 = b_2 =b_4 = ⋯ = b_2k, and b_2k+1 =2 and b_2k+2≥ 2a-2.

In this case, we claim that {1, …, (k+1)a+1} = {_1, _3, …, _2(k+1)a-1,_2(k+1)a}.  That is, if one considers the diagram at the top of 
Figure <ref>, then the elements in the bottom row are 
1,2, …, (k+1)a, reading from left to right, and the element 
at the top of column (k+1)a is equal to (k+1)a+1. 
If this is not the case, then let 

    i = min({1, …, (k+1)a+1} - {_1, _3, …, _2(k+1)a-1,_2(k+1)a}).
This means _2(k+1)a > i and, hence one can see by the relative order of the elements 
in the first (k+1)a columns of A(O) that i can not lie in the first 
(k+1)a columns. Then the question is for what j is _j=i.  First we claim that 
it  cannot be that _2(k+1)a+1 =i. That is, in such a  situation,
_2(k+1)a> _2(k+1)a+1.  Now it cannot be that 
_2(k+1)a and _2(k+1)a+1 lie in brick b_2k+2 because 
then the τ_a-match in  that starts in 
the first cell of b_2k+1 ends at cell 2(k+1)a which means that 
cell 2(k+1)a would be labeled with a y and satisfy Case I of our 
definition of J_τ_a which would violate our assumption that 
(B,) is fixed point of J_τ_a. Thus it must be the case 
that brick b_2k+3 starts at cell 2(k+1)a+1. But then there 
must be a τ_a-match in  contained in the cells of bricks 
b_2k+2 and b_2k+3 which would imply that there is a τ_a-match 
in  starting at cell  2ka+3 which violates our assumption in this case. 
Hence j > 2(k+1)a+1 which implies  
that both _j-2 and _j-1 are greater than _j =i. But then 
there could be no τ_a-match in  which contains both 
_j-1 and _j because the only role that i could play in 
τ_a-match in  would be 1 under those circumstances. 

It follows that if we remove the elements in A(0) from the first 
(k+1)a-1 columns plus the bottom element of column (k+1)a, then 
(B','), where B'=(b_2k+2-(2a-1),b_2k+3, …, b_t) 
and ' = red(_2(k+1)a…_n), will 
be a fixed point of J_τ_a of size n-(2(k+1)a)+1.  Note that 
in such a situation, we will have 
n-(k+1)a-1(k+1)a-1 ways to choose the elements of 
that lie in the top rows of the first (k+1)a-1 columns of A(O). 
Note that the powers of y coming from the bricks b_1, …, b_2k is 
y^ka and the powers of y coming from bricks b_2k+1 and b_2k+2 
is -y^a-1. It follows 
that the elements in Subcase (2.A) contribute 

    -∑_k=0^⌊ (n-2a)/(2a)⌋n-(k+1)a-1(k+1)a-1 
    y^(k+1)a-1 U_τ_a,n-(2(k+1)a)+1(y)

to U_τ_a,n(y). 

 

Subcase (2.B). There is a  k ≥ 0 such 
that there are τ_a-matches in  starting at cells 
1, 3, 2a+1, 2a+3, … ,2(k-1)a+1,2(k-1)a+3,2ka+1,2ka+3, there is no τ_a-match
in  starting at cell 2(k+1)a+1, 2 =b_1 =b_3 = ⋯ = b_2k-1=b_2k+1, 
2a-2 = b_2 =b_4 = ⋯ = b_2k+2, and b_2k+3≥ 2.

In this case, we claim that {1, …, (k+1)a+2} = {_1, _3, …, _2(k+1)a+1,_2(k+1)a+2}.  That is, if one considers the diagram at the bottom of 
Figure <ref>, then the elements in the bottom row are 
1,2, …, (k+1)a+1, reading from left to right, and the element 
at the top of column (k+1)a+1 is equal to (k+1)a+2. 
If this is not the case, then let 

    i = min({1, …, (k+1)a+2} - {_1, _3, …, _2(k+1)a+1,_2(k+1)a+2}).

This means _2(k+1)a+2 > i and, hence one can see by the relative order of the elements 
in the first (k+1)a+1 columns of A(O) that i can not lie in the first 
(k+1)a+1 columns. Then the question is for what j is _j=i.  First we claim that 
it  cannot be that _2(k+1)a+3 =i. That is, in such as situation,
_2(k+1)a+2> _2(k+1)a+3.  Now it cannot be that 
_2(k+1)a+2 and _2(k+1)a+3 lie in brick b_2k+3 because 
then the τ_a-match in  that starts in 
the first cell of b_2k+2 ends at cell 2(k+1)a+2 which means that 
cell 2(k+1)a+2 would be labeled with a y and satisfy Case I of our 
definition of J_τ_a which would violate our assumption that 
(B,) is fixed point of J_τ_a. Thus it must be the case b_2k+3=2 
that brick b_2k+4 starts at cell 2(k+1)a+3. But then there 
must be a τ_a-match in  contained in the cells of bricks 
b_2k+3 and b_2k+4 which would imply that there is a τ_a-match 
in  starting at cell  2(k+1)a+1 which violates our assumption in this case. 
Hence j > 2(k+1)a+3 which implies  
that both _j-2 and _j-1 are greater than _j =i. But then 
there could be no τ_a-match in  which contains both 
_j-1 and _j because the only role that i could play in 
τ_a-match in  would be 1 under those circumstances. 

It follows that if we remove the elements in A(0) from the first 
(k+1)a+1 columns plus the bottom element of column (k+1)a+2, then 
(B','), where B'=(b_2k+3-1,b_2k+4, …, b_t) 
and ' = red(_2(k+1)a+2…_n, will 
be a fixed point of J_τ_a of size n-(2(k+1)a)-1.  Note that 
in such a situation, we will have 
n-(k+1)a-2(k+1)a ways to choose the elements of 
that lie in the top rows of the first (k+1)a-1 columns of A(O). 
Note that the powers of y coming from the bricks b_1, …, b_2k_2 is 
y^(k+1)a.
It follows 
that the elements in Subcase (2.B) contribute 

    ∑_k=0^⌊ (n-2a-2)/(2a)⌋n-(k+1)a-2(k+1)a 
    y^(k+1)aU_τ_a,n-(2(k+1)a)-1(y)

to U_τ_a,n(y). 

 

Therefore, the recursion for the polynomials U_τ,n(y) is given by 

    U_τ,n(y)  =       (1-y)U_τ,n-1(y)  - 
    ∑_k=0^⌊ (n-2a)/(2a)⌋n-(k+1)a-1(k+1)a-1 y^(k+1)a-1
    U_τ_a,n-(2(k+1)a)+1(y) 
              +∑_k=0^⌊ (n-2a-2)/(2a)⌋n-(k+1)a-2(k+1)a 
    y^(k+1)a U_τ_a,n-(2(k+1)a)-1(y).

This concludes the proof of Theorem <ref>. 























20



AAM R.E.L. Aldred, M.D. Atkinson, and D.J. McCaughan, 
Avoiding consecutive patterns in permutations, Adv. in Applied Math.,
45: Issue 3 (2010), 449-461. 


BR Q.T.  Bach and J.B. Remmel, Generating functions for descents over 
permutations which avoid sets of consecutive patterns, Australian Journal 
of Combinatorics. 64 (2016), 194-231.




BR2 Q.T. Bach and J.B. Remmel, Descent c-Wilf equivalence, to appear 
in Discrete Mathematics and Theoretical Computer Science. 


B1 A.M. Baxter, Refining enumeration schemes to count according 
to inversion number, Pure Mathematics and Applications, 21 (2) (2010),
 136-160. 



B2 A.M. Baxter, Refining enumeration schemes to count according 
to permutation statistics, Electronic J. Comb., 21: Issue 2 (2014). 



DK V. Dotsenko and A. Khoroshkin, Anick-type resolutions and 
consecutive pattern avoidance, arXiv:1002.2761v1 (2010).




DR A. Duane and J. Remmel, Minimal overlapping patterns in colored
permutations, Electronic J. Combinatorics, 18 (2) (2011).


Eg1 O. Eğecioğlu and J. B. Remmel, Brick tabloids and the connection matrices between bases of symmetric functions, Discrete Appl. Math., 34 (1991), no. 1-3, 107–120, Combinatorics and theoretical computer science (Washington, DC, 1989).
  
EN
S, Elizalde and M. Noy, Consecutive patterns in
permutations, Adv.
  in Appl. Math. 30 (2003), no. 1-2, 110-125, Formal power series and
  algebraic combinatorics (Scottsdale, AZ, 2001).

EN2 S. Elizalde and M. Noy, Clusters, generating 
functions and asymptotics for consecutive patterns in permutations,
Advances in App. Math., 49(2012), 351-374. 

 




EKP R. Ehrenborg, S. Kitaev, and P. Perry, A spectral approach 
to consecutive pattern-avoiding permutations, J. of Combinatorics, 
2 (2011), 305-353. 



GJ I.P. Goulden and D.M. Jackson, Combinatorial Enumeration,
A Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons Inc,
New York, (1983).











JR1 M. Jones and J. B. Remmel, Pattern Matching in the Cycle Structures of Permutations, Pure Math. and Applications, 22 (2011), 
173-208.



JR M. Jones and J. B. Remmel, A reciprocity approach to computing 
generating functions for permutations with no pattern matches, 
Discrete Mathematics and Theoretical Computer Science, 
DMTCS Proceedings, 23 International Conference on Formal 
Power Series and Algebraic Combinatorics (FPSAC 2011), 119 (2011), 
551-562.


JR2 M. Jones and J. Remmel, A reciprocity method for 
computing generating function over the set of permutations 
with no consecutive occurrences of τ, 
Discrete Mathematics, 313 Issue 23 (2013), 2712-2729. 


JR3 M. Jones and J. Remmel, Generating functions 
for the number of permutations with no 
consecutive occurrences of  1p23 ⋯ (p-1) or 13⋯(p-1)2p,  
to appear in Pure Mathematics and Applications.



Kit1
S. Kitaev, Partially ordered generalized patterns,
Discrete Math.298 (2005), 212-229.


Kitbook S. Kiteav, Patterns in permutations and words, 
Springer-Verlag, 2011. 



MenRem  A. Mendes and J.B. Remmel, 
Permutations and words counted by 
consecutive patterns, Adv. Appl. Math, 37 4, (2006), 443-480.

oeis N. J. A. Sloane, The on-line encyclopedia of integer sequences,
published electronically at * http://www.research.att.com/njas/sequences/.


Stanley R.P. Stanley, Enumerative Combinatorics, vol. 2, 
Cambridge Studies in Advanced Mathematics 62, Cambridge University 
Press, (1999). 








