###################################################################### ##P1234: Save this file as P1234 # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read P123 # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #Created: June-Aug. 2012 with(combinat): print(`Created: June-Aug. 2012`): print(` This is P1234, one of the numerous Maple packages `): print(`accompanying Brian Nakamura and Doron Zeilberger's article: `): print(`"Using Noonan-Zeilberger Functional Equations `): print(`to enumerate (in Polynomial Time!) Generalized Wilf classes"`): print(`available from:`): print(` http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/Gwilf.html .`): print(): print(``): print(`Please report bugs to zeilberg at math dot rutgers dot edu`): print(``): print(`The most current version of this package `): print(` is available from`): print(`http://www.math.rutgers.edu/~zeilberg/tokhniot/P1234 .`): print(`-------------------------------------------------------------`): print(`For a list of the Checking procedures type ezraC();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`-------------------------------------------------------------`): print(`-------------------------------------------------------------`): print(`For a list of the supporting procedures type ezra1();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`-------------------------------------------------------------`): print(`-------------------------------------------------------------`): print(`For a list of the MAIN procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`-------------------------------------------------------------`): ezraC:=proc() if args=NULL then print(` The checking procedures are: CheckPn, PnDirect `): print(` u3Gessel `): else ezra(args): fi: end: ezra1:=proc() if args=NULL then print(` The supporting procedures are: `): print(` PqLy, PqLyT, TrimTriple, TrimTriples, Wt, Yeladim, YeladimT `): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are:`): print(` fn, L10`): print(` Pn, Seq1PC, Seqs `): print(` `): elif nops([args])=1 and op(1,[args])=CheckPn then print(`CheckPn(N):Checks Pn(n,q,y,z) for n from 1 to N `): print(`Try: `): print(` CheckPn(8); `): elif nops([args])=1 and op(1,[args])=fn then print(`fn(n,q): the weight-enumerator of S_n according to the weight`): print(`q^(#1234)`): elif nops([args])=1 and op(1,[args])=L10 then print(`L10(q): The sequence of length 10 whose n-th entry is the weight-enumerator`): print(`of S_n according to the weight q^(#Of 1234 patterns). Try:`): print(`L10(q);`): elif nops([args])=1 and op(1,[args])=Pn then print(`Pn(n,q,y,z):The weight-enumerator of perms of {1, ..., n}`): print(`according to the weight Wt(pi,q,y,z) ...`): print(`try: `): print(`Pn(5,q,y,z); `): elif nops([args])=1 and op(1,[args])=PnDirect then print(`PnDirect(n,q,y,z):The weight-enumerator of perms of {1, ..., n}`): print(`according to the weight Wt(n,q,y,z) `): print(`computed directly. FOR CHECKING PURPOSES ONLY, VERY SLOW!`): print(`try: `): print(`PnDirect(5,q,y,z); `): elif nops([args])=1 and op(1,[args])=PqL then print(` PqL(q,L1,L2):The value of P_n(n,q,y,z) where n=nops(L1)=nops(L2)`): print(`and one plugs in for [y[1], ..., y[n]] the`): print(`values of L1, and for [z[1], ..., z[n]] the values of L2 try:`): print(`PqL(q,[y1,y2,y3,y4],[z1,z2,z3,z4]);`): elif nops([args])=1 and op(1,[args])=PqLy then print(`Like PqL(q,L1,L2), but using Yeladim(L1,L2,q)`): print(`Try:`): print(`PqLy(q,[y1,y2,y3],[z1,z2,z3]);`): elif nops([args])=1 and op(1,[args])=PqLyT then print(`PqLyT(q,L1,L2,r):Like PqLy but only interested in terms up`): print(`to the r-th power of q`): print(`Try:`): print(`PqLyT(q,[1,1,1,1],[1,1,1,1],1);`): elif nops([args])=1 and op(1,[args])=Seq1PC then print(`The pre-computed first 60 terms of the sequence`): print(`enumerating permutations of length n with exactly`): print(`one occurrence of the pattern 1234, try:`): print(`Seq1PC();`): elif nops([args])=1 and op(1,[args])=Seqs then print(`Seqs(N,R): The lists whose R+1 lists whose (r+1)-th list`): print(`is the first N members (starting at n=1)`): print(`number of permutations with exactly r occurrence of 1234,`): print(`try: Seqs(8,3);`): elif nops([args])=1 and op(1,[args])=TrimTriple then print(`TrimTrible(P,q,r): Given a Triple P=[coeff,L1,L2]`): print(`where coeff is a power of q, `): print(` and L1, L2 are lists of powers of q, of the same length`): print(`returns the `): print(`empty set if coeff has power larger than r,`): print(`and otherwise returns the singleton`): print(`{[coeff,L1a,L2a]} where L1a is L1 with`): print(`any power larger than q^(r+1) is replaced by q^(r+1)`): print(`and ditto for L2a and L2`): print(`For example, try: `): print(`TrimTriple([q,[1,1,q,q,q^3,q^4,q^4],[1$7]],q,2);`): elif nops([args])=1 and op(1,[args])=TrimTriples then print(`TrimTriples(S,q,r): the set of trimmed triples coming from the`): print(`set of triples S with respect to the power r, try:`): print(`TrimTriples({[q,[1,1,q,q,q^3,q^4,q^4]]},q,1);`): elif nops([args])=1 and op(1,[args])=u3Gessel then print(`u3Gessel(n): Ira Gessel's single-sum formula for the number`): print(`of 1234-avoiding permutations of length n.`): print(`For checking purposes only. Try:`): print(` u3Gessel(20);`): elif nops([args])=1 and op(1,[args])=Wt then print(`Wt(pi,q,y,z): the weight of a permutation pi according to`): print(`q^(#1234)*Product(y[i]^#(123,1=i)*z[1]^#(12,1=i),i=1..n)`): print(`Try: `): print(`Wt([1,2,3,4],q,y,z); `): elif nops([args])=1 and op(1,[args])=Yeladim then print(`Yeladim(L1,L2,q): the children of the lists L1,L2`): print(`Try: Yeladim([1,1,1],[1,1,1],q);`): elif nops([args])=1 and op(1,[args])=YeladimT then print(`YeladimT(L1,L2,q,r): the trimmed children of the list L1,L2`): print(`with respect to the power r.`): print(`Try: YeladimT([1,q^3,q^5],[1,q,q^3],q,2);`): else print(`There is no ezra for`,args): fi: end: #fn(n,q): the weight-enumerator of S_n according to the weight #q^(#1234) fn:=proc(n,q) local gu,i,y,z: gu:=Pn(n,q,y,z): sort(subs({seq(y[i]=1,i=1..n), seq(z[i]=1,i=1..n)},gu)): end: #Pn(n,q,y,z):The weight-enumerator of perms of {1, ..., n} #according to the weight Wt(pi) Pn:=proc(n,q,y,z) local i,j,gu: option remember: if n=1 then RETURN(1): else gu:=Pn(n-1,q,y,z): expand(add(z[i]^(n-i)*subs( { seq(y[j]=q*y[j+1],j=i..n-1), seq(z[j]=y[i]*z[j+1],j=i..n-1) },gu),i=1..n)): fi: end: #Wt(pi,q,y,z): the weight of a permutation pi according to #123*y[1]#(12,i=1)*y[2]#(12,1=2) ... #Try #Wt([1,2,3,4],q,y,z); Wt:=proc(pi,q,y,z) local n,i1,i2,i3,i4,mu: n:=nops(pi): mu:=1: for i1 from 1 to n do for i2 from i1+1 to n do for i3 from i2+1 to n do for i4 from i3+1 to n do if pi[i1]n then print(`Bad input`): RETURN(FAIL): fi: if n=1 then RETURN(1): else #I am here gu:=YeladimT(L1,L2,q,r): mu:=expand(add(gu[i][1]*PqLyT(q,gu[i][2],gu[i][3],r),i=1..nops(gu))): mu:=add(coeff(mu,q,i)*q^i,i=0..r): RETURN(mu): fi: end: #TrimTriple(P,q,r): Given a Triple P=[coeff,L1,L2] #where coeff is a power of q, #and L1, L2 are lists of powers of q, returns the #empty set if coeff has power larger than r, #and otherwise returns the singleton #{[coeff,L1,L2]} where L1 is L with #any power larger than q^(r+1) is replaced by q^(r+1) #and ditto for L2 #For example, try: #TrimTriple([q,[1,1,q,q,q^3,q^4,q^4],[1,1,q,q^2,q^4,q^5],q,2); TrimTriple:=proc(P,q,r) local c,L1,L2,L1a,L2a,i: c:=P[1]: L1:=P[2]: L2:=P[3]: if degree(c,q)>r then RETURN({}): fi: L1a:=[]: for i from 1 to nops(L1) do if degree(L1[i],q)>r+1 then L1a:=[op(L1a),q^(r+1)]: else L1a:=[op(L1a),L1[i]]: fi: od: L2a:=[]: for i from 1 to nops(L2) do if degree(L2[i],q)>r+1 then L2a:=[op(L2a),q^(r+1)]: else L2a:=[op(L2a),L2[i]]: fi: od: {[c,L1a,L2a]}: end: #TrimTriples(S,q,r): the set of trimmed pairs coming from the #set of pairs S with respect to the power r, try: #TrimTripless({[q,[1,1,q,q,q^3,q^4,q^4]]},q,1); TrimTriples:=proc(S,q,r) local P: {seq(op(TrimTriple(P,q,r)), P in S)}: end: #Yeladim(L1,L2,q): the children of the lists L1,L2 #Try: Yeladim([1,1,1],[1,1,1],q); Yeladim:=proc(L1,L2,q) local n,i,j: n:=nops(L1): if n<>nops(L2) then print(`Bad input`): RETURN(FAIL): fi: [seq([L2[i]^(n-i),[op(1..i-1,L1),seq(q*L1[j],j=i+1..n)], [op(1..i-1,L2),seq(L1[i]*L2[j],j=i+1..n)] ],i=1..n)]; end: #YeladimT(L1,L2,q,r): the trimmed children of the lists L1,L2 #with respect to the power r. #Try: YeladimT([1,q^3,q^5],[1,q,q^2],q,2); YeladimT:=proc(L1,L2,q,r): TrimTriples(Yeladim(L1,L2,q),q,r): end: #The pre-computed first 60 terms of the sequence #enumerating permutations of length n with exactly #one occurrence of the pattern 1234, try: #Seq1PC(); Seq1PC:=proc(): [0, 0, 0, 1, 12, 102, 770, 5545, 39220, 276144, 1948212, 13817680, 98679990, 710108396, 5150076076, 37641647410, 277202062666, 2056218941678, 15358296210724 , 115469557503753, 873561194459596, 6647760790457218, 50871527629923754, 391345137795371013, 3025568471613091692, 23501724670464335914, 183370520135071994536, 1436795093911521996331, 11303188383039278887124, 89260541978520331533700, 707437404671874557268114, 5626126164818258630374045, 44890241684861288556544076, 359292558147818914062905054, 2884266669622763402468701512, 23219594217700126162520486007, 187434994793367078497274016728, 1516951863432717428865342122514, 12307486811260788573138997510158, 100091622070561248038115522094299, 815856655310848928578612531715452, 6664649278732787947706840950747342, 54556925760523407881545676405013408, 447502671399799218201374470592229908, 3677735825253348084543449338636800582, 30281156066331736463347959494392409358, 249770415890730744157727067651222087912, 2063751411787705526591393085398259906294, 17080254371002108847763233225265546563922, 141587847621622659073468460280075352694446, 1175513889140825068064271227763908680579396, 9774090674960633543231851429280816436250211, 81385980818954917977714389436691979144342332, 678619575253521928628465126027915180667541928, 5666131159257662124927798395714589959734397534, 47370851152873309016702311042815057403665160213, 396535282237070465951199610831966182410281984016, 3323388874367547430998197230881721747956318469392, 27886406504332702747838608145623422551792005719924, 234261080605837210966025910570764305425250198302448]: end: #u3Gessel(n): Ira Gessel's single-sum formula for the number #of 1234-avoiding permutations of length n. #For checking purposes only. Try: # u3Gessel(20); u3Gessel:=proc(n) local k: 2*add(binomial(2*k,k)*binomial(n,k)^2*(3*k^2+2*k+1-n-2*k*n)/(k+1)^2/(k+2)/ (n-k+1),k=0..n): end: #L10(q): The sequence of length 10 whose n-th entry is the weight-enumerator #of S_n according to the weight q^(#Of 1234 patterns). Try: #L10(q); L10:=proc(q): [1, 2, 6, q+23, q^5+4*q^2+12*q+103, q^15+5*q^9+8*q^6+12*q^5+6*q^4+10*q^3+63*q^2 +102*q+513, q^35+6*q^25+10*q^19+18*q^16+12*q^15+13*q^13+24*q^11+32*q^10+72*q^9+ 10*q^8+46*q^7+142*q^6+116*q^5+146*q^4+196*q^3+665*q^2+770*q+2761, q^70+7*q^55+ 12*q^45+15*q^41+10*q^39+8*q^36+28*q^35+40*q^32+41*q^29+10*q^28+24*q^27+44*q^26+ 84*q^25+24*q^24+89*q^23+12*q^21+142*q^20+136*q^19+96*q^18+115*q^17+333*q^16+156 *q^15+112*q^14+312*q^13+199*q^12+600*q^11+573*q^10+804*q^9+503*q^8+885*q^7+1782 *q^6+1204*q^5+2148*q^4+2477*q^3+5982*q^2+5545*q+15767, q^126+8*q^105+14*q^90+21 *q^85+12*q^80+19*q^75+10*q^74+68*q^71+12*q^70+20*q^66+50*q^65+40*q^62+10*q^61+ 46*q^59+40*q^58+94*q^57+44*q^56+152*q^55+60*q^53+16*q^52+28*q^51+48*q^50+94*q^ 49+161*q^48+12*q^47+112*q^46+364*q^45+30*q^44+157*q^43+124*q^42+302*q^41+158*q^ 40+440*q^39+54*q^38+242*q^37+408*q^36+400*q^35+272*q^34+567*q^33+746*q^32+220*q ^31+620*q^30+948*q^29+502*q^28+998*q^27+928*q^26+1590*q^25+1253*q^24+1586*q^23+ 640*q^22+1323*q^21+3081*q^20+2102*q^19+2776*q^18+2718*q^17+4679*q^16+3006*q^15+ 3004*q^14+5586*q^13+5312*q^12+8585*q^11+7775*q^10+9533*q^9+9599*q^8+11533*q^7+ 19936*q^6+13188*q^5+25190*q^4+25886*q^3+49748*q^2+39220*q+94359, q^210+9*q^182+ 16*q^161+28*q^155+14*q^146+22*q^140+12*q^136+84*q^135+10*q^130+35*q^129+8*q^127 +12*q^126+59*q^125+60*q^121+12*q^120+60*q^116+158*q^115+40*q^112+187*q^110+56*q ^109+24*q^107+72*q^106+142*q^105+15*q^104+80*q^103+240*q^101+116*q^100+216*q^97 +50*q^96+161*q^95+104*q^94+8*q^93+300*q^92+340*q^91+246*q^90+108*q^89+16*q^88+ 406*q^87+140*q^86+594*q^85+422*q^84+56*q^83+160*q^82+299*q^81+265*q^80+263*q^79 +747*q^78+68*q^77+350*q^76+942*q^75+424*q^74+828*q^73+586*q^72+1426*q^71+302*q^ 70+779*q^69+372*q^68+737*q^67+1210*q^66+1320*q^65+870*q^64+953*q^63+1422*q^62+ 994*q^61+1208*q^60+2104*q^59+1824*q^58+2534*q^57+1846*q^56+3908*q^55+992*q^54+ 2116*q^53+1916*q^52+1548*q^51+4140*q^50+3726*q^49+3816*q^48+2594*q^47+5228*q^46 +6714*q^45+2831*q^44+6043*q^43+4618*q^42+7195*q^41+6875*q^40+8640*q^39+5268*q^ 38+8688*q^37+9190*q^36+9042*q^35+12164*q^34+12342*q^33+14354*q^32+10686*q^31+ 16001*q^30+18642*q^29+15216*q^28+20286*q^27+20598*q^26+29569*q^25+25212*q^24+ 25486*q^23+24894*q^22+30289*q^21+49273*q^20+36084*q^19+48938*q^18+46271*q^17+ 64086*q^16+51594*q^15+55779*q^14+82752*q^13+85736*q^12+102866*q^11+100201*q^10+ 113954*q^9+132620*q^8+130920*q^7+210663*q^6+142550*q^5+260505*q^4+244233*q^3+ 396642*q^2+276144*q+586590]: end: