Function Repository Resource:

# BaxterPermutationQ

Determine whether a permutation is a Baxter permutation

Contributed by: Motoharu Ito
 ResourceFunction["BaxterPermutationQ"][perm] gives True if perm is a Baxter permutation and False otherwise.

## Details

A permutation p={p1,p2,,pn} is a Baxter permutation if there are no four indices i<j<k<l such that k=j+1 and pi,pj,pk,pl is an occurrence of the pattern 2413 or 3142.

## Examples

### Basic Examples (2)

Test whether {2,6,3,1,5,4} is a Baxter permutation:

 In:= Out= {2,4,1,3} is not a Baxter permutation:

 In:= Out= {2,5,4,1,3} is not a Baxter permutation because it does not avoid pattern 2413 for (i,j,k,l)=(1,3,4,5):

 In:= Out= {1,3,5,2,4} is not a Baxter permutation because it does not avoid pattern 2413 for (i,j,k,l)=(2,3,4,5):

 In:= Out= ### Scope (2)

Count the total number of Baxter permutations up to length seven (the Baxter numbers):

 In:= Out= Compare with an explicit expression for the Baxter numbers:

 In:= Out= The permutations of the down-crossing fixed points is a Baxter Permutation:

 In:= Out= In:= Out= If the positive integers n, a, b have n=ab, then the Chebyshev polynomial satisfies Tn=TaTb=TbTa. Then Tn(Ta(x))=Ta(Tn(x))=Ta(x), so Ta(x) is also a fixed point of Tn. Similarly, Tb(x) is also a fixed point of Tn. Thus, Ta and Tb are fixed point permutations on the fixed point set of Tn. Interestingly, the permutation by Ta and Tb also preserves the type of fixed points (i.e. up-crossing, down-crossing, touching). The type is the mapping of a down-crossing fixed point to a down-crossing fixed point. The fixed points marked with red dots are down-crossing fixed points:

 In:= Out= Motoharu Ito

## Version History

• 1.0.0 – 08 December 2022