Classes of partial matching words of length 6 and 7 according to pattern τ-avoiding matchings and the numbers #Mn(τ), n=1,2,3,4,5,6,7.



A matching on a set [2n]={1,2,\ldots,2n} is a partition of [2n] in which every block contains exactly two elements, or equivalently, a graph on [2n] in which every vertex has degree one. There are many ways to represent a matching. It can be displayed by drawing the 2n points on a horizontal line in the increasing order. This is called the linear representation of a matching. An edge e=(i,j) in a matching is always written in such a way that i<j, where the vertices i and j are called the initial point and the end point, respectively. We assume that every edge (i,j) is drawn as an arc between the nodes i and j above the horizontal line. The set of matchings on [2n] is denoted by Mn.
In this paper, we also use the representation of a matching M with n edges by a sequence of length 2n on the set {1,2,...,n} such that each element i (1<i<n) appears exactly twice, and the first occurrence of the element i precedes that of j if i<j. Such a representation is called the Davenport-Schinzel sequence or the canonical sequential form. In fact, the canonical sequential form of a matching is the sequence obtained from its linear representation by labeling the endpoints in accordance with the order of the appearances of initial points, see the corresponding paper.
Given a sequence a1a2...am of integers, we define its pattern as a sequence obtained by replacing the minimum element (which may have repeated occurrences) by 1, and replacing the second minimum element by 2, and so on. For example, the patten of the sequence 33299253826 is 221664132514. In this paper, we are mainly concerned with the partial pattern 12312 in the sense that it does not form a complete matching. The set of partial patterns of length k is denoted by P(k). In the terminology of canonical sequential forms, we say that a matching π avoids a pattern τ, or π is τ-avoiding, if there is no subsequence of the pattern τ in π. The set of τ-avoiding matchings on [2n] is denoted MMn(τ). Two partitions σ and σ' are equivalent if there is a size-preserving bijection between σ-avoiding and σ'-avoiding matchings. Here the table of all the equivalences for P(6).


Pattern #M1(τ) #M2(τ) #M3(τ) #M4(τ) #M5(τ) #M6(τ) #M7(τ)
1234551315105000
123456131510594500
123445,1234541315105315693 1287
123435,123453131510544116835863
123434,123443131570 31513866006
123424 131577 396205710790
123425,1234521315105513238710959
123345 1315105567277212870
123442 131577 432247514560
123414 131581 450254714754
123415,1234511315105561293115487
123344 131570 378237617160
123234,123243,123324,123342,123423,123432131584495300318564
123245 1315105621356420085
122344,123244 131577 441287121203
123441 131581 484317921664
123134*,123143*,123413131587539350323594
121344,123144131581491334125465
1231451315105657406625643
123314,123341*,123431*131587555375726508
123124**,123142*,123214**,123241,123412*,123421*131590594416530454
112344131585542386630681
1223451315105720495034411
123132,123213131483570431835068
121342131593638464735263
122314131593644477137004
122341131593646481837744
121324131593646482938072
123123,123312,123321131484594471940898
1213451315105745545641086
123231131484595475041541
121332,122313131484595475941913
121323131484596478742440
121234,122134131595684534644293
122334,122343131591639511546111
112334,112343,121334,121343131593669547150219
122331131485622526650299
112323,112332,121233,122133131485624533451876
1123451315105800651355971
112233131486648576058896
112324,112342131597745656365063
112234131599784714673341



Pattern #M1(τ) #M2(τ) #M3(τ) #M4(τ) #M5(τ) #M6(τ) #M7(τ) #M8(τ)
1234566131510594500
12345671315105945103950
1234556,1234565131510594534659009
1234545,12345541315105630346518018
1234546,12345641315105945485121879
12345351315105693435626741
12344551315105630415830888
1234536,12345631315105945564331031
12345531315105693475232175
12345251315105729495033111
12344561315105945623736036
1233455,12343551315105693485137323
1234526,12345621315105945617138103
12345151315105753538838527
1234345,1234354,1234435,1234453,1234534,12345431315105756544539039
12345521315105729532441327
1232455,12342551315105729540143433
1234516,12345611315105945655543815
1234245,1234524,12342541315105783592945539
12343561315105945683146332
12345511315105753574246781
1234155,12314551315105753580548611
1234425,1234452,12345421315105783610548841
12345141315105801629550221
12234551315105765596250258
12341541315105801629550402
12341451315105801629550427
12342561315105945722752858
1234235,1234325,1234352,1234523,1234532,12342531315105810653454145
12344151315105801646355020
1234451,12345411315105801646355226
12134551315105785635055575
1234243,1234324131598747627056134
12341561315105945751558044
12345131315105825682758546
12341531315105825683458698
12341351315105825684959040
12324531315105837701860411
12343151315105825692960796
12343511315105825693660889
12345311315105825695161276
1234234,1234423,1234432131598756653461347
1234342131598756654561750
1232443,1233424131598756654561867
12334251315105837708462023
1232434131598756655662231
1234143131599771668062266
12334521315105837710662634
1234314131599772670462713
12324351315105837710662777
11234551315105814691463871
1234134131599773676064227
12334561315105945792064350
12341521315105840721264827602584
12342511315105840721264827602359
1234125,1234215,1234512,12345211315105840721264932
1231434131599773679965648
1233445,12334541315105819702966495
12314531315105849735866510
1233414131599778690167022
12314351315105849738067385
1231443131599779692467444
1234413,1234431131599778692167575
12334151315105849742768267
1234341131599779695368303
1233442131598765684268458
12334511315105849743668643
12342141315100796710968706
12341421315100796711068740
1223434,1223443,1232344,1233244131598765686469342
12134241315100794709769370
1232345,12332451315105855752469498
12324561315100797718570928
12314241315100797718170944
12341241315100797718570958
12314521315105861764071062
1223445,1223454,1232445,12324541315105837735971123
12234141315100798720471303
12324141315100798720671364
12342411315100798722571971
12324151315105861768572329
1231344131599782709572376
12314251315105861768472471
12134421315100800726572584
1123434,1123443,1213443,1213434131599783711772757
12324511315105861770372871
12314421315100801729673217
12313451315105865775173410
1233441131599787719273575
1234412,12344211315100803734373896
1233144131599788722574480
12324131315101819750574819
12321431315101819750674864
1223344131598774712874880
1231342,1234132*,1234213*1315101819750974987
12314321315101819751375143
12321341315101819751375147
12313241315101819751375152
1213454,1213445,1231445,12314541315105849761975167
12331451315105865782175222
12314561315105945839575256
12312431315101820755576227
12324411315100805744676924
12234411315100805745277202
1212344,1221344,1223144,1231244,1232144,12132441315100805746177630
1123344,1213344131599791735977955
1233124,1233142,12332411315101823764978251861239
12314231315101823764978251861254
1231234,1233214,1233412,1233421,1234123,1234312,12343211315101823765378403
12323141315101823765478473
12323411315101823765878629
12342311315101823765878630
12324311315101823765878647
1231245,12321451315105875804778928
1123445,11234541315105861788179433
12134521315105880813479454
12134251315105880814280314
12234151315105880818581455
12234511315105880819481755
11234241315101828786784360
12234561315105945880084669
1223435,12234531315105873819585319
12134231315102847809486068
11234421315101832797786566
12234131315102850818487886
12134321315102850818687963
12133421315102850818687991
12133241315102850818687998
12231431315102850818788047
1122344,11232441315101833803188139
12231341315102850819088168
12132431315102850819388292
12132341315102850819388295
12231451315105894855888436
1123435,1123453,1213453,12134351315105881837988447
12134561315105945894588677
12132451315105894857389082
12234311315102853829790822
12233141315102853830891291
12233411315102853831191422
1123234,1123243,1123324,1123342,1123423,11234321315102853831991836
12233451315105891862492898
1212345,12213451315105905889395513
1123345,12133451315105897877395597
1123425,11234521315105897880396607
11234561315105945924496995
1212334,1212343,1221334,122134313151038818887102305
112324513151059099126102903
1122334,112234313151038838967104515
112234513151059209450109747


The program, C++ program that creates the data in the above tables:
#include
#define MAXN 100 /*Maximum length of the words*/

int n; /*2n is the length of the matching*/

int word[MAXN],p[MAXN]; /* the matching, the pattern*/
int nlet[MAXN];

long num1=0; /*number matchings*/

int listp[100000][10],nlistp=0; /*list of the patterns of length at most 10 and number the patterns*/

FILE *fout; /*file contains the output*/

int order(int a,int b) /*checking the order between two elements*/
{
 if (a==b) return 0;
 else if(a>b) return 1;
         else return -1;
}

int testK(int k,int *p1,int *p2) /*test if p1 and p2 of length k are order-isomorphic*/
{
 int i;
 for (i=0;i<k;i++)
   if (order(p1[i],p1[k])!=order(p2[i],p2[k])) return 1;
 return 0;
}

int vpatterns3() /* checking if the word contains the pattern of length 4*/
{
 int curword[4]; /*subword of 'word[]' currently being tested*/
 int i1,i2,i4;
 for(i4=0;i4<n-2;i4++){
   curword[0]=word[i4];
   for(i2=i4+1;i2<n-1;i2++){
     curword[1]=word[i2];
     if (testK(1,curword,p)) continue;
     for(i1=i2+1;i1<n;i1++){
       curword[2]=word[i1];
       if (!testK(2,curword,p))//pattern found
         return 0;
     }
   }
 }
 return 1;//no pattern
}

int vpatterns4() /* checking if the word contains the pattern of length 4*/
{
 int curword[4]; /*subword of 'word[]' currently being tested*/
 int i1,i2,i3,i4;
 for(i4=0;i4<n-3;i4++){
   curword[0]=word[i4];
   for(i3=i4+1;i3<n-2;i3++){
     curword[1]=word[i3];
     if (testK(1,curword,p)) continue;
     for(i2=i3+1;i2<n-1;i2++){
       curword[2]=word[i2];
       if (testK(2,curword,p)) continue;
       for(i1=i2+1;i1<n;i1++){
         curword[3]=word[i1];
         if (!testK(3,curword,p))//pattern found
           return 0;
       }
     }
   }
 }
 return 1;//no pattern
}

int vpatterns5()
{
 int curword[5];//subword of 'word[]' currently being tested
 int i1,i2,i3,i4,i5;
 for(i5=0;i5<n-4;i5++){
   curword[0]=word[i5];
   for(i4=i5+1;i4<n-3;i4++){
     curword[1]=word[i4];
     if (testK(1,curword,p)) continue;
     for(i3=i4+1;i3<n-2;i3++){
       curword[2]=word[i3];
       if (testK(2,curword,p)) continue;
       for(i2=i3+1;i2<n-1;i2++){
         curword[3]=word[i2];
         if (testK(3,curword,p)) continue;
         for(i1=i2+1;i1<n;i1++){
           curword[4]=word[i1];
           if (!testK(4,curword,p))//pattern found
             return 0;
         }
       }
     }
   }
 }
 return 1;//no pattern
}

int vpatterns6()
{
 int curword[6];
 int i1,i2,i3,i4,i5,i6;
 for(i6=0;i6<n-5;i6++){
   curword[0]=word[i6];
   for(i5=i6+1;i5<n-4;i5++){
     curword[1]=word[i5];
     if (testK(1,curword,p)) continue;
     for(i4=i5+1;i4<n-3;i4++){
       curword[2]=word[i4];
       if (testK(2,curword,p)) continue;
       for(i3=i4+1;i3<n-2;i3++){
         curword[3]=word[i3];
         if (testK(3,curword,p)) continue;
         for(i2=i3+1;i2<n-1;i2++){
           curword[4]=word[i2];
           if (testK(4,curword,p)) continue;
           for(i1=i2+1;i1<n;i1++){
             curword[5]=word[i1];
             if (!testK(5,curword,p))
               return 0;
           }
         }
       }
     }
   }
 }
 return 1;
}

int vpatterns7()
{
 int curword[7];
 int i1,i2,i3,i4,i5,i6,i7;
 for(i7=0;i7<n-6;i7++){
   curword[0]=word[i7];
   for(i6=i7+1;i6<n-5;i6++){
     curword[1]=word[i6];
     if (testK(1,curword,p)) continue;
     for(i5=i6+1;i5<n-4;i5++){
       curword[2]=word[i5];
       if (testK(2,curword,p)) continue;
       for(i4=i5+1;i4<n-3;i4++){
         curword[3]=word[i4];
         if (testK(3,curword,p)) continue;
         for(i3=i4+1;i3<n-2;i3++){
           curword[4]=word[i3];
           if (testK(4,curword,p)) continue;
           for(i2=i3+1;i2<n-1;i2++){
             curword[5]=word[i2];
             if (testK(5,curword,p)) continue;
             for(i1=i2+1;i1<n;i1++){
               curword[6]=word[i1];
               if (!testK(6,curword,p))
                 return 0;
             }
           }
         }
       }
     }
   }
 }
 return 1;
}

int matching()
{
 int lbb,laa[MAXN],i,j;
 lbb=0;
 for(i=0;i<n;i++) if(lbb<word[i]) lbb=word[i];

 for(i=1;i<=lbb;i++) laa[i]=0;
 for(i=0;i<n;i++) laa[word[i]]++;
 for(i=1;i<=lbb;i++) if(laa[i]!=2) return(0);
 return(1);
}

int test()
{
 int i;
 for(i=0;i<n-1;i++)
   if(word[i+2]==word[i]) return(0);
 return(1);
}

void builtmatchs(int mp,int l,int lenp) /*built all the prefect matchings of length 2n, and count 1 if it avoids the pattern of length lenp*/
{
 int j,i,ii;
 if(l==n/2+1)
 {
   if (vpatterns6()==1) num1++;
 }
 else
 {
   ii=mp; while(nlet[ii]==1) ii++;
   mp=ii+1;
   for(j=ii+1;j<n;j++)
     if(nlet[j]==0)
     {
       word[ii]=l; nlet[ii]=1; word[j]=l; nlet[j]=1;
       builtmatchs(mp,l+1,lenp);
       nlet[j]=0; nlet[ii]=0;
     }
 }
}

void builtpatterns(int l,int lenp) /*built all the word patterns p[] of length lenp,*/
{
 int i,j,v,la[MAXN],lb,fg,i1;
 if (l==lenp)
 {
   lb=-1; for(i1=0;i1<lenp;i1++) if(lb<p[i1]) lb=p[i1];
   for(i1=0;i1<=lb;i1++) la[i1]=0;
   for(i1=0;i1<lenp;i1++) la[p[i1]]++;
   fg=1; for(i1=0;i1<=lb;i1++) if(la[i1]>2) fg=0;
   if(fg==1)
   {
     for(i=0;i<lenp;i++) listp[nlistp][i]=p[i];
     nlistp++;
   }
 }
 else
 {
   v=0; for(i=0;i<l;i++) if(p[i]>v) v=p[i];
   for(j=1;j<=(v+1);j++)
   {
     p[l]=j;
     builtpatterns(l+1,lenp);
   }
 }
}

int main()
{
 int lenp=6; /*the length of the pattern (either 4,5,6, or 7)*/

 fout=fopen("output.txt","w"); /*open output file*/

 builtpatterns(0,lenp); /*built all the patterns p of length lenp and give for each the sequence of p-avoiding words */

 int i,i1;
 for(i1=0;i1<nlistp;i1++)
 {
   for(i=0;i<lenp;i++) p[i]=listp[i1][i];

   printf("%d) patterns ",i1+1); fprintf(fout,"%d) patterns ",i1+1);
   for(i=0;i<lenp;i++) {printf("%d",p[i]); fprintf(fout,"%d",p[i]);}
   printf("-Matchings :");
   fprintf(fout,"-Matchings:");

   for(n=2;n<15;n=n+2) /*the length of the prefect matchings */
   {
     num1=0;
     for(i=0;i<n;i++) {word[i]=0; nlet[i]=0;}

     builtmatchs(0,1,lenp);
     printf("%6d ",num1);
     fprintf(fout,"%6d ",num1);
   }
   printf("\n");
   fprintf(fout,"\n");
 }

 fclose(fout);/*close the file*/
 return(1);/*end*/
}