###################################################################### ##RandWilf: Save this file as RandWilf # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read RandWilf # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #zeilberg at math dot rutgers dot edu # ###################################################################### #Created: June 21, 2012 print(`Created: June 21, 2012`): print(` This is RandWilf `): print(`It accompanies Doron Zeilberger's talk `): print(`Automatic Meta-GASCOMania`): print(`at the GASCOM 2012 conference, Bordeaux, June 25-27,2012`): print(`delivered at LABRI, Tue. June 26, 2012 (local time)`): print(`dedicated to the memory of Herbert Saul Wilf (1931-2011)`): print(``): print(`This package uses Herb Wilf's seminal methodology`): print(`for selection, uniformly at random, a member of a combinatorial set`): print(`[Herbert S. Wilf, "A Unified Setting for Sequencing, Ranking, and Selection Algoirthms for Combinatorial Objects`): print(`Adv. Math. 24 (1977), 281-291, and described in more detail in the classic "Combinatorial Algorithms" `): print(`by Albert Nijenhuis and Herbert Wilf.`): print(`Here it is applied to lattice walks with any given set of (positive) steps`): print(``): print(`Please report bugs to zeilberg at math dot rutgers dot edu`): print(``): print(`The most current version of this package and paper`): print(` are available from`): print(`http://www.math.rutgers.edu/~zeilberg/ .`): print(`For a list of the procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): with(combinat): ezra1:=proc() if args=NULL then print(` The supporting procedures are: `): print(``): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: `): print(`NW, RollLD, RW, W `): elif nops([args])=1 and op(1,[args])=NW then print(`NW(Steps,pt,d): Given a list of steps of length d`): print(`(lists of non-negative integers`): print(`but with at least one non-zero entry), representing`): print(`steps that a walker can take, finds the NUMBER of`): print(`walks that end-up at the point pt.`): print(`Try: NW([[1,0],[0,1]],[5,5],2);`): elif nops([args])=1 and op(1,[args])=RollLD then print(`RollLD(L): Given a Loaded die, L, rolls it, try:`): print(`RollLD([1,3,2]);`): elif nops([args])=1 and op(1,[args])=RW then print(`RW(Steps,pt,d): Given a list of steps of length d`): print(`(lists of non-negative integers`): print(`but with at least one non-zero entry), representing`): print(`steps that a walker can take, finds ONE, drawn uniformly-at-random`): print(`member of the set of`): print(`walks that end-up at the point pt.`): print(`Try: RW([[1,0],[0,1]],[5,5],2);`): elif nops([args])=1 and op(1,[args])=W then print(`W(Steps,pt,d): Given a list of steps of length d`): print(`(lists of non-negative integers`): print(`but with at least one non-zero entry), representing`): print(`steps that a walker can take, finds the SET of`): print(`walks that end-up at the point pt.`): print(`Try: W([[1,0],[0,1]],[5,5],2);`): else print(`There is no ezra for`,args): fi: end: #W(Steps,pt,d): Given a list of steps of length d #(lists of non-negative integers #but with at least one non-zero entry), representing #steps that a walker can take, finds the set of #walks that end-up at the point pt. #Try: W([[1,0],[0,1]],[5,5],2); W:=proc(Steps,pt,d) local i,j,gu,gu1,pt1,gu11: option remember: if not type(Steps, list) then print(`Bad input`): RETURN(FAIL): fi: if {seq(type(Steps[i],list),i=1..nops(Steps))}<>{true} then print(`Bad input`): RETURN(FAIL): fi: if {seq(nops(Steps[i]),i=1..nops(Steps))}<>{d} then print(`Bad input`): RETURN(FAIL): fi: if {seq(seq(evalb(Steps[i][j]>=0),j=1..d),i=1..nops(Steps))}<>{true} then print(`Bad input`): RETURN(FAIL): fi: if member([0$d], convert(Steps,set)) then print(`Bad input`): RETURN(FAIL): fi: if pt=[0$d] then RETURN({[]}): fi: if min(op(pt))<0 then RETURN({}): fi: gu:={}: for i from 1 to nops(Steps) do pt1:=[seq(pt[j]-Steps[i][j],j=1..d)]: gu1:=W(Steps,pt1,d): gu:=gu union {seq([op(gu11),i],gu11 in gu1)}: od: gu: end: #NW(Steps,pt,d): Given a list of steps of length d #(lists of non-negative integers #but with at least one non-zero entry), representing #steps that a walker can take, finds the NUMBER of #walks that end-up at the point pt. #Try: NW([[1,0],[0,1]],[5,5],2); NW:=proc(Steps,pt,d) local i,j,gu,gu1,pt1: option remember: if not type(Steps, list) then print(`Bad input`): RETURN(FAIL): fi: if {seq(type(Steps[i],list),i=1..nops(Steps))}<>{true} then print(`Bad input`): RETURN(FAIL): fi: if {seq(nops(Steps[i]),i=1..nops(Steps))}<>{d} then print(`Bad input`): RETURN(FAIL): fi: if {seq(seq(evalb(Steps[i][j]>=0),j=1..d),i=1..nops(Steps))}<>{true} then print(`Bad input`): RETURN(FAIL): fi: if member([0$d], convert(Steps,set)) then print(`Bad input`): RETURN(FAIL): fi: if pt=[0$d] then RETURN(1): fi: if min(op(pt))<0 then RETURN(0): fi: gu:=0: for i from 1 to nops(Steps) do pt1:=[seq(pt[j]-Steps[i][j],j=1..d)]: gu1:=NW(Steps,pt1,d): gu:=gu+gu1: od: gu: end: #RollLD(L): Given a Loaded die, L, rolls it, try: #RollLD([1,3,2]); RollLD:=proc(L) local i,r,N: N:=convert(L,`+`): r:=rand(1..N)(): for i from 1 to nops(L) while convert([op(1..i,L)],`+`){true} then print(`Bad input`): RETURN(FAIL): fi: if {seq(nops(Steps[i]),i=1..nops(Steps))}<>{d} then print(`Bad input`): RETURN(FAIL): fi: if {seq(seq(evalb(Steps[i][j]>=0),j=1..d),i=1..nops(Steps))}<>{true} then print(`Bad input`): RETURN(FAIL): fi: if member([0$d], convert(Steps,set)) then print(`Bad input`): RETURN(FAIL): fi: if pt=[0$d] then RETURN([]): fi: if min(op(pt))<0 then RETURN(FAIL): fi: LD:=[]: for i from 1 to nops(Steps) do pt1:=[seq(pt[j]-Steps[i][j],j=1..d)]: LD:=[op(LD),NW(Steps,pt1,d)]: od: r:=RollLD(LD): pt1:=[seq(pt[j]-Steps[r][j],j=1..d)]: gu:=RW(Steps,pt1,d): [op(gu),r]: end: