Program for evaluating the generating function for the number of involutions on n letters containing the pattern 231 exactly r times
/*This program finds the generating function I_r(x) for the number of
involutions on n letters containing 231 exactly r times. So the input of this
program is r and the output is the equation that I_r(x) satisfied.
This equation will appear in the data file I231r.txt*/
#include <stdio.h> /*open a program*/
#define MAXN 20 /*max length permutations*/
#define MAXSHAP 1000 /*max number of the shapes*/
int n; /*length current permutation in the algorithm*/
int prem[MAXN], bool_prem[MAXN]; /*array contains the current permutation
in the algorithm*/
int allshap[MAXSHAP][MAXN], /*List of the shapes*/
lallshap[MAXSHAP], /*Length every shape in the list*/
eshape[MAXSHAP], /*the list of e=E(shape)*/
ss[MAXN], /*array used to check the permutation is an involution*/
numshapes=0; /*The current number of the shapes in the algorithm*/
int equ[1000][3], /* the equation which I_r satisfied which every term in the
form equ[][0]*x^equ[][1]*I_equ[][2](x) just remark, the I_r(x)=x/(1-x)I_r(x)
does not contin in equ[][]*/
leq=0; /* the number of terms in the equation*/
int r; /* the number of occurrences of the pattern 231*/
/*To find the unique number E(shape). Given for the procedure the number of the
shape in the list*/
int finde(int s)
{
int i,/*index*/
fg,/*boolean*/
shape[MAXN],/*the shape which we want to find for it the E(shape)*/
ls=lallshap[s]; /*the length of the shape*/
for(i=0;i<ls;i++) {shape[i]=allshap[s][i]-1;} /*define the shape*/
fg=0; /*until yet E(shape) not exist*/
while (fg==0)
{
fg=1; for(i=0;i<ls;i++) if (shape[shape[i]]!=i) fg=0;
/*if the shape involution*/
if (fg==0) /*if not involution and to the right side of
the shape the number of length the shape +1, then stop*/
{for(i=ls;i>0;i--)
shape[i]=shape[i-1]; shape[0]=ls; ls++;}
}
return(ls); /*return the E(shape)*/
}
/*Put the term in the equation such that if there term like it just add it to
the coefficient, if not then put it as a new term*/
void putinequ(int a, int b, int c)
{
if (leq==0) {equ[leq][0]=a; equ[leq][1]=b; equ[leq][2]=c; leq++;} /*if the
list empty then just put it*/
else /*if not empty*/
{
int j=leq,i=0; /*new indexes to start new search if there
term like it*/
while (i<leq)
{
if
((equ[i][1]==b)&&(equ[i][2]==c)) j=i;
i++;
} /* if yes then
add the conficent, if not put it as the last term*/
if (j<leq) equ[j][0]++; else {equ[leq][0]=a; equ[leq][1]=b;
equ[leq][2]=c; leq++;}
}
}
/*Given for this procedure ms the number of occurrences 231 in the current
involution perm[] */
void terms(int ms)
{
int i,j,j1,j2,/*indexes*/
shape[MAXN], /* the shape */
ls=0, /* the length the shape*/
dd[MAXN],
ws,
itexist, /* if the shape exist in the old list*/
fg,fg2; /* boolean*/
for(i=0;i<n;i++) {if (ss[i]==1) dd[ls]=prem[i]+1; ls=ls+ss[i]; } /*defined the
shape*/
for(i=0;i<n;i++) shape[i]=i+1;
ws=1;
for(i=1;i<=n;i++)
{ for(j=0;j<ls;j++) if (dd[j]==i)
{shape[j]=ws; ws++;} } /*shape with numbers 1...ls*/
itexist=0; /*check if the shape exist in the list*/
for(i=0;i<numshapes;i++)
{
fg=0;
if(lallshap[i]==ls) /*the same length*/
{
fg=1; for(j=0;j<ls;j++) if
(allshap[i][j]!=shape[j]) fg=0; /* the same shape*/
}
if (fg==1) itexist=1; /*if yes stop*/
}
if (itexist==0) /*if the shape not exist in the list the continue*/
{
/* if the shapes divided to two small shapes, then we not add
it to the list*/
fg2=0;
for(i=3;i<ls-2;i++)
{
fg=1;
for(j1=0;j1<i;j1++)
for(j2=i;j2<ls;j2++)
if(shape[j1]>shape[j2]) fg=0;
if (fg==1) fg2=1;
}
if (fg2==0) /*if not dinvided, then add it*/
{
lallshap[numshapes]=ls; printf("%d)
",numshapes);
for(j=0;j<ls;j++)
{allshap[numshapes][j]=shape[j]; printf("%2d",shape[j]);}
printf(" ");
eshape[numshapes]=finde(numshapes); /*find
the unique number eshape*/
putinequ(1,eshape[numshapes],r-ms); /*put
it in the equation*/
numshapes++; /*number of the shapes
increasing by 1*/
}
}
}
int II() /* Return 1 if the current prem is involution , otherwise 0*/
{
int i;
for(i=0;i<n;i++) if(prem[prem[i]]!=i) return(0);
return(1);
}
void patterns() /*counting number of occurrences of 231 in the involution*/
{
int i,j,k,ma=0;
for(i=0;i<n;i++) ss[i]=0; /*no number joint in any occurrences of 231 in the
involution*/
for(j=0;j<n-2;j++)
for(k=j+1;k<n-1;k++)
for(i=k+1;i<n;i++)
if(ma<=r)
{
if ((prem[i]<prem[j])&&(prem[j]<prem[k])) { ma++;
ss[i]=1; ss[j]=1; ss[k]=1;}
/*add the numbers to the list which are containing in the occurrence*/
}
if ((ma<=r)&&(ma>=1)) terms(ma); /*if the number of occurrences between 1 and r
then continue to find the shape*/
}
void builtinvolutions() /*Procedure counting all the involutions in S_n*/
{
int fg,i,j;
fg=0; for(i=0;i<n;i++) fg=fg+bool_prem[i];
if (fg==n) patterns();
else
for(j=0;j<n;j++) if (bool_prem[j]==0)
{
i=0; while(prem[i]!=-1) i++;
bool_prem[j]=1; prem[i]=j;
bool_prem[i]=1; prem[j]=i;
builtinvolutions();
bool_prem[j]=0; bool_prem[i]=0; prem[i]=-1; prem[j]=-1;
}
}
void main()
{
int i,j,s;
FILE *inp;
/*introduction*/
printf("The program find the genrating function for the number of involutions in
the symmetric group on n letters containing\n");
printf(" a given number of occurrences of the pattern 231\n\n\n\n");
printf("First give me r=? the number of the occurrences of 231 :"); scanf("%d",&r);
/*Find the shapes up to length 2(r+1)*/
n=2*(r+1);
for(i=0;i<n;i++) { bool_prem[i]=0; prem[i]=-1; }
builtinvolutions();
/*Sort the equation such that I_r before I_{r-1}*/
for(i=0;i<leq-1;i++)
for(j=i+1;j<leq;j++)
if((equ[i][2]<equ[j][2])||((equ[i][2]==equ[j][2])&&(equ[i][1]<equ[j][1])))
{
s=equ[i][0]; equ[i][0]=equ[j][0]; equ[j][0]=s;
s=equ[i][1]; equ[i][1]=equ[j][1]; equ[j][1]=s;
s=equ[i][2]; equ[i][2]=equ[j][2]; equ[j][2]=s;
}
/*Put the output in the file and print it on the screen*/
inp=fopen("I231r=8.txt","w");
fprintf(inp,"The generating function for the number of involutions\n");
fprintf(inp," in S_n containing 231 exactly %d times is given by\n",r);
fprintf(inp," the following equation:\n");
if (r!=0) { printf("I_%d=x/(1-x)*I_%d",r,r);
fprintf(inp,"I_%d=x/(1-x)*I_%d",r,r); }
else { printf("I_%d=1+x/(1-x)*I_%d",r,r);
fprintf(inp,"I_%d=1+x/(1-x)*I_%d",r,r); }
for(i=0;i<leq;i++)
{
printf("+%d*x^%d*I_%d",equ[i][0],equ[i][1],equ[i][2]);
fprintf(inp,"+%d*x^%d*I_%d",equ[i][0],equ[i][1],equ[i][2]);
}
fclose(inp);
printf("\n"); fprintf(inp," \n \n");
}
Examples:
The generating function for the number of involutions
in S_n containing 231 exactly 0 times is given by
the following equation:I_0=1+x/(1-x)*I_0
The generating function for the number of involutions
in S_n containing 231 exactly 1 times is given by
the following equation:I_1=x/(1-x)*I_1+1*x^4*I_0
The generating function for the number of involutions
in S_n containing 231 exactly 2 times is given by
the following equation:I_2=x/(1-x)*I_2+1*x^4*I_1+1*x^6*I_0+2*x^5*I_0+1*x^4*I_0
The generating function for the number of involutions
in S_n containing 231 exactly 3 times is given by
the following equation: I_3=x/(1-x)*I_3+
1*x^4*I_2+1*x^6*I_1+2*x^5*I_1+1*x^4*I_1+1*x^8*I_0 +2*x^6*I_0+ 4*x^5*I_0
The generating function for the number of involutions
in S_n containing 231 exactly 4 times is given by
the following equation:I_4=x/(1-x)*I_4+1*x^4*I_3+1*x^6*I_2+2*x^5*I_2+1*x^4*I_2
+1*x^8*I_1 +2*x^6*I_1 +4*x^5*I_1 +1*x^10*I_0+4*x^7*I_0+6*x^6*I_0
The generating function for the number of involutions
in S_n containing 231 exactly 5 times is given by
the following equation:
I_5=x/(1-x)*I_5+1*x^4*I_4+1*x^6*I_3+2*x^5*I_3+1*x^4*I_3+1*x^8*I_2 +2*x^6*I_2
+4*x^5*I_2+1*x^10*I_1+4*x^7*I_1+6*x^6*I_1+1*x^12*I_0+2*x^8*I_0+6*x^7*I_0+8*x^6*I_0
The generating function for the number of involutions
in S_n containing 231 exactly 6 times is given by
the following equation:
I_6=x/(1-x)*I_6+1*x^4*I_5+1*x^6*I_4+2*x^5*I_4+1*x^4*I_4+1*x^8*I_3+2*x^6*I_3+4*x^5*I_3+1*x^10*I_2
+4*x^7*I_2+6*x^6*I_2+1*x^12*I_1+2*x^8*I_1+6*x^7*I_1+8*x^6*I_1+1*x^14*I_0+4*x^9*I_0+10*x^8*I_0
+9*x^7*I_0+4*x^6*I_0
The generating function for the number of involutions
in S_n containing 231 exactly 7 times is given by
the following equation:
I_7=x/(1-x)*I_7+1*x^4*I_6+1*x^6*I_5+2*x^5*I_5+1*x^4*I_5+1*x^8*I_4+2*x^6*I_4+4*x^5*I_4+1*x^10*I_3
+4*x^7*I_3+6*x^6*I_3+1*x^12*I_2+2*x^8*I_2+6*x^7*I_2+8*x^6*I_2+1*x^14*I_1+4*x^9*I_1+10*x^8*I_1
+9*x^7*I_1+4*x^6*I_1+1*x^16*I_0+2*x^10*I_0+9*x^9*I_0+5*x^8*I_0+17*x^7*I_0