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: