Program finding the genrating finction for the number of permutations
in S_n(132,tau)

This programing find the generating function of the number 132-avoiding permutations in S_n(tau).
The arguments of the program is two:
        The first:  is the pattern xtau in the form of array
        The second: is the length of xtau.

restart:

genfunction132:=proc()
local xtau,pr,maxp,imaxp,minp,decomtau,lendecomtau,xdelta,xtheta,lxdelta,lxtheta,gdelta,gtheta,v, ff, k,m,i,j,i1,j1;
xtau:=args[1]: k:=args[2]:
if (k=0) then RETURN(0) fi:
if (k=1) then RETURN(1) fi:
if (k=2) then RETURN(1/(1-x)) fi:
for i from 1 by 1 to k do pr[i]:=xtau[i]: od:
i1:=1: m:=-1: decomtau[m]:=([]):
for i from 1 by 1 to k do
      if (i1<=k) then
           maxp:=0: for j from i1 by 1 to k do
                                  if (pr[j]>maxp) then maxp:=pr[j]: imaxp:=j: fi:
                           od:
           m:=m+1:
          for j from i1 by 1 to imaxp do decomtau[m][j+1-i1]:=pr[j]: od:
          lendecomtau[m]:=imaxp+1-i1:
     fi:
i1:=imaxp+1: od:
for i from 0 to m do minp[i]:=k:
   for j from 1 to lendecomtau[i] do
           if (decomtau[i][j]<minp[i]) then minp[i]:=decomtau[i][j]: fi:
od: od:
for i from 1 by 1 to lendecomtau[0]-1 do xdelta[0][i]:=decomtau[0][i]-minp[0]+1: od:
lxdelta[0]:=lendecomtau[0]-1:
if (m=0) then ff:=genfunction132(xdelta[0],lxdelta[0]): ff:=simplify(1/(1-x*ff)): RETURN(ff): fi:
for i1 from 1 by 1 to m do
     j1:=0: for i from 0 by 1 to i1 do
                  for j from 1 by 1 to lendecomtau[i] do
                       j1:=j1+1: xdelta[i1][j1]:=decomtau[i][j]-minp[i1]+1:
              od: od:
     lxdelta[i1]:=j1: od:
for i1 from 0 by 1 to m do
   j1:=0:  for i from i1 by 1 to m do for j from 1 by 1 to lendecomtau[i] do
                     j1:=j1+1: xtheta[i1][j1]:=decomtau[i][j]: od: od:
   lxtheta[i1]:=j1: od:
gdelta[-1]:=0: for i from 0 by 1 to m-1 do gdelta[i]:=genfunction132(xdelta[i],lxdelta[i]): od:
gdelta[m]:=v: gtheta[0]:=v:
for i from 1 by 1 to m do gtheta[i]:=genfunction132(xtheta[i],lxtheta[i]): od:
ff:=1: for i from 0 by 1 to m do ff:=ff+x*(gdelta[i]-gdelta[i-1])*gtheta[i]: od:
ff:=simplify(solve(v=ff,v)); RETURN(ff):
end:
 

Avoiding:=proc()
print(" Programming: the genenrating function of the numebr 132-avoiding permutations such that also tau-avoiding ");
print(" By ");
print(" Toufik Mansour ");
lprint(" This programming contain the following functions: ");
lprint("1) Avoiding : The menu,");
lprint("2) Avoiding132(k,tau) :To find the generating function for |S_n(132,tau)|. An exmaple let k=4 and tau=array([1,2,3,4]) then Avoiding132(k,tau),");
lprint("3) Tableavoiding132(k) : Table of all the generating functions for |S_n(132,tau)| where tau in S_k,");
lprint("4) WC132(k) : The number Wilf classes in Tableavoiding132(k).");
lprint("5) LWC132(k) : The list of Wilf classes in Tableavoiding132(k).");
end:

Avoiding132:=proc() local xtau,k: xtau:=args[1]: k:=args[2]:
print("The generating function of the sequence (",S[n](132,args[1] ),") n=0,1,2,... is equal to"); print(genfunction132(xtau,k)); end:

daa:=proc() local a,n,i,c: a:=args[1]: n:=args[2]: c:="(": for i from 1 by 1 to n-1 do c:=cat(c,a[i],","): od: c:=cat(c,a[n],")"):RETURN(c): end:

Tableavoiding132:=proc() local pp,k,i,j,s,f: k:=args[1]: j:=0: with(combinat, permute): pp:=permute(k):
for i from 1 by 1 to k! do s:=pp[i]: if isprem132(s,k)=1 then j:=j+1: f:=genfunction132(s,k):
lprint(j,"The generating function of", S[n](132,daa(s,k)),"is",f); fi:  od: RETURN():
end:

isprem132:=proc()
local a,k,i1,i2,i3: a:=args[1]: k:=args[2]: if (k<3) then RETURN(1); fi:
for i1 from 1 by 1 to k-2 do for i2 from i1+1 by 1 to k-1 do for i3 from i2+1 by 1 to k do
    if (a[i1]<a[i3]) then if (a[i3]<a[i2]) then RETURN(0): fi: fi: od: od: od: RETURN(1): end:

WC132:=proc()
local pp,k,i,j,s,f,aff,laff,cf: k:=args[1]: j:=0: laff:=0:
with(combinat, permute): pp:=permute(k):
for i from 1 by 1 to k! do
s:=pp[i]: if isprem132(s,k)=1 then  f:=genfunction132(s,k): cf:=1:
                                                            for j from 1 by 1 to laff do if (simplify(normal(rationalize(aff[j]-f)))=0) then cf:=0: fi: od:
                                                           if (cf=1) then laff:=laff+1: aff[laff]:=f:  fi:  fi:
od: RETURN(laff): end:

LWC132:=proc()
local pp,k,i,j,s,f,aff,laff,cf: k:=args[1]: j:=0: laff:=0:
with(combinat, permute): pp:=permute(k):
for i from 1 by 1 to k! do
   s:=pp[i]:
   if isprem132(s,k)=1 then  f:=genfunction132(s,k): cf:=1:
                                               for j from 1 by 1 to laff do if (simplify(aff[j]-f)=0) then cf:=0: fi: od:
                                               if (cf=1) then laff:=laff+1: aff[laff]:=f: lprint(laff,"(",i,")",factor(f)): fi:
   fi:
od: RETURN(laff): end:

> #--------------------------------------------------------------------------
>#################### Exmaples
>Avoiding();

> Avoiding132( array([5,1,2,3,4]),5);

> Tableavoiding132(1);

> Tableavoiding132(2);

> Tableavoiding132(3);

> Tableavoiding132(4);

com11:=proc() local a,b,k,i,r: a:=args[1]: b:=args[2]: k:=args[3]: r:=0: for i from 1 by 1 to k do if (a[i]=b[i]) then r:=r+1: fi: od: if (r=k) then RETURN(1): else RETURN(0): fi: end:

AWC132:=proc() local pp,k,i,j,s,f,f1,f2,a1,a2,ll,m,wc,ld: k:=args[1]: j:=0: ll:=0: ld:=25: with(combinat, permute): pp:=permute(k):  for i from 1 by 1 to k! do s:=pp[i]: if isprem132(s,k)=1 then  f:=simplify(genfunction132(s,k)): f1:=numer(f): f2:=denom(f): ll:=ll+1: for j from 1 by 1 to ld do  a1[ll][j]:=subs(x=j,f1): a2[ll][j]:=subs(x=j,f2): od: fi: od: for i from 1 by 1 to ll do m[i]:=1: for j from 1 by 1 to i-1 do if ((com11(a1[i],a1[j],ld)=1) and (com11(a2[i],a2[j],ld)=1)) then m[i]:=0 fi: od: od:  wc:=0: for i from 1 by 1 to ll do wc:=wc+m[i]: od: lprint("the number of clases of Avoiding 132 and pattern from s",k,"is =",wc):  end: