Classes of partial matching words of length 6 and 7 according to pattern τ-avoiding matchings and the numbers #M_n(τ), 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 M_n.
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 a₁a₂...a_m 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 MM_n(τ). 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	#M₁(τ)	#M₂(τ)	#M₃(τ)	#M₄(τ)	#M₅(τ)	#M₆(τ)	#M₇(τ)
123455	1	3	15	105	0	0	0
123456	1	3	15	105	945	0	0
123445,123454	1	3	15	105	315	693	1287
123435,123453	1	3	15	105	441	1683	5863
123434,123443	1	3	15	70	315	1386	6006
123424	1	3	15	77	396	2057	10790
123425,123452	1	3	15	105	513	2387	10959
123345	1	3	15	105	567	2772	12870
123442	1	3	15	77	432	2475	14560
123414	1	3	15	81	450	2547	14754
123415,123451	1	3	15	105	561	2931	15487
123344	1	3	15	70	378	2376	17160
123234,123243,123324,123342,123423,123432	1	3	15	84	495	3003	18564
123245	1	3	15	105	621	3564	20085
122344,123244	1	3	15	77	441	2871	21203
123441	1	3	15	81	484	3179	21664
123134,123143,123413	1	3	15	87	539	3503	23594
121344,123144	1	3	15	81	491	3341	25465
123145	1	3	15	105	657	4066	25643
123314,123341,123431	1	3	15	87	555	3757	26508
123124*,123142,123214*,123241,123412,123421*	1	3	15	90	594	4165	30454
112344	1	3	15	85	542	3866	30681
122345	1	3	15	105	720	4950	34411
123132,123213	1	3	14	83	570	4318	35068
121342	1	3	15	93	638	4647	35263
122314	1	3	15	93	644	4771	37004
122341	1	3	15	93	646	4818	37744
121324	1	3	15	93	646	4829	38072
123123,123312,123321	1	3	14	84	594	4719	40898
121345	1	3	15	105	745	5456	41086
123231	1	3	14	84	595	4750	41541
121332,122313	1	3	14	84	595	4759	41913
121323	1	3	14	84	596	4787	42440
121234,122134	1	3	15	95	684	5346	44293
122334,122343	1	3	15	91	639	5115	46111
112334,112343,121334,121343	1	3	15	93	669	5471	50219
122331	1	3	14	85	622	5266	50299
112323,112332,121233,122133	1	3	14	85	624	5334	51876
112345	1	3	15	105	800	6513	55971
112233	1	3	14	86	648	5760	58896
112324,112342	1	3	15	97	745	6563	65063
112234	1	3	15	99	784	7146	73341

Pattern	#M₁(τ)	#M₂(τ)	#M₃(τ)	#M₄(τ)	#M₅(τ)	#M₆(τ)	#M₇(τ)	#M₈(τ)
1234566	1	3	15	105	945	0	0
1234567	1	3	15	105	945	10395	0
1234556,1234565	1	3	15	105	945	3465	9009
1234545,1234554	1	3	15	105	630	3465	18018
1234546,1234564	1	3	15	105	945	4851	21879
1234535	1	3	15	105	693	4356	26741
1234455	1	3	15	105	630	4158	30888
1234536,1234563	1	3	15	105	945	5643	31031
1234553	1	3	15	105	693	4752	32175
1234525	1	3	15	105	729	4950	33111
1234456	1	3	15	105	945	6237	36036
1233455,1234355	1	3	15	105	693	4851	37323
1234526,1234562	1	3	15	105	945	6171	38103
1234515	1	3	15	105	753	5388	38527
1234345,1234354,1234435,1234453,1234534,1234543	1	3	15	105	756	5445	39039
1234552	1	3	15	105	729	5324	41327
1232455,1234255	1	3	15	105	729	5401	43433
1234516,1234561	1	3	15	105	945	6555	43815
1234245,1234524,1234254	1	3	15	105	783	5929	45539
1234356	1	3	15	105	945	6831	46332
1234551	1	3	15	105	753	5742	46781
1234155,1231455	1	3	15	105	753	5805	48611
1234425,1234452,1234542	1	3	15	105	783	6105	48841
1234514	1	3	15	105	801	6295	50221
1223455	1	3	15	105	765	5962	50258
1234154	1	3	15	105	801	6295	50402
1234145	1	3	15	105	801	6295	50427
1234256	1	3	15	105	945	7227	52858
1234235,1234325,1234352,1234523,1234532,1234253	1	3	15	105	810	6534	54145
1234415	1	3	15	105	801	6463	55020
1234451,1234541	1	3	15	105	801	6463	55226
1213455	1	3	15	105	785	6350	55575
1234243,1234324	1	3	15	98	747	6270	56134
1234156	1	3	15	105	945	7515	58044
1234513	1	3	15	105	825	6827	58546
1234153	1	3	15	105	825	6834	58698
1234135	1	3	15	105	825	6849	59040
1232453	1	3	15	105	837	7018	60411
1234315	1	3	15	105	825	6929	60796
1234351	1	3	15	105	825	6936	60889
1234531	1	3	15	105	825	6951	61276
1234234,1234423,1234432	1	3	15	98	756	6534	61347
1234342	1	3	15	98	756	6545	61750
1232443,1233424	1	3	15	98	756	6545	61867
1233425	1	3	15	105	837	7084	62023
1232434	1	3	15	98	756	6556	62231
1234143	1	3	15	99	771	6680	62266
1233452	1	3	15	105	837	7106	62634
1234314	1	3	15	99	772	6704	62713
1232435	1	3	15	105	837	7106	62777
1123455	1	3	15	105	814	6914	63871
1234134	1	3	15	99	773	6760	64227
1233456	1	3	15	105	945	7920	64350
1234152	1	3	15	105	840	7212	64827	602584
1234251	1	3	15	105	840	7212	64827	602359
1234125,1234215,1234512,1234521	1	3	15	105	840	7212	64932
1231434	1	3	15	99	773	6799	65648
1233445,1233454	1	3	15	105	819	7029	66495
1231453	1	3	15	105	849	7358	66510
1233414	1	3	15	99	778	6901	67022
1231435	1	3	15	105	849	7380	67385
1231443	1	3	15	99	779	6924	67444
1234413,1234431	1	3	15	99	778	6921	67575
1233415	1	3	15	105	849	7427	68267
1234341	1	3	15	99	779	6953	68303
1233442	1	3	15	98	765	6842	68458
1233451	1	3	15	105	849	7436	68643
1234214	1	3	15	100	796	7109	68706
1234142	1	3	15	100	796	7110	68740
1223434,1223443,1232344,1233244	1	3	15	98	765	6864	69342
1213424	1	3	15	100	794	7097	69370
1232345,1233245	1	3	15	105	855	7524	69498
1232456	1	3	15	100	797	7185	70928
1231424	1	3	15	100	797	7181	70944
1234124	1	3	15	100	797	7185	70958
1231452	1	3	15	105	861	7640	71062
1223445,1223454,1232445,1232454	1	3	15	105	837	7359	71123
1223414	1	3	15	100	798	7204	71303
1232414	1	3	15	100	798	7206	71364
1234241	1	3	15	100	798	7225	71971
1232415	1	3	15	105	861	7685	72329
1231344	1	3	15	99	782	7095	72376
1231425	1	3	15	105	861	7684	72471
1213442	1	3	15	100	800	7265	72584
1123434,1123443,1213443,1213434	1	3	15	99	783	7117	72757
1232451	1	3	15	105	861	7703	72871
1231442	1	3	15	100	801	7296	73217
1231345	1	3	15	105	865	7751	73410
1233441	1	3	15	99	787	7192	73575
1234412,1234421	1	3	15	100	803	7343	73896
1233144	1	3	15	99	788	7225	74480
1232413	1	3	15	101	819	7505	74819
1232143	1	3	15	101	819	7506	74864
1223344	1	3	15	98	774	7128	74880
1231342,1234132,1234213	1	3	15	101	819	7509	74987
1231432	1	3	15	101	819	7513	75143
1232134	1	3	15	101	819	7513	75147
1231324	1	3	15	101	819	7513	75152
1213454,1213445,1231445,1231454	1	3	15	105	849	7619	75167
1233145	1	3	15	105	865	7821	75222
1231456	1	3	15	105	945	8395	75256
1231243	1	3	15	101	820	7555	76227
1232441	1	3	15	100	805	7446	76924
1223441	1	3	15	100	805	7452	77202
1212344,1221344,1223144,1231244,1232144,1213244	1	3	15	100	805	7461	77630
1123344,1213344	1	3	15	99	791	7359	77955
1233124,1233142,1233241	1	3	15	101	823	7649	78251	861239
1231423	1	3	15	101	823	7649	78251	861254
1231234,1233214,1233412,1233421,1234123,1234312,1234321	1	3	15	101	823	7653	78403
1232314	1	3	15	101	823	7654	78473
1232341	1	3	15	101	823	7658	78629
1234231	1	3	15	101	823	7658	78630
1232431	1	3	15	101	823	7658	78647
1231245,1232145	1	3	15	105	875	8047	78928
1123445,1123454	1	3	15	105	861	7881	79433
1213452	1	3	15	105	880	8134	79454
1213425	1	3	15	105	880	8142	80314
1223415	1	3	15	105	880	8185	81455
1223451	1	3	15	105	880	8194	81755
1123424	1	3	15	101	828	7867	84360
1223456	1	3	15	105	945	8800	84669
1223435,1223453	1	3	15	105	873	8195	85319
1213423	1	3	15	102	847	8094	86068
1123442	1	3	15	101	832	7977	86566
1223413	1	3	15	102	850	8184	87886
1213432	1	3	15	102	850	8186	87963
1213342	1	3	15	102	850	8186	87991
1213324	1	3	15	102	850	8186	87998
1223143	1	3	15	102	850	8187	88047
1122344,1123244	1	3	15	101	833	8031	88139
1223134	1	3	15	102	850	8190	88168
1213243	1	3	15	102	850	8193	88292
1213234	1	3	15	102	850	8193	88295
1223145	1	3	15	105	894	8558	88436
1123435,1123453,1213453,1213435	1	3	15	105	881	8379	88447
1213456	1	3	15	105	945	8945	88677
1213245	1	3	15	105	894	8573	89082
1223431	1	3	15	102	853	8297	90822
1223314	1	3	15	102	853	8308	91291
1223341	1	3	15	102	853	8311	91422
1123234,1123243,1123324,1123342,1123423,1123432	1	3	15	102	853	8319	91836
1223345	1	3	15	105	891	8624	92898
1212345,1221345	1	3	15	105	905	8893	95513
1123345,1213345	1	3	15	105	897	8773	95597
1123425,1123452	1	3	15	105	897	8803	96607
1123456	1	3	15	105	945	9244	96995
1212334,1212343,1221334,1221343	1	3	15	103	881	8887	102305
1123245	1	3	15	105	909	9126	102903
1122334,1122343	1	3	15	103	883	8967	104515
1122345	1	3	15	105	920	9450	109747

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*/
}

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.

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