###################################################################### ## F12345 Save this file as F12345 to use it, stay in the # ## same directory, get into Maple (by typing: maple ) # ## and then type: read F12345 # ## Then follow the instructions given there # ## # ## Written by Brian Nakamura and Doron Zeilberger, # ## Rutgers University , # ## [bnaka, zeilberg] at math dot rutgers dot edu. # ###################################################################### print(`First Written: August, 2012: tested for Maple 15 `): print(`Version of August, 2012 `): print(): print(`This is F12345, A Maple package`): print(`accompanying Brian Nakamura and Doron Zeilberger's article: `): print(`"Using the Noonan-Zeilberger Functional Equations `): print(`to enumerate (in Polynomial Time!) Generalized Wilf classes`): print(): print(`The most current version is available at:`): print(` http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/Gwilf.html .`): print(`Please report all bugs to: zeilberg at math dot rutgers dot edu .`): print(): print(`For general help, and a list of the MAIN functions,`): print(` type "ezra();". For specific help type "ezra(procedure_name);" `): print(): ezra:=proc() if args=NULL then print(` F12345: A Maple package for using schemes to enumerate `): print(`the number of n-permutations with 0,1,2,3, etc. occurrences`): print(`of the pattern 12345 `): print(`The MAIN procedures are`): print(` F12345r, Seqs12345 `): elif nargs=1 and args[1]=F12345r then print(`F12345r(Lx,Ly,Lz,q): Given lists of positive integers of size r+2`): print(`and a variable q, finds `): print(`P_n(1 (repeated Lx[1] times),q (repeated Lx[2] times), ..., q^(r+1) `): print(` (repeated Lx[r+2] times); 1 (repeated Ly[1] times), q (repeated Ly[2] times), `): print(` ..., q^(r+1) (repeated Ly[r+2] times); 1 (repeated Lz[1] times), `): print(` q (repeated Lz[2] times), ..., q^(r+1) (repeated Lz[r+2] times) )`): print(` (analogous to the approach for 123 and 1234 described in the accompanying paper) `): print(`Try, for example: `): print(`F12345r([8,0,0],[8,0,0],[8,0,0],q); `): elif nargs=1 and args[1]=Seqs12345 then print(`Seqs12345(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 occurence of 12345,`): print(` try: Seqs12345(8,3); `): else print(`There is no such thing as`, args): fi: end: # LtoEL(L,r): inputs compact format list L and number # of occurrences r, and outputs q "exponents" list LtoEL:=proc(L,r) local i: if nops(L)<>r+2 then RETURN(FAIL): fi: [seq((i-1)$L[i],i=1..nops(L))]: end: # F12345rRecList(Lx,Ly,Lz,q,r): the set of reduced items to sum over F12345rRecList:=proc(Lx,Ly,Lz,q,r) local i,j,n,S,k: n:=nops(Lx): S:={}: for i from 1 to n do k:=Lx[i]*(n-i): if k<=r+1 then S:=S union {[q^k,[op(1..i-1,Lx), seq(min(Lx[j]+Ly[i],r+1),j=i+1..n)], [op(1..i-1,Ly), seq(min(Ly[j]+Lz[i],r+1),j=i+1..n)], [op(1..i-1,Lz), seq(min(Lz[j],r)+1,j=i+1..n)]]}: fi: od: S: end: # F12345SqrT(Lx,Ly,Lz,q,r): main recursive procedure # for computing F12345 F12345SqrT:=proc(Lx,Ly,Lz,q,r) local su,i,grq: option remember: if nops(Lx)=1 then RETURN(1): fi: su:=F12345rRecList(Lx,Ly,Lz,q,r): grq:=expand(add(su[i][1]*F12345SqrT(su[i][2],su[i][3],su[i][4],q,r),i=1..nops(su))): grq:=add(coeff(grq,q,i)*q^i,i=0..r): end: # F12345r(Lx1,Ly1,Lz1,q): F12345r:=proc(Lx1,Ly1,Lz1,q) local r: if nops(Lx1)<>nops(Ly1) or nops(Ly1)<>nops(Lz1) then RETURN(FAIL): fi: r:=nops(Lx1)-2: if r<0 then RETURN(FAIL): fi: F12345SqrT(LtoEL(Lx1,r),LtoEL(Ly1,r),LtoEL(Lz1,r),q,r): end: # Seqs12345(N,R): The lists whose R+1 lists whose (r+1)-th list # is the first N members (starting at n=1) # number of permutations with exactly r occurence of 12345, # try: Seqs12345(8,3); Seqs12345:=proc(N,R) local gu,n1,q,r: option remember: gu:=[seq(F12345r([n1,0$(R+1)],[n1,0$(R+1)],[n1,0$(R+1)],q),n1=1..N)]: [seq([seq(coeff(gu[n1],q,r),n1=1..N)],r=0..R)]: end: