####################################################################### ## Research: Save this file as ScoringPathsStats. # ## To use it, stay in the same directory # ## get into Maple (by typing: maple ) # ## and then type: read "ScoringPathsStats.txt"; # ## Then follow the instructions given there # ## # ## Written by Bryan Ek, Rutgers University, # ## bryan.t.ek@math.rutgers.edu. # ####################################################################### print(`This is ScoringPathsStats`): print(`by Bryan Ek, advisee to Dr. Zeilberger, Rutgers University.`): print(``): print(`If you have comments or notice any errors, please email`): print(`bryan [dot] t [dot] ek [at] math [dot] rutgers [dot] edu`): print(`bryan.t.ek@math.rutgers.edu`): print(``): print(`The latest version (3/12/2018) of this package is available from`): print(`http://www.math.rutgers.edu/~bte14/Code/ScoringPaths/ScoringPathsStats.txt`): print(``): print(`This package contains functions for enumerating walks and their statistics.`): print(`Given a set of possible steps on a square lattice, how many different walks are there of length n starting from the origin?`): print(`How much area is under the curve of each walk?`): print(`What if we restrict to having cyclic walks? I.e. we return the x-axis.`): print(`What if we disallow walks going below the line y=b<0? Or above the line y=a>0?`): print(`This package uses generating function relations to answer these questions.`): print(``): print(`For a detailed list of functions and their purpose type Help().`): print(``): ########################################################################################################################################### #Help function Help:=proc(): if args=`BoundedScoringPathsAreaEqsVars` then print(`BoundedScoringPathsAreaEqsVars(possibleScores,upperLimit,lowerLimit,t,z,f): inputs possible scores and the upperLimit and lowerLimit for the y-value.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`Assumes that upperLimit>=0,lowerLimit<=0.`): print(`f is a placeholder to keep track of the different g.f.s.`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Outputs a set of equations (and the used variables) relating the g.f.s for the number of paths of total x-step n, that start at (0,0) and stay within the limits.`): print(`Includes information about the area under each walk. The g.f.s have terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Includes the g.f.s for all pairs of limits (up,low) such that up-low=upperLimit-lowerLimit.`): print(`All equations are linear.`): print(`Try BoundedScoringPathsAreaEqsVars({[1,0],[1,-2],[2,-3],[0,1]},3,-2,t,z,f).`): elif args=`AllBoundedScoringPathsArea` then print(`AllBoundedScoringPathsArea(possibleScores,upperLimit,lowerLimit,t,z,f): inputs possible scores and the upperLimit and lowerLimit for the y-value.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`Assumes that upperLimit>=0,lowerLimit<=0.`): print(`f is a placeholder to keep track of the different g.f.s.`): print(`t is the variable in the g.f.`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f.s have terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Outputs ALL the g.f.s for the number of paths of total x-step n, that start at (0,0) and stay within its limits.`): print(`Includes the g.f.s for all pairs of limits (up,low) such that up-low=upperLimit-lowerLimit.`): print(`All equations are linear so the generating functions are all rational!`): print(`Uses BoundedScoringPathsAreaEqsVars.`): print(`Try AllBoundedScoringPathsArea({[1,0],[1,-2],[2,-3],[0,1]},3,-2,t,z,f).`): elif args=`BoundedScoringPathsArea` then print(`BoundedScoringPathsArea(possibleScores,upperLimit,lowerLimit,t,z): inputs possible scores and the upperLimit and lowerLimit for the y-value.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`Assumes that upperLimit>=0,lowerLimit<=0.`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Outputs only the g.f. for the number of paths of total x-step n, that start at (0,0) and stay within the limits given.`): print(`Uses AllBoundedScoringPathsArea.`): print(`Try BoundedScoringPathsArea({[1,0],[1,-2],[2,-3],[0,1]},3,-2,t,z).`): elif args=`BoundedScoringPathsAreaCoefficients` then print(`BoundedScoringPathsAreaCoefficients(possibleScores,upperLimit,lowerLimit,z,N): inputs possible scores and the upperLimit and lowerLimit for the y-value.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`Assumes that upperLimit>=0,lowerLimit<=0.`): print(`Outputs the first N+1 coefficients of the Taylor series of the g.f. for the number of paths that start at (0,0) and stay within the limits.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Uses BoundedScoringPaths.`): print(`Try BoundedScoringPathsCoefficients({[1,0],[1,-2],[2,-3],[0,1]},3,-2,z,9).`): elif args=`BoundedScoringPathsAreaNumber` then print(`BoundedScoringPathsAreaNumber(possibleScores,upperLimit,lowerLimit,n,a): inputs possible scores and the upperLimit and lowerLimit for the y-value.`): print(`Assumes that upperLimit>=0,lowerLimit<=0.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`Outputs the number of paths of x-step length n that start at (0,0), stay within the bounds, and have area a below the curve.`): print(`This function operates empirically.`): print(`If there are BOTH [0,-] and [0,+] steps that sum to 0 within the bounds, then you will obtain infinite recursion.`): print(`Try seq(add(BoundedScoringPathsAreaNumber({[1,0],[1,-2],[2,-3],[0,1]},3,-2,n1,a1)*z^a1,a1=0..9),n1=0..9).`): elif args=`EqualBoundedScoringPathsAreaEqsVars` then print(`EqualBoundedScoringPathsAreaEqsVars(possibleScores,upperLimit,lowerLimit,t,z,f,e): inputs possible scores and the upperLimit and lowerLimit for the y-value.`): print(`Assumes that upperLimit>=0,lowerLimit<=0.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`f,e are placeholder variables for the g.f.s.`): print(`f[upperLimit,lowerLimit] is the g.f. for the number of paths of total x-step n, that start at (0,0), end at (n,0), and stay within the limits.`): print(`e[upperLimit,lowerLimit,c] is the g.f. for the number of "irreducible" walks that start at (c,0), end at (n,0), stay within the given limits, and touch 0 only at the end.`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Outputs a set of equations (and the used variables) relating the g.f.s held in f and e.`): print(`Try EqualBoundedScoringPathsAreaEqsVars({[1,0],[1,-2],[2,-3],[0,1]},3,-2,t,z,f,e).`): elif args=`AllEqualBoundedScoringPathsArea` then print(`AllEqualBoundedScoringPathsArea(possibleScores,upperLimit,lowerLimit,t,z,f,e): inputs possible scores and the upperLimit and lowerLimit for the y-value.`): print(`Assumes that upperLimit>=0,lowerLimit<=0.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`f,e are placeholder variables for the g.f.s.`): print(`f[upperLimit,lowerLimit] is the g.f. for the number of paths of total x-step n, that start at (0,0), end at (n,0), and stay within the limits.`): print(`e[upperLimit,lowerLimit,c] is the g.f. for the number of "irreducible" walks that start at (c,0), end at (n,0), stay within the given limits, and touch 0 only at the end.`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Outputs the g.f.s f[upperLimit,lowerLimit] and e[upperLimit,lowerLimit,c] for all c=lowerLimit..-1,1..upperLimit.`): print(`Uses EqualBoundedScoringPathsAreaEqsVars.`): print(`Try AllEqualBoundedScoringPathsArea({[1,0],[1,-2],[2,-3],[0,1]},3,-2,t,z,f,e).`): elif args=`EqualBoundedScoringPathsArea` then print(`EqualBoundedScoringPaths(possibleScores,upperLimit,lowerLimit,t,z): inputs possible scores and the upperLimit and lowerLimit for the y-value.`): print(`Assumes that upperLimit>=0,lowerLimit<=0.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Outputs the g.f. for the number of paths of total x-step n, that start at (0,0), end at (n,0), and stay within the limits.`): print(`Uses EqualBoundedScoringPathsAreaEqsVars.`): print(`Try EqualBoundedScoringPathsArea({[1,0],[1,-2],[2,-3],[0,1]},3,-2,t,z).`): elif args=`EqualBoundedScoringPathsAreaCoefficients` then print(`EqualBoundedScoringPathsAreaCoefficients(possibleScores,upperLimit,lowerLimit,z,N): inputs possible scores and the upperLimit and lowerLimit for the y-value.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`Assumes that upperLimit>=0,lowerLimit<=0.`): print(`Outputs the first N+1 coefficients of the Taylor series of the g.f. for the number of paths that start at (0,0), end at (n,0), and stay within the limits.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Uses EqualBoundedScoringPathsArea.`): print(`Try EqualBoundedScoringPathsAreaCoefficients({[1,0],[1,-2],[2,-3],[0,1]},3,-2,z,9).`): elif args=`SpecificEqualBoundedScoringPathsAreaNumber` then print(`SpecificEqualBoundedScoringPathsAreaNumber(possibleScores,upperLimit,lowerLimit,n,startingLevel,area): inputs possible scores (x-step,y-step) and the upperLimit and lowerLimit for the y-value.`): print(`Assumes that upperLimit>=0,lowerLimit<=0, and startingLevel is somewhere between these 2 numbers.`): print(`possibleScores is a list or set of scores in the format [x,y].`): print(`Outputs the number of paths that start at (0,startingLevel), end at (n,0), stay within the bounds, and have area a under the curve.`): print(`Does this empirically.`): print(`If there are BOTH [0,-] and [0,+] steps that sum to 0 within the bounds, then you will obtain infinite recursion.`): print(`Try seq(add(SpecificEqualBoundedScoringPathsAreaNumber({[1,0],[1,-2],[2,-3],[0,1]},3,-2,n1,a1)*z^a1,a1=-9..9),n1=0..9).`): elif args=`SpecificIrreducibleBoundedScoringPathsAreaNumber` then print(`SpecificIrreducibleBoundedScoringPathsNumber(possibleScores,upperLimit,lowerLimit,n,startingLevel,a): inputs possible scores (x-step,y-step) and the upperLimit and lowerLimit for the y-value.`): print(`Assumes that upperLimit>=0,lowerLimit<=0, and startingLevel is somewhere between these 2 numbers.`): print(`possibleScores is a list or set of scores in the format [x,y].`): print(`Outputs the number of paths that start at (0,startingLevel), end at (n,0) while never touching the x-axis previously, stay within the bounds, and have area a under the curve.`): print(`Does this empirically.`): print(`If there are BOTH [0,-] and [0,+] steps that sum to 0 within the bounds, then you will obtain infinite recursion.`): print(`Try seq(add(SpecificIrreducibleBoundedScoringPathsAreaNumber({[1,0],[1,-2],[2,-3],[0,1]},3,-2,n1,a1)*z^a1,a1=-9..9),n1=0..9).`): elif args=`SpecificIrreducibleBoundedScoringPathsAreaNumberHelp` then print(`SpecificIrreducibleBoundedScoringPathsAreaNumberHelp(possibleScores,upperLimit,lowerLimit,n,startingLevel): inputs possible scores (x-step,y-step) and the upperLimit and lowerLimit for the y-value.`): print(`Helps SpecificIrreducibleBoundedScoringPathsAreaNumber.`): elif args=`SemiBoundedScoringPathsAreaEqsVars` then print(`SemiBoundedScoringPathsAreaEqsVars(possibleScores,lowerLimit,t,z,k,f,g): inputs possible scores and lowerLimit for the y-value.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`Assumes lowerLimit<=0.`): print(`f,g,k are placeholders to keep track of the different g.f.s. g is for irreducible (only hits minimum at the respective endpoint) walks.`): print(`f[a,b] is the g.f. for the number of walks from (0,a) to (n,b) that stay above the lowerLimit.`): print(`g[a,b] is the g.f. for the number of irreducible walks from (0,a) to (n,b) that stay above the lowerLimit.`): print(`f,g are the same g.f. as for EqualSemiBoundedScoringPathsAreaEqsVars(possibleScores,lowerLimit,t,f,g).`): print(`k[y] is the g.f. for walks above lowerLimit that begin at (0,y) and end anywhere.`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Outputs a set of equations (and the used variables) relating the g.f.s held in f,g,k.`): print(`Try SemiBoundedScoringPathsAreaEqsVars({[1,0],[1,-2],[2,-3],[0,1]},-2,t,z,k,f,g).`): elif args=`SemiBoundedScoringPathsAreaSeries` then print(`SemiBoundedScoringPathsAreaSeries(possibleScores,lowerLimit,t,z,k,f,g,N): inputs possible scores and the lowerLimit for the y-value.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`Assumes that lowerLimit<=0.`): print(`Outputs the Taylor series (truncated at t^(N+1)) of the g.f.s found in SemiBoundedScoringPathsAreaEqsVars.`): print(`f,g,k are placeholders to keep track of the different g.f.s. g is for irreducible (only hits minimum at the respective endpoint) walks.`): print(`f[a,b] is the g.f. for the number of walks from (0,a) to (n,b) that stay above the lowerLimit.`): print(`g[a,b] is the g.f. for the number of irreducible walks from (0,a) to (n,b) that stay above the lowerLimit.`): print(`f,g are the same g.f. as for EqualSemiBoundedScoringPathsAreaEqsVars(possibleScores,lowerLimit,t,z,f,g).`): print(`k[y] is the g.f. for walks above lowerLimit that begin at (0,y) and end anywhere.`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Uses SemiBoundedScoringPathsAreaEqsVars. Iterates to a fixed-point solution starting from {f[a,a]=1,f[a,b]=0,g[0,0]=0,g[a,b]=0,k[y]=1}.`): print(`Try SemiBoundedScoringPathsAreaSeries({[1,0],[1,-2],[2,-3],[0,1]},-2,t,z,k,f,g,9).`): elif args=`SemiBoundedScoringPathsAreaCoefficients` then print(`SemiBoundedScoringPathsAreaCoefficients(possibleScores,lowerLimit,z,N): inputs possible scores and the lowerLimit for the y-value.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`Assumes that lowerLimit<=0.`): print(`Outputs the first N+1 coefficients of the Taylor series of the g.f. for the number of paths that start at (0,0), stay above the lowerLimit, and end anywhere.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Uses SemiBoundedScoringPathsAreaSeries.`): print(`Try SemiBoundedScoringPathsAreaCoefficients({[1,0],[1,-2],[2,-3],[0,1]},-2,z,9).`): elif args=`SpecificSemiBoundedScoringPathsAreaNumber` then print(`SpecificSemiBoundedScoringPathsAreaNumber(possibleScores,lowerLimit,n,startingLevel,area): inputs possible scores (x-step,y-step) in the format {[x1,y1],[x2,y2],...}.`): print(`Outputs the number of paths that start at (0,startingLevel), are of length n, don't go below y=lowerLimit<=0, and have area a under the curve.`): print(`There CANNOT be (0,+) steps. Otherwise you get infinity as the answer.`): print(`The answer is computed empirically.`): print(`Try seq(add(SpecificSemiBoundedScoringPathsAreaNumber({[1,0],[1,-2],[2,-3],[0,1]},-2,n1,a1)*z^a1,a1=-9..9),n1=0..9).`): elif args=`SpecificSemiBoundedScoringPathsAreaNumberHelp` then print(`A helper function to compute the number of walks after parsing in SpecificBoundedScoringPathsAreaNumber.`): elif args=`SpecificSemiBoundedScoringPathsAreaNumberHelp2` then print(`Computes the number of ways to end at the current x value. All of these scores correspond to steps straight down.`): elif args=`EqualSemiBoundedScoringPathsAreaEqsVars` then print(`EqualSemiBoundedScoringPathsAreaEqsVars(possibleScores,lowerLimit,t,z,f,g): inputs possible scores and lowerLimit for the y-value.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`Assumes lowerLimit<=0.`): print(`f,g are placeholders to keep track of the different g.f.s. g is for irreducible (only hits minimum at the respective endpoint) walks.`): print(`f[a,b] is the g.f. for the number of walks from (0,a) to (n,b) that stay above the lowerLimit.`): print(`g[a,b] is the g.f. for the number of irreducible walks from (0,a) to (n,b) that stay above the lowerLimit.`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Outputs a set of equations (and the used variables) relating the g.f.s held in f and g.`): print(`Try EqualSemiBoundedScoringPathsAreaEqsVars({[1,0],[1,-2],[2,-3],[0,1]},-2,t,z,f,g).`): elif args=`EqualSemiBoundedScoringPathsAreaSeries` then print(`EqualSemiBoundedScoringPathsAreaSeries(possibleScores,lowerLimit,t,z,f,g,N): inputs possible scores and the lowerLimit for the y-value.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`Assumes that lowerLimit<=0.`): print(`Outputs the Taylor series (truncated at t^(N+1)) of the g.f.s found in EqualSemiBoundedScoringPathsAreaEqsVars.`): print(`f[a,b] is the g.f. for the number of walks from (0,a) to (n,b) that stay above the lowerLimit.`): print(`g[a,b] is the g.f. for the number of irreducible walks from (0,a) to (n,b) that stay above the lowerLimit.`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Uses EqualSemiBoundedScoringPathsAreaEqsVars. Iterates to a fixed-point solution starting from {f[a,a]=1,f[a,b]=0,g[0,0]=0,g[a,b]=0}.`): print(`Try EqualSemiBoundedScoringPathsAreaSeries({[1,0],[1,-2],[2,-3],[0,1]},-2,t,z,f,g,9).`): elif args=`EqualSemiBoundedScoringPathsAreaCoefficients` then print(`EqualSemiBoundedScoringPathsAreaCoefficients(possibleScores,lowerLimit,z,N): inputs possible scores and the lowerLimit for the y-value.`): print(`possibleScores is a list or set of scores in the format [x-step,y-step].`): print(`Assumes that lowerLimit<=0.`): print(`Outputs the first N+1 coefficients of the Taylor series of the g.f. for the number of paths that start at (0,0), end at (n,0), and stay above the lowerLimit.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Uses EqualSemiBoundedScoringPathsArea.`): print(`Try EqualSemiBoundedScoringPathsAreaCoefficients({[1,0],[1,-2],[2,-3],[0,1]},-2,z,9).`): elif args=`SpecificEqualSemiBoundedScoringPathsAreaNumber` then print(`SpecificEqualSemiBoundedScoringPathsAreaNumber(possibleScores,lowerLimit,n,startingLevel,area): inputs possible scores (x-step,y-step) in the format {[x1,y1],[x2,y2],...}.`): print(`Outputs the number of paths that start at (0,startingLevel), end at (n,0), don't go below y=lowerLimit<=0, and have area a under the curve.`): print(`There should NOT be BOTH (0,+) and (0,-) steps. Otherwise you get infinity as the answer.`): print(`The answer is computed empirically.`): print(`Try seq(add(SpecificEqualSemiBoundedScoringPathsAreaNumber({[1,0],[1,-2],[2,-3],[0,1]},-2,n1,a1)*z^a1,a1=-9..9),n1=0..9).`): elif args=`SpecificEqualSemiBoundedScoringPathsAreaNumberN` then print(`SpecificEqualSemiBoundedScoringPathsAreaNumberN(possibleScores,lowerLimit,n,startingLevel,area): A helper function that works if there are no (0,+) steps.`): print(`Helps SpecificEqualSemiBoundedScoringPathsAreaNumber.`): elif args=`SpecificEqualSemiBoundedScoringPathsAreaNumberP` then print(`SpecificEqualSemiBoundedScoringPathsAreaNumberP(possibleScores,lowerLimit,n,startingLevel,maxDescentRate,area): A helper function that works if there are no (0,-) steps.`): print(`Helps SpecificEqualSemiBoundedScoringPathsAreaNumber.`): print(`Inputting maxDescentRate just saves some computation time. It is determined by possibleScores.`): elif args=`SpecificIrreducibleSemiBoundedScoringPathsAreaNumber` then print(`SpecificIrreducibleSemiBoundedScoringPathsAreaNumber(possibleScores,n,startingLevel,area): inputs possible scores (x-step,y-step) in the format {[x1,y1],[x2,y2],...}.`): print(`Outputs the number of paths that start at (0,startingLevel), end at (n,0), don't go below y=min(startingLevel,0), and have area a under the curve.`): print(`There should NOT be BOTH (0,+) and (0,-) steps. Otherwise you get infinity as the answer.`): print(`The answer is computed empirically.`): print(`Try seq(add(SpecificIrreducibleSemiBoundedScoringPathsAreaNumber({[1,0],[1,-2],[2,-3],[0,1]},-2,n1,a1)*z^a1,a1=-9..9),n1=0..9).`): elif args=`SpecificIrreducibleSemiBoundedScoringPathsAreaNumberN` then print(`SpecificIrreducibleSemiBoundedScoringPathsAreaNumberN(possibleScores,lowerLimit,n,startingLevel,area): A helper function that works if there are no (0,+) steps.`): print(`Helps SpecificIrreducibleSemiBoundedScoringPathsAreaNumber.`): elif args=`SpecificIrreducibleSemiBoundedScoringPathsAreaNumberP` then print(`SpecificIrreducibleSemiBoundedScoringPathsAreaNumberP(possibleScores,lowerLimit,n,startingLevel,maxDescentRate,area): A helper function that works if there are no (0,-) steps.`): print(`Helps SpecificIrreducibleSemiBoundedScoringPathsAreaNumber.`): print(`Inputting maxDescentRate just saves some computation time. It is determined by possibleScores.`): elif args=`UnBoundedScoringPathsArea` then print(`UnBoundedScoringPathsArea(possibleScores,t,z): inputs possible scores and a variable t.`): print(`possibleScores is a list or set of scores in the format [x,y]. All scores should have x-step>0.`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Outputs a relation for the generating function of the number of paths of total x-step, n, that start at (0,0) and go anywhere.`): print(`Try UnBoundedScoringPathsArea({[1,1],[1,-1],[1,2],[2,-3]},t,z).`): elif args=`UnBoundedScoringPathsAreaCoefficients` then print(`UnBoundedScoringPathsAreaCoefficients(possibleScores,z,N): Outputs the first N+1 coefficients of the Taylor series of the g.f. for the number of paths of x-step n.`): print(`Uses UnBoundedScoringPathsArea.`): print(`Try UnBoundedScoringPathsAreaCoefficients({[1,1],[1,-1],[1,2],[2,-3]},z,a9).`): elif args=`UnBoundedScoringPathsAreaNumber` then print(`UnBoundedScoringPathsAreaNumber(possibleScores,n,area): inputs possible scores (x-step,y-step)`): print(`Outputs the number of paths of total x-step, n, that start at (0,0), go anywhere, and have area a under the curve.`): print(`The answer is computed empirically.`): print(`Try seq(add(UnBoundedScoringPathsAreaNumber({[1,1],[1,-1],[1,2],[2,-3]},n1,a1/2),a1=-9..9),n1=0..9).`): elif args=`UnBoundedScoringPathsAreaNumber1` then print(`UnBoundedScoringPathsAreaNumber1(possibleScores,n,area): A helper function after ensuring no infinite recursion.`): print(`Helps UnBoundedScoringPathsAreaNumber.`): elif args=`EqualUnBoundedScoringPathsAreaEqsVars` then print(`EqualUnBoundedScoringPathsAreaEqsVars(possibleScores,t,z,B,h,f,g): inputs possible scores (x-step,y-step), and placeholder variables.`): print(`possibleScores is a list or set of scores in the format [x,y].`): print(`h,f,g are placeholder generating functions. f,g are the same g.f. as for EqualSemiBoundedScoringPathsAreaEqsVars(possibleScores,0,t,z,f,g).`): print(`GF is the g.f. for the number of walks that begin at (0,0) and end at (n,0).`): print(`h[i] is the g.f. for walks that start at (i,0) and return to the x-axis only at the end.`): print(`f[a,b] is the g.f. for the number of walks from (0,a) to (n,b) that stay above the x-axis.`): print(`g[a,b] is the g.f. for the number of irreducible (only hits min(a,b) at the respective endpoint) walks from (0,a) to (n,b) that stay above the x-axis.`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Outputs many generating functions and equations describing their relations.`): print(`The g.f. for the number of walks that begin at (0,0) and end at (n,0) is found by taking 1/(1-h[0]). (Since gf=1+h[0]*gf.)`): print(`Try EqualUnBoundedScoringPathsAreaEqsVars({[1,0],[1,-2],[2,-3],[0,1]},t,z,B,h,f,g).`): elif args=`EqualUnBoundedScoringPathsAreaSeries` then print(`EqualUnBoundedScoringPathsAreaSeries(possibleScores,t,z,B,h,f,g,N): inputs possible scores which is a list or set of scores in the format [x-step,y-step].`): print(`Outputs the Taylor series (truncated at t^(N+1)) of the g.f.s found in EqualUnBoundedScoringPathsAreaEqsVars.`): print(`h,f,g are placeholder generating functions. f,g are the same g.f. as for EqualSemiBoundedScoringPathsAreaEqsVars(possibleScores,0,t,z,f,g).`): print(`GF is the g.f. for the number of walks that begin at (0,0) and end at (n,0).`): print(`h[i] is the g.f. for walks that start at (i,0) and return to the x-axis only at the end.`): print(`f[a,b] is the g.f. for the number of walks from (0,a) to (n,b) that stay above the x-axis.`): print(`g[a,b] is the g.f. for the number of irreducible (only hits min(a,b) at the respective endpoint) walks from (0,a) to (n,b) that stay above the x-axis.`): print(`t is the variable to keep track of length in the g.f.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Uses EqualUnBoundedScoringPathsAreaEqsVars. Iterates to a fixed-point solution starting from {B=1,f[a,a]=1,f[a,b]=0,h[i]=0,g[0,0]=0,g[a,b]=0}.`): print(`Try EqualUnBoundedScoringPathsSeries({[1,0],[1,-2],[2,-3],[0,1]},t,z,B,h,f,g,9).`): elif args=`EqualUnBoundedScoringPathsAreaCoefficients` then print(`EqualUnBoundedScoringPathsAreaCoefficients(possibleScores,z,N): inputs possible scores which is a list or set of scores in the format [x-step,y-step].`): print(`Outputs the first N+1 coefficients of the Taylor series of the g.f. for the number of paths that start at (0,0) and end at (n,0).`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`Uses UnBoundedScoringPathsAreaSeries.`): print(`Try EqualUnBoundedScoringPathsAreaCoefficients({[1,0],[1,-2],[2,-3],[0,1]},z,9).`): elif args=`SpecificUnBoundedScoringPathsAreaNumber` then print(`SpecificUnBoundedScoringPathsAreaNumber(possibleScores,n,startingLevel,area): inputs possible scores (x-step,y-step) in the format {[x1,y1],[x2,y2],...}.`): print(`Outputs the number of paths that start at (0,startingLevel) and end at (n,0).`): print(`There should NOT be BOTH (0,+) and (0,-) steps. Otherwise you get infinity as the answer.`): print(`z is the variable to keep track of area in the g.f.`): print(`Includes information about the area under each walk. The g.f. has terms c*t^n*z^a to indicate there are c walks of length n with area a under the curve.`): print(`The answer is computed empirically.`): print(`Try seq(add(SpecificUnBoundedScoringPathsAreaNumber({[1,0],[1,-2],[2,-3],[0,1]},n1,0,a1/2),a1=-9..9),n1=0..9).`): elif args=`SpecificUnBoundedScoringPathsAreaNumberN` then print(`SpecificUnBoundedScoringPathsAreaNumberN(possibleScores,n,startingLevel,maxRate,area): A helper function that works if there are no (0,+) steps.`): print(`Helps SpecificUnBoundedScoringPathsAreaNumber.`): print(`Inputting maxRate just saves some computation time. It is determined by possibleScores.`): elif args=`SpecificUnBoundedScoringPathsAreaNumberP` then print(`SpecificUnBoundedScoringPathsAreaNumberP(possibleScores,n,startingLevel,maxRate,area): A helper function that works if there are no (0,-) steps.`): print(`Helps SpecificUnBoundedScoringPathsAreaNumber.`): print(`Inputting maxRate just saves some computation time. It is determined by possibleScores.`): elif args=`SpecificIrreducibleUnBoundedScoringPathsAreaNumber` then print(`SpecificIrreducibleUnBoundedScoringPathsAreaNumber(possibleScores,n,startingLevel,area): inputs possible scores (x-step,y-step) in the format {[x1,y1],[x2,y2],...}.`): print(`Outputs the number of paths that start at (0,startingLevel) and end at (n,0).`): print(`There should NOT be BOTH (0,+) and (0,-) steps. Otherwise you get infinity as the answer.`): print(`The answer is computed empirically.`): print(`Try seq(add(SpecificIrreducibleUnBoundedScoringPathsAreaNumber({[1,0],[1,-2],[2,-3],[0,1]},n1,0,a1/2),a1=-9..9),n1=0..9).`): elif args=`SpecificIrreducibleUnBoundedScoringPathsAreaNumberN` then print(`SpecificIrreducibleUnBoundedScoringPathsAreaNumberN(possibleScores,n,startingLevel,maxRate,area): A helper function that works if there are no (0,+) steps.`): print(`Helps SpecificIrreducibleUnBoundedScoringPathsAreaNumber.`): print(`Inputting maxRate just saves some computation time. It is determined by possibleScores.`): elif args=`SpecificIrreducibleUnBoundedScoringPathsAreaNumberP` then print(`SpecificIrreducibleUnBoundedScoringPathsAreaNumberP(possibleScores,n,startingLevel,maxRate,area): A helper function that works if there are no (0,-) steps.`): print(`Helps SpecificIrreducibleUnBoundedScoringPathsAreaNumber.`): print(`Inputting maxRate just saves some computation time. It is determined by possibleScores.`): elif args=`RandomStepSet` then print(`RandomStepSet(numSteps,xBound,yBound): produces a set of steps each with x-value between 0 and xBound and y-value between -yBound and yBound.`): print(`There cannot be a [0,0] step, thus we need yBound>=1. And there must be some step with x-value>0 so we should also have xBound>=1.`): print(`Try RandomStepSet(8,4,3).`): elif args=`RandomZeroStepSet` then print(`Producing random step sets for the Bounded, EqualBounded, EqualSemiBounded and EqualUnBounded cases.`): print(`The bounded cases could be expanded to include some pairs of (+) and (-) zero steps but I do not currently know the restrictions.`): print(`RandomZeroStepSet(numSteps,xBound,yBound): produces a set of steps each with x-value between 0 and xBound and y-value between -yBound and yBound.`): print(`There cannot be a [0,0] step, thus we need yBound>=1. And there must be some step with x-value>0 so we should also have xBound>=1.`): print(`There also cannot be both (+) and (-) zero steps.`): print(`Try RandomZeroStepSet(8,4,3).`): elif args=`RandomSemiBoundedStepSet` then print(`Producing random step sets for the SemiBounded case.`): print(`RandomSemiBoundedStepSet(numSteps,xBound,yBound): produces a set of steps each with x-value between 0 and xBound and y-value between -yBound and yBound.`): print(`There cannot be a [0,0] step, thus we need yBound>=1. And there must be some step with x-value>0 so we should also have xBound>=1.`): print(`There also cannot be (+) zero steps.`): print(`Try RandomSemiBoundedStepSet(8,4,3).`): elif args=`RandomUnBoundedStepSet` then print(`Producing random step sets for the UnBounded case.`): print(`RandomUnBoundedStepSet(numSteps,xBound,yBound): produces a set of steps each with x-value between 1 and xBound and y-value between -yBound and yBound.`): print(`There cannot be zero steps.`): print(`Try RandomUnBoundedStepSet(8,4,3).`): elif args=`PaperBounded1Area` then print(`PaperBounded1Area(Steps,upperLimit,lowerLimit,K): inputs a set of steps, Steps, and a positive integer K, outputs an article about the`): print(`generating function of walks from the origin back to [n,0] for some n that never go below y=lowerLimit or above y=upperLimit.`): print(`Includes information about the area under the curve of each walk encoded in z^a.`): print(`c*t^n*z^a indicates there are c paths of length n with area a under the walk.`): print(`It also outputs the first K terms, for the sake of the OEIS.`): print(`Try:`): print(`PaperBounded1Area({[1,2],[1,-2],[1,3],[1,-3]},8,-2,20);`): elif args=`PaperBounded2Area` then print(`PaperBounded2Area(Steps,K): inputs a set of steps, Steps, and a positive integer K, outputs an article about the`): print(`generating function of walks from the origin back to [n,0] for some n that never go further than one step from the x-axis.`): print(`Includes information about the area under the curve of each walk encoded in z^a.`): print(`c*t^n*z^a indicates there are c paths of length n with area a under the walk.`): print(`It also outputs the first K terms, for the sake of the OEIS.`): print(`Try:`): print(`PaperBounded2Area({[1,2],[1,-2],[1,3],[1,-3]},20);`): elif args=`PaperSemiBoundedArea` then print(`PaperSemiBoundedArea(Steps,K): inputs a set of steps, Steps, and a positive integer K, outputs an article about the`): print(`generating function of walks from the origin back to [n,0] for some n that never go below the x-axis.`): print(`Includes information about the area under the curve of each walk encoded in z^a.`): print(`c*t^n*z^a indicates there are c paths of length n with area a under the walk.`): print(`It also outputs the first K terms, for the sake of the OEIS.`): print(`Try:`): print(`PaperSemiBoundedArea({[1,1],[1,-1],[1,0]},40,true);`): elif args=`PaperEqualSemiBoundedArea` then print(`PaperEqualSemiBoundedArea(Steps,K): inputs a set of steps, Steps, and a positive integer K, outputs an article about the`): print(`generating function of walks from the origin back to [n,0] for some n that never go below the x-axis.`): print(`Includes information about the area under the curve of each walk encoded in z^a.`): print(`c*t^n*z^a indicates there are c paths of length n with area a under the walk.`): print(`It also outputs the first K terms, for the sake of the OEIS.`): print(`Try:`): print(`PaperEqualSemiBoundedArea({[1,1],[1,-1],[1,0]},40);`): elif args=`BookEqualSemiBounded` then print(`BookEqualSemiBounded(Steps,K): inputs a set of steps, Steps, and a positive integer K.`): print(`Outputs a book about the generating functions of walks from the origin back to [n,0] for some n that never go below the x-axis.`): print(`Includes information about the area under the curve of each walk encoded in z^a.`): print(`c*t^n*z^a indicates there are c paths of length n with area a under the walk.`): print(`Iterates over all subsets of Steps.`): print(`Try:`): print(`BookEqualSemiBounded({[1,1],[1,-1],[1,0],[2,2],[2,-2],[3,3],[3,-1]},40);`): elif args=`PaperEqualSemiBoundedAreaPair` then print(`PaperEqualSemiBoundedAreaPair(a,b,K): inputs positive integers a and b that are relatively prime, and a positive integer K, outputs an article about the`): print(`generating function of walks from the origin back to [(a+b)*n,0] for some n that never go below the x-axis.`): print(`Includes information about the area under the curve of each walk encoded in z^a.`): print(`c*t^n*z^a indicates there are c paths of length n with area a under the walk.`): print(`It also outputs the first K terms, for the sake of the OEIS.`): print(`Try:`): print(`PaperEqualSemiBoundedAreaPair(2,3,40);`): elif args=`PaperUnBoundedArea` then print(`PaperUnBoundedArea(Steps,K): inputs a set of steps, Steps, and a positive integer K, outputs an article about the`): print(`generating function of walks from the origin back to [n,0] for some n.`): print(`Includes information about the area under the curve of each walk encoded in z^a.`): print(`c*t^n*z^a indicates there are c paths of length n with area a under the walk.`): print(`It also outputs the first K terms, for the sake of the OEIS.`): print(`Try:`): print(`PaperUnBoundedArea({[1,1],[1,-1],[1,0]},40);`): elif args=`PaperUnBoundedPairArea` then print(`PaperUnBoundedPairArea(a,b,K): inputs positive integers a and b that are relatively prime, and a positive integer K, outputs an article about the`): print(`generating function of walks from the origin back to [(a+b)*n,0] for some n.`): print(`Includes information about the area under the curve of each walk encoded in z^a.`): print(`c*t^n*z^a indicates there are c paths of length n with area a under the walk.`): print(`It also outputs the first K terms, for the sake of the OEIS.`): print(`Try:`): print(`PaperUnBoundedPairArea(2,3,40);`): else print(`Primary functions:`): print(`BoundedScoringPathsAreaEqsVars, EqualBoundedScoringPathsAreaEqsVars, SemiBoundedScoringPathsAreaEqsVars, EqualSemiBoundedScoringPathsAreaEqsVars, UnBoundedScoringPathsArea, EqualUnBoundedScoringPathsAreaEqsVars`): print(``): print(`Enumerating functions:`): print(`BoundedScoringPathsAreaCoefficients, BoundedScoringPathsAreaNumber, EqualBoundedScoringPathsAreaCoefficients, SpecificEqualBoundedScoringPathsAreaNumber, SpecificIrreducibleBoundedScoringPathsAreaNumber, SemiBoundedScoringPathsAreaCoefficients, SpecificSemiBoundedScoringPathsAreaNumber, EqualSemiBoundedScoringPathsAreaCoefficients, SpecificEqualSemiBoundedScoringPathsAreaNumber, SpecificIrreducibleSemiBoundedScoringPathsAreaNumber, UnBoundedScoringPathsAreaCoefficients, UnBoundedScoringPathsAreaNumber, EqualUnBoundedScoringPathsAreaCoefficients, SpecificUnBoundedScoringPathsAreaNumber, SpecificIrreducibleUnBoundedScoringPathsAreaNumber`): print(``): print(`Helper functions:`): print(`SpecificIrreducibleBoundedScoringPathsAreaNumberHelp, SemiBoundedScoringPathsAreaSeries, SpecificSemiBoundedScoringPathsAreaNumberHelp, SpecificSemiBoundedScoringPathsAreaNumberHelp2, EqualSemiBoundedScoringPathsAreaSeries, SpecificEqualSemiBoundedScoringPathsAreaNumberN, SpecificEqualSemiBoundedScoringPathsAreaNumberP, SpecificIrreducibleSemiBoundedScoringPathsAreaNumberN, SpecificIrreducibleSemiBoundedScoringPathsAreaNumberP, UnBoundedScoringPathsAreaNumber1, UnBoundedScoringPathsAreaSeries, SpecificUnBoundedScoringPathsAreaNumberN, SpecificUnBoundedScoringPathsAreaNumberP, SpecificIrreducibleUnBoundedScoringPathsAreaNumberN, SpecificIrreducibleUnBoundedScoringPathsAreaNumberP, RandomStepSet, RandomZeroStepSet, RandomSemiBoundedStepSet, RandomUnBoundedStepSet`): print(``): print(`Paper-producing functions:`): print(`PaperBounded1Area, PaperBounded2Area, PaperSemiBoundedArea, PaperEqualSemiBoundedArea, BookEqualSemiBoundedArea, PaperEqualSemiBoundedPairArea, PaperUnBoundedArea, PaperUnBoundedPairArea`): print(``): print(`If all the y-steps have a common factor, it may be necessary to divide by that factor.`): print(`In the unbounded and semi-bounded (equal) cases, you can have steps with x-step=0, as long as they are all in the same direction. E.g. {[0,1],[0,-2]} is NOT allowed.`): print(`You cannot have steps with x-step=0 in the free (walk anywhere) unbounded case.`): print(`You cannot have steps with x-step=0 and y-step>0 in the free (walk anywhere) semibounded case.`): print(`In the bounded case, you can have BOTH [0,-] and [0,+] ONLY IF you cannot sum to 0 within the bounds.`): print(`Generating function(s) will be abbreviated as g.f.(s).`): print(``): fi: end: ########################################################################################################################################### ########################################################################################################################################### ########################################################################################################################################### #Bounded ########################################################################################################################################### ########################################################################################################################################### BoundedScoringPathsAreaEqsVars:=proc(possibleScores,upperLimit,lowerLimit,t,z,f) local eqs,vars,i,expr,score: eqs:={}: vars:={}: for i from lowerLimit to upperLimit do expr:=1: for score in possibleScores do if i+score[2]>=lowerLimit and i+score[2]<=upperLimit then expr:=expr+t^score[1]*z^(score[1]*(i+score[2]/2))*f[upperLimit-i-score[2],lowerLimit-i-score[2]]: fi: od: eqs:=eqs union {f[upperLimit-i,lowerLimit-i]=expr}: vars:=vars union {f[upperLimit-i,lowerLimit-i]}: od: eqs,vars: end: ########################################################################################################################################### AllBoundedScoringPathsArea:=proc(possibleScores,upperLimit,lowerLimit,t,z,f): solve(BoundedScoringPathsAreaEqsVars(possibleScores,upperLimit,lowerLimit,t,z,f)): end: ########################################################################################################################################### BoundedScoringPathsArea:=proc(possibleScores,upperLimit,lowerLimit,t,z) local f: subs(AllBoundedScoringPathsArea(possibleScores,upperLimit,lowerLimit,t,z,f),f[upperLimit,lowerLimit]): end: ###################################################################################################### BoundedScoringPathsAreaCoefficients:=proc(possibleScores,upperLimit,lowerLimit,z,N) local t,f: f:=taylor(BoundedScoringPathsArea(possibleScores,upperLimit,lowerLimit,t,z),t,N+1): seq(coeff(f,t,i),i=0..N): end: ###################################################################################################### BoundedScoringPathsAreaNumber:=proc(possibleScores,upperLimit,lowerLimit,n,area) BoundedScoringPathsAreaNumberHelp(possibleScores,upperLimit,0,lowerLimit,n,area): end: #################################### BoundedScoringPathsAreaNumberHelp:=proc(possibleScores,relativeUpperLimit,startingLevel,relativeLowerLimit,n,area) local count,score: option remember: if n<0 or area>(startingLevel+relativeUpperLimit)*n or area<(startingLevel+relativeLowerLimit)*n then return(0): elif n=0 then if area=0 then #Could end the path now. count:=1: else return(0): fi: else count:=0: end: for score in possibleScores do if score[1]<=n and score[2]>=relativeLowerLimit and score[2]<=relativeUpperLimit then count:=count+BoundedScoringPathsAreaNumberHelp(possibleScores,relativeUpperLimit-score[2],startingLevel+score[2],relativeLowerLimit-score[2],n-score[1],area-score[1]*(startingLevel+score[2]/2)): fi: od: count: end: ########################################################################################################################################### EqualBoundedScoringPathsAreaEqsVars:=proc(possibleScores,upperLimit,lowerLimit,t,z,f,e) local expr,expr2,score,eqs,vars,i: expr:=0: expr2:=0: for score in possibleScores do if score[2]=0 then expr:=expr+t^score[1]: elif score[2]>=lowerLimit and score[2]<=upperLimit then expr2:=expr2+t^score[1]*z^(score[1]*score[2]/2)*e[upperLimit,lowerLimit,score[2]]: fi: od: eqs:={e[upperLimit,lowerLimit,0]=expr2,f[upperLimit,lowerLimit]=1+(expr+e[upperLimit,lowerLimit,0])*f[upperLimit,lowerLimit]}: #Could equivalently put in f[upperLimit,lowerLimit]=1/(1-expr-e[u,l,0]) vars:={f[upperLimit,lowerLimit],seq(e[upperLimit,lowerLimit,i],i in seq(lowerLimit..upperLimit))}: for i in {seq(lowerLimit..upperLimit)} minus {0} do #These e[lowerLimit,upperLimit,c] are "irreducible" (hits 0 only at endpoint) paths from c back to 0. expr:=0: for score in possibleScores do if score[2]=-i then expr:=expr+t^score[1]*z^(score[1]*(i+score[2]/2)): elif i+score[2]>=lowerLimit and i+score[2]<=upperLimit then expr:=expr+t^score[1]*z^(score[1]*(i+score[2]/2))*e[upperLimit,lowerLimit,i+score[2]]: fi: od: eqs:=eqs union {e[upperLimit,lowerLimit,i]=expr}: od: eqs,vars: end: ########################################################################################################################################### AllEqualBoundedScoringPathsArea:=proc(possibleScores,upperLimit,lowerLimit,t,z,f,e): solve(EqualBoundedScoringPathsAreaEqsVars(possibleScores,upperLimit,lowerLimit,t,z,f,e)): end: ########################################################################################################################################### EqualBoundedScoringPathsArea:=proc(possibleScores,upperLimit,lowerLimit,t,z) local f,e: subs(AllEqualBoundedScoringPathsArea(possibleScores,upperLimit,lowerLimit,t,z,f,e),f[upperLimit,lowerLimit]): end: ###################################################################################################### EqualBoundedScoringPathsAreaCoefficients:=proc(possibleScores,upperLimit,lowerLimit,z,N) local t,f: f:=taylor(EqualBoundedScoringPathsArea(possibleScores,upperLimit,lowerLimit,t,z),t,N+1): seq(coeff(f,t,i),i=0..N): end: ###################################################################################################### SpecificEqualBoundedScoringPathsAreaNumber:=proc(possibleScores,relativeUpperLimit,relativeLowerLimit,n,startingLevel,area) local count,score: option remember: if n<0 or area>(startingLevel+relativeUpperLimit)*n or area<(startingLevel+relativeLowerLimit)*n then return(0): elif n=0 then if area<>0 then return(0): elif startingLevel=0 then return(1): fi: end: count:=0: for score in possibleScores do if score[2]>=relativeLowerLimit and score[2]<=relativeUpperLimit then count:=count+SpecificEqualBoundedScoringPathsAreaNumber(possibleScores,relativeUpperLimit-score[2],relativeLowerLimit-score[2],n-score[1],startingLevel+score[2],area-score[1]*(startingLevel+score[2]/2)): fi: od: count: end: ###################################################################################################### SpecificIrreducibleBoundedScoringPathsAreaNumber:=proc(possibleScores,upperLimit,lowerLimit,n,startingLevel,area) local count,score: option remember: if startingLevel=0 then #Must take at least 1 step. count:=0: for score in possibleScores do if score[2]<>0 and score[2]>=lowerLimit and score[2]<=upperLimit then count:=count+SpecificIrreducibleBoundedScoringPathsAreaNumberHelp(possibleScores,upperLimit,lowerLimit,n-score[1],score[2],area-score[1]*score[2]/2): fi: od: count: else SpecificIrreducibleBoundedScoringPathsAreaNumberHelp(possibleScores,upperLimit,lowerLimit,n,startingLevel,area) fi: end: ###################################################################################################### SpecificIrreducibleBoundedScoringPathsAreaNumberHelp:=proc(possibleScores,upperLimit,lowerLimit,n,startingLevel,area) local count,score: option remember: if n<0 or area>(startingLevel+relativeUpperLimit)*n or area<(startingLevel+relativeLowerLimit)*n then return(0): elif startingLevel=0 then if n=0 and area=0 then return(1): else return(0): fi: end: count:=0: for score in possibleScores do if score[2]+startingLevel>=lowerLimit and score[2]+startingLevel<=upperLimit then count:=count+SpecificIrreducibleBoundedScoringPathsAreaNumberHelp(possibleScores,upperLimit,lowerLimit,n-score[1],startingLevel+score[2],area-score[1]*(startingLevel+score[2]/2)): fi: od: count: end: ########################################################################################################################################### ########################################################################################################################################### #Semi-bounded ########################################################################################################################################### ########################################################################################################################################### SemiBoundedScoringPathsAreaEqsVars:=proc(possibleScores,lowerLimit,t,z,k,f,g) local eqs,vars,stepsUp,stepsDown,stepsRight,yvalues,score: eqs,vars:=EqualSemiBoundedScoringPathsAreaEqsVars(possibleScores,lowerLimit,t,z,f,g): stepsUp:={}: stepsDown:={}: stepsRight:={}: yvalues:={-lowerLimit}: for score in possibleScores do if score[2]<0 then stepsDown:=stepsDown union {score}: elif score[2]=0 then stepsRight:=stepsRight union {score}: else stepsUp:=stepsUp union {score}: yvalues:=yvalues union {score[2]-1}: fi: od: eqs:=eqs union {k[lowerLimit](t,z)=1+(g[lowerLimit,lowerLimit](t,z)+add(t^stepR[1]*z^(stepR[1]*lowerLimit),stepR in stepsRight))*k[lowerLimit](t,z)+add(t^stepU[1]*z^(stepU[1]*(lowerLimit+stepU[2]/2))*k[stepU[2]-1+lowerLimit](t*z,z),stepU in stepsUp),seq(k[y+lowerLimit](t,z)=k[lowerLimit](t*z^y,z)+add(g[y-i+lowerLimit,lowerLimit](t*z^i,z)*k[lowerLimit](t*z^i,z),i=0..(y-1)),y in yvalues minus {0})}: vars:=vars union {k[lowerLimit],seq(k[y+lowerLimit],y in yvalues)}: eqs,vars: end: ###################################################################################################### SemiBoundedScoringPathsAreaSeries:=proc(possibleScores,lowerLimit,t,z,k,f,g,N) local eqs,vars,vect,var,maxUp,maxDown,vect2,expressionSubs: eqs,vars:=SemiBoundedScoringPathsAreaEqsVars(possibleScores,lowerLimit,t,z,k,f,g): vect:={}: for var in vars do if op(0,var)=k or (op(0,var)=f and op(var)[1]=op(var)[2]) then vect:=vect union {var(t,z)=1}: else vect:=vect union {var(t,z)=0}: fi: od: maxUp:=max(seq(score[2],score in possibleScores),-lowerLimit): maxDown:=-min(seq(score[2],score in possibleScores),lowerLimit)-1: vect2:={}: while vect<>vect2 do vect2:=vect: # expressionSubs:=vect union {seq(seq(var(t*z^i,z)=subs(t=t*z^i,subs(vect,var(t,z))),i=1..yMax),var in vars minus {g[lowerLimit,lowerLimit]})}: expressionSubs:=vect union {seq(var(t*z,z)=subs(t=t*z,subs(vect,var(t,z))),var in vars minus {g[lowerLimit,lowerLimit]})} union {seq(seq(var(t*z^i,z)=subs(t=t*z^i,subs(vect,var(t,z))),i=2..min(maxUp-1,maxDown)),var in {seq(g[i+lowerLimit,lowerLimit],i=1..maxUp-1),seq(g[lowerLimit,i+lowerLimit],i=1..maxDown),seq(f[lowerLimit,i+lowerLimit],i=0..maxDown)})} union {seq(k[lowerLimit](t*z^i,z)=subs(t=t*z^i,subs(vect,k[lowerLimit](t,z))),i=2..maxUp),f[lowerLimit,lowerLimit](t*z^(-lowerLimit),z)=subs(t=t*z^(-lowerLimit),subs(vect,f[lowerLimit,lowerLimit](t,z)))}: vect:={seq(lhs(eq)=convert(taylor(expand(subs(expressionSubs,rhs(eq))),t=0,N+1),polynom),eq in eqs)}: od: vect: end: ###################################################################################################### SemiBoundedScoringPathsAreaCoefficients:=proc(possibleScores,lowerLimit,z,N) local k0,t,k,f,g: k0:=subs(SemiBoundedScoringPathsAreaSeries(possibleScores,lowerLimit,t,z,k,f,g,N),k[0](t,z)): [seq(coeff(k0,t,i),i=0..N)]: end: ###################################################################################################### SpecificSemiBoundedScoringPathsAreaNumber:=proc(possibleScores,lowerLimit,n,startingLevel,area) local score,zeroScores: zeroScores:={}: for score in possibleScores do if score[1]=0 then if score[2]>=0 then return(infinity): else zeroScores:=zeroScores union {score[2]}: fi: fi: od: SpecificSemiBoundedScoringPathsAreaNumberHelp(possibleScores,lowerLimit,n,startingLevel,zeroScores,area): end: ################################################### #A helper function to compute the number of walks after parsing in SpecificBoundedScoringPathsNumber. SpecificSemiBoundedScoringPathsAreaNumberHelp:=proc(possibleScores,lowerLimit,n,startingLevel,zeroScores,area) option remember: if n<0 or startingLevel0 or nops(irrWalks)>0 do #This will eventually terminate since the coordinates are bounded by [max(stepsUp[2])-1,-max(stepsDown[2])-1]. if nops(walks)>0 then w:=walks[1]: if w[1]>w[2] then #Moving down eqs:=eqs union {f[op(w)](t,z)=add(g[w[1]-i,0](t*z^i,z)*f[0,w[2]-i](t*z^i,z),i=0..w[2])}: walks:=walks union {seq([0,w[2]-i],i=0..(w[2]-1))}: irrWalks:=irrWalks union {seq([w[1]-i,0],i=0..w[2])}: elif w[1]=w[2] then #Staying flat eqs:=eqs union {f[op(w)](t,z)=add(g[w[1]-i,0](t*z^i,z)*f[0,w[2]-i](t*z^i,z),i=0..(w[2]-1))+f[0,0](t*z^(w[2]),z)}: walks:=walks union {seq([0,w[2]-i],i=0..(w[2]-1))}: irrWalks:=irrWalks union {seq([w[1]-i,0],i=0..(w[2]-1))}: else #Moving up eqs:=eqs union {f[op(w)](t,z)=add(g[w[1]-i,0](t*z^i,z)*f[0,w[2]-i](t*z^i,z),i=0..(w[1]-1))+f[0,0](t*z^(w[1]),z)*g[0,w[2]-w[1]](t*z^(w[1]),z)}: walks:=walks union {seq([0,w[2]-i],i=0..(w[1]-1))}: irrWalks:=irrWalks union {seq([w[1]-i,0],i=0..(w[1]-1)),[0,w[2]-w[1]]}: fi: doneWalks:=doneWalks union {w}: walks:=walks minus doneWalks: irrWalks:=irrWalks minus doneIrrWalks: else #nops(irrWalks)>0 iw:=irrWalks[1]: if iw[1]>0 then eqs:=eqs union {g[op(iw)](t,z)=add(t^stepd[1]*z^(stepd[1]*(lowerLimit-stepd[2]/2))*f[iw[1]-1,-stepd[2]-1](t*z,z),stepd in stepsDown)}: walks:=walks union {seq([iw[1]-1,-stepd[2]-1],stepd in stepsDown)}: else #iw[2]>0 eqs:=eqs union {g[op(iw)](t,z)=add(t^stepu[1]*z^(stepu[1]*(lowerLimit+stepu[2]/2))*f[stepu[2]-1,iw[2]-1](t*z,z),stepu in stepsUp)}: walks:=walks union {seq([stepu[2]-1,iw[2]-1],stepu in stepsUp)}: fi: doneIrrWalks:=doneIrrWalks union {iw}: irrWalks:=irrWalks minus {iw}: walks:=walks minus doneWalks: fi: od: #Currently f[a,b] is the g.f. for the number of walks from (0,a) to (n,b) that stay above y=0. #And g[a,b] is the g.f. for the number of irreducible walks from (0,a) to (n,b). #The following adjusts this so f[a,b] is the g.f. for the number of walks from (0,a) to (n,b) that stay above the lowerLimit. Similar for g[a,b]. subs({seq(f[op(w)]=f[w[1]+lowerLimit,w[2]+lowerLimit],w in doneWalks),seq(g[op(iw)]=g[iw[1]+lowerLimit,iw[2]+lowerLimit],iw in doneIrrWalks)},eqs),{seq(f[w[1]+lowerLimit,w[2]+lowerLimit],w in doneWalks),seq(g[iw[1]+lowerLimit,iw[2]+lowerLimit],iw in doneIrrWalks)}: end: ###################################################################################################### EqualSemiBoundedScoringPathsAreaSeries:=proc(possibleScores,lowerLimit,t,z,f,g,N) local eqs,vars,vect,var,vect2,expressionSubs,maxUp,maxDown: eqs,vars:=EqualSemiBoundedScoringPathsAreaEqsVars(possibleScores,lowerLimit,t,z,f,g): vect:={}: for var in vars do if op(0,var)=f and op(var)[1]=op(var)[2] then vect:=vect union {var(t,z)=1}: else vect:=vect union {var(t,z)=0}: fi: od: maxUp:=max(seq(score[2],score in possibleScores),-lowerLimit)-1: maxDown:=-min(seq(score[2],score in possibleScores),lowerLimit)-1: vect2:={}: while vect<>vect2 do vect2:=vect: expressionSubs:=vect union {seq(var(t*z,z)=subs(t=t*z,subs(vect,var(t,z))),var in vars minus {g[lowerLimit,lowerLimit]}), seq(seq(var(t*z^i,z)=subs(t=t*z^i,subs(vect,var(t,z))),i=2..min(maxUp,maxDown)),var in {seq(g[i+lowerLimit,lowerLimit],i=1..maxUp),seq(g[lowerLimit,i+lowerLimit],i=1..maxDown),seq(f[lowerLimit,i+lowerLimit],i=0..maxDown)}), f[lowerLimit,lowerLimit](t*z^(-lowerLimit),z)=subs(t=t*z^(-lowerLimit),subs(vect,f[lowerLimit,lowerLimit](t,z)))}: vect:={seq(lhs(eq)=convert(taylor(expand(subs(expressionSubs,rhs(eq))),t=0,N+1),polynom),eq in eqs)}: od: vect: end: ###################################################################################################### EqualSemiBoundedScoringPathsAreaCoefficients:=proc(possibleScores,lowerLimit,z,N) local f0,t,g: f0:=subs(EqualSemiBoundedScoringPathsAreaSeries(possibleScores,lowerLimit,t,z,f,g,N),f[0,0](t,z)): [seq(coeff(f0,t,i),i=0..N)]: end: ###################################################################################################### SpecificEqualSemiBoundedScoringPathsAreaNumber:=proc(possibleScores,lowerLimit,n,startingLevel,area) local zeroPstep,zeroNstep,score,maxDescentRate: zeroPstep:=false: zeroNstep:=false: for score in possibleScores do if score[1]=0 then if score[2]>0 then zeroPstep:=true: else #score[2]<0 zeroNstep:=true: fi: fi: od: if zeroPstep then if zeroNstep then return(infinity): else maxDescentRate:=0: for score in possibleScores do if score[2]<0 then maxDescentRate:=min(maxDescentRate,score[2]/score[1]): fi: od: return(SpecificEqualSemiBoundedScoringPathsAreaNumberP(possibleScores,lowerLimit,n,startingLevel,maxDescentRate,area)): fi: fi: SpecificEqualSemiBoundedScoringPathsAreaNumberN(possibleScores,lowerLimit,n,startingLevel,area): end: ################################################# #A helper function that works if there are no (0,+) steps. SpecificEqualSemiBoundedScoringPathsAreaNumberN:=proc(possibleScores,lowerLimit,n,startingLevel,area) option remember: if n<0 or startingLevel0 then return(0): elif startingLevel=0 then return(1): fi: fi: add(SpecificEqualSemiBoundedScoringPathsAreaNumberN(possibleScores,lowerLimit,n-score[1],startingLevel+score[2],area-score[1]*(startingLevel+score[2]/2)),score in possibleScores): end: ################################################# #A helper function that works if there are no (0,-) steps. #Inputting maxDescentRate just saves some computation time. It is determined by possibleScores. SpecificEqualSemiBoundedScoringPathsAreaNumberP:=proc(possibleScores,lowerLimit,n,startingLevel,maxDescentRate,area) option remember: if n<0 or startingLevel0 or area0 then return(0): elif startingLevel=0 then return(1): fi: fi: add(SpecificEqualSemiBoundedScoringPathsAreaNumberP(possibleScores,lowerLimit,n-score[1],startingLevel+score[2],maxDescentRate,area-score[1]*(startingLevel+score[2]/2)),score in possibleScores): end: ###################################################################################################### SpecificIrreducibleSemiBoundedScoringPathsAreaNumber:=proc(possibleScores,n,startingLevel,area) local zeroPstep,zeroNstep,score,maxDescentRate,count: zeroPstep:=false: zeroNstep:=false: for score in possibleScores do if score[1]=0 then if score[2]>0 then zeroPstep:=true: else #score[2]<0 zeroNstep:=true: fi: fi: od: if zeroPstep then if zeroNstep then return(infinity): else maxDescentRate:=0: for score in possibleScores do if score[2]<0 then maxDescentRate:=min(maxDescentRate,score[2]/score[1]): fi: od: if startingLevel<=0 then count:=0: for score in possibleScores do if score[2]>0 then #There must be a first step. And it must be positive. count:=count+SpecificIrreducibleSemiBoundedScoringPathsAreaNumberP(possibleScores,min(startingLevel+1,0),n-score[1],startingLevel+score[2],maxDescentRate,area-score[1]*(startingLevel+score[2]/2)): fi: od: return(count): else return(SpecificIrreducibleSemiBoundedScoringPathsAreaNumberP(possibleScores,0,n,startingLevel,maxDescentRate,area)): fi: fi: fi: if startingLevel<=0 then count:=0: for score in possibleScores do if score[2]>0 then #There must be a first step. And it must be positive. count:=count+SpecificIrreducibleSemiBoundedScoringPathsAreaNumberN(possibleScores,min(startingLevel+1,0),n-score[1],startingLevel+score[2],area-score[1]*(startingLevel+score[2]/2)): fi: od: count else SpecificIrreducibleSemiBoundedScoringPathsAreaNumberN(possibleScores,0,n,startingLevel,area): fi: end: ################################################# #A helper function that works if there are no (0,+) steps. SpecificIrreducibleSemiBoundedScoringPathsAreaNumberN:=proc(possibleScores,lowerLimit,n,startingLevel,area) option remember: if n<0 or startingLevel0 then return(0): elif startingLevel=0 then return(1): fi: fi: add(SpecificIrreducibleSemiBoundedScoringPathsAreaNumberN(possibleScores,lowerLimit,n-score[1],startingLevel+score[2],area-score[1]*(startingLevel+score[2]/2)),score in possibleScores): end: ################################################# #A helper function that works if there are no (0,-) steps. #Inputting maxDescentRate just saves some computation time. It is determined by possibleScores. SpecificIrreducibleSemiBoundedScoringPathsNumberP:=proc(possibleScores,lowerLimit,n,startingLevel,maxDescentRate,area) option remember: if n<0 or startingLevel0 or area0 then return(0): elif startingLevel=0 then return(1): fi: fi: add(SpecificIrreducibleSemiBoundedScoringPathsAreaNumberP(possibleScores,lowerLimit,n-score[1],startingLevel+score[2],maxDescentRate,area-score[1]*(startingLevel+score[2]/2)),score in possibleScores): end: ########################################################################################################################################### ########################################################################################################################################### #Unbounded ########################################################################################################################################### ########################################################################################################################################### UnBoundedScoringPathsArea:=proc(possibleScores,t,z,f): f(t,z)=1+add(t^score[1]*z^(score[1]*score[2]/2)*f(t*z^score[2],z),score in possibleScores): end: ###################################################################################################### UnBoundedScoringPathsAreaCoefficients:=proc(possibleScores,z,N) local t,f,f0,expr,ysubs,i: expr:=rhs(UnBoundedScoringPathsArea(possibleScores,t,z,f)): f0:=1: ysubs:={seq(score[2],score in possibleScores)}: #So we know exactly which substitutions are needed. for i from 1 to N do f0:=convert(taylor(expand(subs({seq(f(t*z^y,z)=subs(t=t*z^y,f0),y in ysubs)},expr)),t=0,i+1),polynom): od: [seq(coeff(f0,t,i),i=0..N)]: end: ###################################################################################################### UnBoundedScoringPathsAreaNumber:=proc(possibleScores,n,area): if member(0,{seq(score[1],score in possibleScores)}) then return(infinity): fi: UnBoundedScoringPathsAreaNumber1(possibleScores,0,n,area): end: ################################################# #A helper function after ensuring no infinite recursion. UnBoundedScoringPathsAreaNumber1:=proc(possibleScores,currentLevel,n,area) option remember: if n<0 then return(0): elif n=0 then if area=0 then return(1): else return(0): fi: fi: add(UnBoundedScoringPathsAreaNumber1(possibleScores,currentLevel+score[2],n-score[1],area-score[1]*(currentLevel+score[2]/2)),score in possibleScores): end: ########################################################################################################################################### EqualUnBoundedScoringPathsAreaEqsVars:=proc(possibleScores,t,z,B,h,f,g) local stepsUp,stepsDown,stepsRight,score,maxJump,eqs,irrEqs,hEqs,walks,w: stepsUp:={}: stepsDown:={}: stepsRight:={}: for score in possibleScores do if score[2]<0 then stepsDown:=stepsDown union {score}: elif score[2]=0 then stepsRight:=stepsRight union {score}: else stepsUp:=stepsUp union {score}: fi: od: maxJump:=max(seq(abs(score[2]),score in possibleScores))-1: #The h[i] equations written out on multiple lines for ease of reading code. # h[0](t,z)=g[0,0](t,z)+g[0,0](t,1/z)+add(add(g[ls[2]-i,0](t,1/z)*t^ls[1]*z^(ls[1]*(i-ls[2]/2))*h[i](t,z),i=1..(ls[2]-1)),ls in stepsUp)+add(add(g[0,i](t,z)*t^ls[1]*z^(ls[1]*(i+ls[2]/2))*h[i+ls[2]](t,z),i=1..(-ls[2]-1)),ls in stepsDown) # h[0] is partially why irreducible walks do not include steps to the right. If g[0,0] did, then I would have to write h[0]=2*g[0,0]-stepsRight, which is less elegant. # seq(h[j](t,z)=g[j,0](t,z)+add(add(f[j-1,i-1](t*z,z)*t^ls[1]*z^(ls[1]*(i+ls[2]/2))*h[i+ls[2]](t,z),i=1..(-ls[2]-1)),ls in stepsDown),j=1..maxJump) # seq(h[-j](t,z)=g[0,j](t,1/z)+add(add(f[ls[2]-i-1,j-1](t/z,1/z)*t^ls[1]*z^(ls[1]*(i-ls[2]/2))*h[i](t,z),i=1..(ls[2]-1)),ls in stepsUp),j=1..maxJump) hEqs:={h[0](t,z)=g[0,0](t,z)+g[0,0](t,1/z)+add(add(g[ls[2]-i,0](t,1/z)*t^ls[1]*z^(ls[1]*(i-ls[2]/2))*h[i](t,z),i=1..(ls[2]-1)),ls in stepsUp)+add(add(g[0,i](t,z)*t^ls[1]*z^(ls[1]*(i+ls[2]/2))*h[i+ls[2]](t,z),i=1..(-ls[2]-1)),ls in stepsDown),seq(h[j](t,z)=g[j,0](t,z)+add(add(f[j-1,i-1](t*z,z)*t^ls[1]*z^(ls[1]*(i+ls[2]/2))*h[i+ls[2]](t,z),i=1..(-ls[2]-1)),ls in stepsDown),j=1..maxJump),seq(h[-j](t,z)=g[0,j](t,1/z)+add(add(f[ls[2]-i-1,j-1](t/z,1/z)*t^ls[1]*z^(ls[1]*(i-ls[2]/2))*h[i](t,z),i=1..(ls[2]-1)),ls in stepsUp),j=1..maxJump)}: #We cannot simply call EqualSemiBoundedScoringPathsAreaEqsVars(possibleScores,0,t,f,g) for the remaining equations since there may be some walks missing. #The irreducible walk equations: # g[0,0](t,z)=add(add(t^(stepU[1]+stepD[1])*z^((stepU[1]*stepU[2]-stepD[1]*stepD[2])/2)*f[stepU[2]-1,-stepD[2]-1](t*z,z),stepD in stepsDown),stepU in stepsUp) # seq(g[0,j](t,z)=add(t^stepU[1]*z^(stepU[1]*stepU[2]/2)*f[stepU[2]-1,j-1](t*z,z),stepU in stepsUp),j=1..maxJump) # seq(g[j,0](t,z)=add(t^stepD[1]*z^(-stepD[1]*stepD[2]/2)*f[j-1,-stepD[2]-1](t*z,z),stepD in stepsDown),j=1..maxJump) irrEqs:={g[0,0](t,z)=add(add(t^(stepU[1]+stepD[1])*z^((stepU[1]*stepU[2]-stepD[1]*stepD[2])/2)*f[stepU[2]-1,-stepD[2]-1](t*z,z),stepD in stepsDown),stepU in stepsUp),seq(g[0,j](t,z)=add(t^stepU[1]*z^(stepU[1]*stepU[2]/2)*f[stepU[2]-1,j-1](t*z,z),stepU in stepsUp),j=1..maxJump),seq(g[j,0](t,z)=add(t^stepD[1]*z^(-stepD[1]*stepD[2]/2)*f[j-1,-stepD[2]-1](t*z,z),stepD in stepsDown),j=1..maxJump)}: eqs:={f[0,0](t,z)=1+(g[0,0](t,z)+add(t^stepR[1],stepR in stepsRight))*f[0,0](t,z)}: walks:={seq(seq([j,i],i=0..(max(seq(-stepD[2],stepD in stepsDown))-1)),j=0..(maxJump-1)),seq(seq([i,j],i=0..(max(seq(stepU[2],stepU in stepsUp))-1)),j=0..(maxJump-1)), seq(seq([stepU[2]-1,-stepD[2]-1],stepD in stepsDown),stepU in stepsUp)} minus {[0,0]}: #[0,0] was already done. for w in walks do if w[1]>w[2] then #Moving down eqs:=eqs union {f[op(w)](t,z)=add(g[w[1]-i,0](t*z^i,z)*f[0,w[2]-i](t*z^i,z),i=0..w[2])}: elif w[1]=w[2] then #Staying flat eqs:=eqs union {f[op(w)](t,z)=add(g[w[1]-i,0](t*z^i,z)*f[0,w[2]-i](t*z^i,z),i=0..(w[2]-1))+f[0,0](t*z^(w[2]),z)}: else #Moving up eqs:=eqs union {f[op(w)](t,z)=add(g[w[1]-i,0](t*z^i,z)*f[0,w[2]-i](t*z^i,z),i=0..(w[1]-1))+f[0,0](t*z^(w[1]),z)*g[0,w[2]-w[1]](t*z^(w[1]),z)}: fi: od: eqs union irrEqs union hEqs union {B(t,z)=1+(h[0](t,z)+add(t^sr[1],sr in stepsRight))*B(t,z)}, {B,f[0,0],seq(f[op(w)],w in walks),seq(g[0,j],j=0..maxJump),seq(g[j,0],j=1..maxJump),seq(h[j],j=-maxJump..maxJump)}: end: ###################################################################################################### EqualUnBoundedScoringPathsAreaSeries:=proc(possibleScores,t,z,B,h,f,g,N) local eqs,vars,vect,var,vect2,maxUp,maxDown,maxJump,expressionSubs: eqs,vars:=EqualUnBoundedScoringPathsAreaEqsVars(possibleScores,t,z,B,h,f,g): vect:={}: for var in vars do if var=B or (op(0,var)=f and op(var)[1]=op(var)[2]) then vect:=vect union {var(t,z)=1}: else vect:=vect union {var(t,z)=0}: fi: od: maxUp:=max(seq(score[2],score in possibleScores))-1: maxDown:=-min(seq(score[2],score in possibleScores))-1: maxJump:=max(seq(abs(score[2]),score in possibleScores))-1: vect2:={}: while vect<>vect2 do vect2:=vect: expressionSubs:=vect union {seq(var(t*z,z)=subs(t=t*z,subs(vect,var(t,z))),var in vars minus {g[0,0]}), seq(seq(var(t*z^i,z)=subs(t=t*z^i,subs(vect,var(t,z))),i=2..min(maxUp,maxDown)),var in {seq(g[i,0],i=1..maxUp),seq(g[0,i],i=1..maxDown),seq(f[0,i],i=0..maxDown)}), seq(var(t,1/z)=subs(z=1/z,subs(vect,var(t,z))),var in {seq(g[i,0],i=1..maxJump),seq(g[0,i],i=0..maxJump)}),seq(seq(f[i,j](t/z,1/z)=subs({t=t/z,z=1/z},subs(vect,var(t,z))),i=1..maxJump-1),j=1..maxJump)}: vect:={seq(lhs(eq)=convert(taylor(expand(subs(expressionSubs,rhs(eq))),t=0,N+1),polynom),eq in eqs)}: od: vect: end: ###################################################################################################### EqualUnBoundedScoringPathsAreaCoefficients:=proc(possibleScores,z,N) local B0,t,B,h,f,g,L: B0:=subs(EqualUnBoundedScoringPathsAreaSeries(possibleScores,t,z,B,h,f,g,N),B(t,z)): L:=[seq(expand(coeff(B0,t,i)),i=0..N)]: L:=simplify(L) assuming z>0: [seq(expand(L[i]),i=1..nops(L))]: end: ###################################################################################################### SpecificUnBoundedScoringPathsAreaNumber:=proc(possibleScores,n,startingLevel,area) local zeroPstep,zeroNstep,score,maxRate: zeroPstep:=false: zeroNstep:=false: for score in possibleScores do if score[1]=0 then if score[2]>0 then zeroPstep:=true: else #score[2]<0 zeroNstep:=true: fi: fi: od: if zeroPstep then if zeroNstep then return(infinity): else maxRate:=0: for score in possibleScores do if score[2]<0 then #Then score[1]<>0 since zeroNstep=false maxRate:=min(maxRate,score[2]/score[1]): fi: od: return(SpecificUnBoundedScoringPathsAreaNumberP(possibleScores,n,startingLevel,maxRate,area)): fi: fi: maxRate:=0: for score in possibleScores do if score[2]>0 then #Then score[1]<>0 since zeroPstep=false maxRate:=max(maxRate,score[2]/score[1]): fi: od: SpecificUnBoundedScoringPathsAreaNumberN(possibleScores,n,startingLevel,maxRate,area): end: ################################################# #A helper function that works if there are no (0,+) steps. #Inputting maxRate just saves some computation time. It is determined by possibleScores. maxRate>0. SpecificUnBoundedScoringPathsAreaNumberN:=proc(possibleScores,n,startingLevel,maxRate,area) option remember: if n<0 or startingLevel+n*maxRate<0 then#or area>n*(startingLevel+maxRate/2) then return(0): elif n=0 then if area<>0 then return(0): elif startingLevel=0 then return(1): fi: fi: add(SpecificUnBoundedScoringPathsAreaNumberN(possibleScores,n-score[1],startingLevel+score[2],maxRate,area-score[1]*(startingLevel+score[2]/2)),score in possibleScores): end: ################################################# #A helper function that works if there are no (0,-) steps. #Inputting maxRate just saves some computation time. It is determined by possibleScores. maxRate<0. SpecificUnBoundedScoringPathsAreaNumberP:=proc(possibleScores,n,startingLevel,maxRate,area) option remember: if n<0 or startingLevel+n*maxRate>0 then#or area0 then return(0): elif startingLevel=0 then return(1): fi: fi: add(SpecificUnBoundedScoringPathsAreaNumberP(possibleScores,n-score[1],startingLevel+score[2],maxRate,area-score[1]*(startingLevel+score[2]/2)),score in possibleScores): end: ###################################################################################################### SpecificIrreducibleUnBoundedScoringPathsAreaNumber:=proc(possibleScores,n,startingLevel,area) local zeroPstep,zeroNstep,score,maxRate,count: zeroPstep:=false: zeroNstep:=false: for score in possibleScores do if score[1]=0 then if score[2]>0 then zeroPstep:=true: else #score[2]<0 zeroNstep:=true: fi: fi: od: if zeroPstep then if zeroNstep then return(infinity): else maxRate:=0: for score in possibleScores do if score[2]<0 then #Then score[1]<>0 since zeroNstep=false maxRate:=min(maxRate,score[2]/score[1]): fi: od: if startingLevel=0 then count:=0: for score in possibleScores do if score[2]<>0 then #Must take at least 1 step that changes altitude. count:=count+SpecificIrreducibleUnBoundedScoringPathsAreaNumberP(possibleScores,n-score[1],score[2],maxRate,area-score[1]*(startingLevel+score[2]/2)): fi: od: return(count): else return(SpecificIrreducibleUnBoundedScoringPathsAreaNumberP(possibleScores,n,startingLevel,maxRate,area)): fi: fi: fi: maxRate:=0: for score in possibleScores do if score[2]>0 then #Then score[1]<>0 since zeroPstep=false maxRate:=max(maxRate,score[2]/score[1]): fi: od: if startingLevel=0 then count:=0: for score in possibleScores do if score[2]<>0 then #Must take at least 1 step that changes altitude. count:=count+SpecificIrreducibleUnBoundedScoringPathsAreaNumberN(possibleScores,n-score[1],score[2],maxRate,area-score[1]*(startingLevel+score[2]/2)): fi: od: count: else SpecificIrreducibleUnBoundedScoringPathsAreaNumberN(possibleScores,n,startingLevel,maxRate,area): fi: end: ################################################# #A helper function that works if there are no (0,+) steps. #Inputting maxRate just saves some computation time. It is determined by possibleScores. SpecificIrreducibleUnBoundedScoringPathsAreaNumberN:=proc(possibleScores,n,startingLevel,maxRate,area) option remember: if n<0 or startingLevel+n*maxRate<0 then return(0): elif startingLevel=0 then if n=0 and area=0 then return(1): else return(0): fi: fi: add(SpecificIrreducibleUnBoundedScoringPathsAreaNumberN(possibleScores,n-score[1],startingLevel+score[2],maxRate,area-score[1]*(startingLevel+score[2]/2)),score in possibleScores): end: ################################################# #A helper function that works if there are no (0,-) steps. #Inputting maxRate just saves some computation time. It is determined by possibleScores. SpecificIrreducibleUnBoundedScoringPathsAreaNumberP:=proc(possibleScores,n,startingLevel,maxRate,area) option remember: if n<0 or startingLevel+n*maxRate>0 then return(0): elif startingLevel=0 then if n=0 and area=0 then return(1): else return(0): fi: fi: add(SpecificIrreducibleUnBoundedScoringPathsAreaNumberP(possibleScores,n-score[1],startingLevel+score[2],maxRate,area-score[1]*(startingLevel+score[2]/2)),score in possibleScores): end: ########################################################################################################################################### #Producing random step sets. #RandomStepSet(numSteps,xBound,yBound): produces a set of steps each with x-value between 0 and xBound and y-value between -yBound and yBound. #There cannot be a [0,0] step, thus we need yBound>=1. And there must be some step with x-value>0 so we should also have xBound>=1. #Try RandomStepSet(8,4,3). RandomStepSet:=proc(numSteps,xBound,yBound) local steps,rax,ray,xValue,yValue: steps:={}: rax:=rand(0..xBound): ray:=rand(-yBound..yBound): while nops(steps)=1. And there must be some step with x-value>0 so we should also have xBound>=1. #There also cannot be both (+) and (-) zero steps. #Try RandomZeroStepSet(8,4,3). RandomZeroStepSet:=proc(numSteps,xBound,yBound) local steps,rax,ray,xValue,yValue,SET: steps:={}: rax:=rand(0..xBound): ray:=rand(-yBound..yBound): SET:=0: while nops(steps)=1. And there must be some step with x-value>0 so we should also have xBound>=1. #There also cannot be (+) zero steps. #Try RandomSemiBoundedStepSet(8,4,3). RandomSemiBoundedStepSet:=proc(numSteps,xBound,yBound) local steps,rax,ray,xValue,yValue: steps:={}: rax:=rand(0..xBound): ray:=rand(-yBound..yBound): while nops(steps)0 and step[2]<=upperLimit-lowerLimit then #Ensures this step could feasibly be used. positiveStep:=true: elif step[2]<0 and step[2]>=lowerLimit-upperLimit then #Ensures this step could feasibly be used. negativeStep:=true: else zeroSteps:=zeroSteps union {step[1]}: fi: od: if not (negativeStep and positiveStep) then if nops(zeroSteps)=0 then print(`The problem is trivial. There is no walk back to the x-axis.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(FAIL): elif nops(zeroSteps)=1 then print(cat(`The problem is trivial. Walks returning to the x-axis consist of only repeated use of the one step `, zeroSteps[1])): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(FAIL): else print(`The only relevant steps are:`): print(zeroSteps): gu:=EqualBoundedScoringPathsArea(zeroSteps,upperLimit,lowerLimit,x,z,f): print(`The problem is equivalent to summing to n in different combinations using parts of size:`): print(seq(st,st in zeroSteps)): print(``): fi: else gu:=EqualBoundedScoringPathsArea(Steps,upperLimit,lowerLimit,x,z,f): fi: print(`Let f(x,z) be its (ordinary) generating function:`): print(f(x,z)=Sum(Sum(A(n,a)*x^n*z^a,n=0..infinity),a=-infinity..infinity)): print(``): print(`Then f(x,z) is given by`): print(``): print(gu): print(``): print(`and in Maple input format`): print(``): lprint(gu): print(``): print(cat(`For the sake of the OEIS, here are the first `, K+1,` terms (starting at n=0).`)): mu:=taylor(gu,x=0,K+1): lprint([seq( expand(coeff(mu,x,i)), i=0..K)]): #The following might be faster. # lprint([seq(add(SpecificEqualBoundedScoringPathsNumber(Steps,upperLimit,lowerLimit,n1,0,a1/2)*z^(a1/2),a1=-K^2..K^2),n1=0..K)]): print(``): print(`----------------------------`): print(cat(`This ends this paper that took `, time()-t0, ` seconds to generate.`)): print(`----------------------------------------------------------------------------------------------------------------`): end: ########################################################################################################################################### #PaperBounded2Area(Steps,K): inputs a set of steps, Steps, and a positive integer K, outputs an article about the #generating function of walks from the origin back to [n,0] for some n that never go further than one step from the x-axis. #Includes information about the area under the curve of each walk encoded in z^a. #c*t^n*z^a indicates there are c paths of length n with area a under the walk. #It also outputs the first K terms, for the sake of the OEIS. #Try: #PaperBounded2Area({[1,2],[1,-2],[1,3],[1,-3]},20); PaperBounded2Area:=proc(Steps,K) local t0,lowerLimit,zeroSteps,upperLimit,upstep,downstep,step,gu,mu: t0:=time(): print(cat(`On the Generating functions of Area-Counting Enumerating sequences for Bounded Paths with set of steps `, Steps,`.`)): print(``): print(`By Bryan Ek's Maple Package ScoringPaths.txt `): print(``): print(`Theorem:`): print(cat(`Let A(n,a) be the number of ways of walking from (0,0) to (n,0) using the steps `, Steps, `, never going further than one step from the x-axis, and having area a under the curve.`)): print(``): lowerLimit:=1: zeroSteps:={}: upperLimit:=-1: upstep:=false: downstep:=false: for step in (convert(Steps,set) minus {[0,0]}) while not (upstep and downstep) do #while not (positiveStep and negativeStep and zeroStep) do #This doesn’t actually save time since we would need all of the zero steps anyway. if step[2]>0 then lowerLimit:=min(lowerLimit,-step[2]): if step[1]=0 then upstep:=true: fi: elif step[2]<0 then upperLimit:=max(upperLimit,-step[2]): if step[1]=0 then downstep:=true: fi: else zeroSteps:=zeroSteps union {step}: fi: od: if upstep and downstep then print(`There are an infinite number of ways to have walks of length n since you included step(s) directly up and down.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(FAIL): elif lowerLimit>0 or upperLimit<0 then if nops(zeroSteps)=0 then print(`The problem is trivial. There is no walk back to the x-axis.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(FAIL): elif nops(zeroSteps)=1 then print(cat(`The problem is trivial. Walks returning to the x-axis consist of only repeated use of the one step `, zeroSteps[1])): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(FAIL): else print(`The only relevant steps are:`): print(zeroSteps): gu:=EqualBoundedScoringPathsArea(zeroSteps,upperLimit,lowerLimit,x,z,f): print(`The problem is equivalent to summing to n in different combinations using parts of size:`): print(seq(st[1],st in zeroSteps)): print(``): fi: else gu:=EqualBoundedScoringPathsArea(Steps,upperLimit,lowerLimit,x,z,f): fi: print(`Let f(x,z) be its (ordinary) generating function:`): print(f(x,z)=Sum(Sum(A(n,a)*x^n*z^a,n=0..infinity),a=-infinity..infinity)): print(``): print(`Then f(x,z) is given by`): print(``): print(gu): print(``): print(`and in Maple input format`): print(``): lprint(gu): print(``): print(cat(`For the sake of the OEIS, here are the first `, K+1,` terms (starting at n=0).`)): mu:=taylor(gu,x=0,K+1): lprint([seq(expand(coeff(mu,x,i)), i=0..K)]): #The following might be faster. # lprint([seq(add(SpecificEqualBoundedScoringPathsNumber(Steps,upperLimit,lowerLimit,n1,0,a1/2)*z^(a1/2),a1=-K^2..K^2),n1=0..K)]): print(``): print(`----------------------------`): print(cat(`This ends this paper that took `, time()-t0, ` seconds to generate.`)): print(`----------------------------------------------------------------------------------------------------------------`): end: ########################################################################################################################################### #PaperSemiBoundedArea(Steps,K): inputs a set of steps, Steps, and a positive integer K, outputs an article about the #generating function of walks from the origin back to [n,0] for some n that never go below the x-axis. #Includes information about the area under the curve of each walk encoded in z^a. #c*t^n*z^a indicates there are c paths of length n with area a under the walk. #It also outputs the first K terms, for the sake of the OEIS. #Try: #PaperSemiBoundedArea({[1,1],[1,-1],[1,0]},40); PaperSemiBoundedArea:=proc(Steps,K) local t0,positiveStep,zeroSteps,maxRateUp,step,gu,eq: t0:=time(): print(cat(`On the Generating Functions of Area-Counting Enumerating sequences for Generalized Paths with set of steps `, Steps,`.`)): print(``): print(`By Bryan Ek's Maple Package ScoringPaths.txt `): print(``): print(`Theorem:`): print(cat(`Let A(n,a) be the number of ways of walking from (0,0) using the steps `, Steps, `, never going below the x-axis, and having area a under the curve.`)): print(``): positiveStep:=false: # zeroStep:=false: zeroSteps:={}: maxRateUp:=0: for step in (convert(Steps,set) minus {[0,0]}) do #while not (positiveStep and negativeStep and zeroStep) do #This doesn’t actually save time since we would need all of the zero steps anyway. if step[2]>0 then if step[1]=0 then print(`There are an infinite number of ways to have meanders of length n since you included step(s) directly up.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(FAIL): else maxRateUp:=max(maxRateUp,step[2]/step[1]): positiveStep:=true: fi: elif step[2]=0 then zeroSteps:=zeroSteps union {step}: fi: od: if not positiveStep then if nops(zeroSteps)=0 then print(`The problem is trivial. There is no non-stationary walk.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(FAIL): elif nops(zeroSteps)=1 then print(cat(`The problem is trivial. Walks consist of only repeated use of the one step `, zeroSteps[1])): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(FAIL): else print(`The only relevant steps are:`): print(zeroSteps): print(`The problem is equivalent to summing to n in different combinations using parts of size:`): print(seq(st[1],st in zeroSteps)): print(``): print(`The generating function (all walks have area 0 under the curve) is given by`): print(1/(1-add(t^zs[1],zs in zeroSteps))): print(`And in Maple input format:`): lprint(1/(1-add(t^zs[1],zs in zeroSteps))): return(FAIL): fi: else gu:=SemiBoundedScoringPathsAreaEqsVars(Steps,0,x,z,k,f,g)[1]: fi: print(`Let k(x,z) be its (ordinary) generating function:`): print(k(x,z)=Sum(Sum(A(n,a)*x^n*z^a,n=0..infinity),a=0..infinity)): print(``): print(`Then k(x,z) satisfies`): print(``): print(k(x,z)=subs(k[0]=k,subs(gu,k[0](x,z)))): print(``): print(`The rest of the system satisfies`): for eq in gu minus {k[0](x,z)=subs(gu,k[0](x,z))} do print(subs(k[0]=k,eq)): od: print(``): print(`and in Maple input format`): for eq in gu do lprint(subs(k[0]=k,eq)): od: print(``): print(cat(`For the sake of the OEIS, here are the first `, K+1,` terms (starting at n=0).`)): # lprint(CodeTools[Usage](SemiBoundedScoringPathsAreaCoefficients(Steps,0,z,K))): #The following is typically faster (better at handling larger step sizes). lprint([seq(add(SpecificSemiBoundedScoringPathsAreaNumber(Steps,0,n1,0,a1/2)*z^(a1/2),a1=0..n1^2*maxRateUp),n1=0..K)]): print(``): print(`----------------------------`): print(cat(`This ends this paper that took `, time()-t0, ` seconds to generate.`)): print(`----------------------------------------------------------------------------------------------------------------`): end: ########################################################################################################################################### #PaperEqualSemiBoundedArea(Steps,K): inputs a set of steps, Steps, and a positive integer K, outputs an article about the #generating function of walks from the origin back to [n,0] for some n that never go below the x-axis. #Includes information about the area under the curve of each walk encoded in z^a. #c*t^n*z^a indicates there are c paths of length n with area a under the walk. #It also outputs the first K terms, for the sake of the OEIS. #Try: #PaperEqualSemiBoundedArea({[1,1],[1,-1],[1,0]},40); PaperEqualSemiBoundedArea:=proc(Steps,K) local t0,positiveStep,zeroSteps,negativeStep,upstep,downstep,maxRateUp,maxRateDown,step,gu,eq: t0:=time(): print(cat(`On the Generating Functions of Area-Counting Enumerating Sequences for Generalized Dyck Paths with set of steps `, Steps,`.`)): print(``): print(`By Bryan Ek's Maple Package ScoringPaths.txt `): print(``): print(`Theorem:`): print(cat(`Let A(n,a) be the number of ways of walking from (0,0) to (n,0) using the steps `, Steps, `, never going below the x-axis, and having area a under the curve.`)): print(``): positiveStep:=false: # zeroStep:=false: zeroSteps:={}: negativeStep:=false: upstep:=false: downstep:=false: maxRateUp:=0: maxRateDown:=0: for step in (convert(Steps,set) minus {[0,0]}) while not (upstep and downstep) do #while not (positiveStep and negativeStep and zeroStep) do #This doesn’t actually save time since we would need all of the zero steps anyway. if step[2]>0 then positiveStep:=true: if step[1]=0 then upstep:=true: maxRateUp:=infinity: else maxRateUp:=max(maxRateUp,step[2]/step[1]): fi: elif step[2]<0 then negativeStep:=true: if step[1]=0 then downstep:=true: maxRateDown:=-infinity: else maxRateDown:=min(maxRateDown,step[2]/step[1]): fi: else zeroSteps:=zeroSteps union {step}: fi: od: if upstep and downstep then print(`There are an infinite number of ways to have excursions of length n since you included step(s) directly up and down.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(FAIL): elif not (negativeStep and positiveStep) then if nops(zeroSteps)=0 then print(`The problem is trivial. There is no walk back to the x-axis.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(FAIL): elif nops(zeroSteps)=1 then print(cat(`The problem is trivial. Walks returning to the x-axis consist of only repeated use of the one step `, zeroSteps[1])): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(FAIL): else print(`The only relevant steps are:`): print(zeroSteps): print(`The problem is equivalent to summing to n in different combinations using parts of size:`): print(seq(st[1],st in zeroSteps)): print(``): print(`The generating function (all walks have area 0 under the curve) is given by`): print(1/(1-add(zs[1],zs in zeroSteps))): print(`And in Maple input format:`): lprint(1/(1-add(zs[1],zs in zeroSteps))): return(FAIL): fi: else gu:=EqualSemiBoundedScoringPathsAreaEqsVars(Steps,0,x,z,f,g)[1]: fi: print(`Let f(x,z) be its (ordinary) generating function:`): print(f(x,z)=Sum(Sum(A(n,a)*x^n*z^a,n=0..infinity),a=0..infinity)): print(``): print(`Then f(x,z) satisfies`): print(``): print(f(x,z)=subs(f[0,0]=f,subs(gu,f[0,0](x,z)))): print(``): print(`The rest of the system satisfies`): for eq in gu minus {f[0,0](x,z)=subs(gu,f[0,0](x,z))} do print(subs(f[0,0]=f,eq)): od: print(``): print(`and in Maple input format`): for eq in gu do lprint(subs(f[0,0]=f,eq)): od: print(``): print(cat(`For the sake of the OEIS, here are the first `, K+1,` terms (starting at n=0).`)): # lprint(CodeTools[Usage](EqualSemiBoundedScoringPathsAreaCoefficients(Steps,0,z,K))): #The following is typically faster (better at handling larger step sizes). if maxRateUp=infinity then #maxRateDown<>-infinity lprint([seq(add(SpecificEqualSemiBoundedScoringPathsAreaNumber(Steps,0,n1,0,a1/2)*z^(a1/2),a1=0..n1^2*(-maxRateDown)),n1=0..K)]): elif maxRateDown=infinity then #maxRateUp<>infinity lprint([seq(add(SpecificEqualSemiBoundedScoringPathsAreaNumber(Steps,0,n1,0,a1/2)*z^(a1/2),a1=0..n1^2*maxRateUp),n1=0..K)]): else lprint([seq(add(SpecificEqualSemiBoundedScoringPathsAreaNumber(Steps,0,n1,0,a1/2)*z^(a1/2),a1=0..n1^2*maxRateUp*(-maxRateDown)/(maxRateUp-maxRateDown)),n1=0..K)]): fi: print(``): print(`----------------------------`): print(cat(`This ends this paper that took `, time()-t0, ` seconds to generate.`)): print(`----------------------------------------------------------------------------------------------------------------`): end: ############### with(combinat): ########################################################################################################################################### #BookEqualSemiBoundedArea(Steps,K): inputs a set of steps, Steps, and a positive integer K. #Outputs a book about the generating functions of walks from the origin back to (n,0) for some n that never go below the x-axis. #Includes information about the area under the curve of each walk encoded in z^a. #c*t^n*z^a indicates there are c paths of length n with area a under the walk. #Iterates over all subsets of Steps. #Try: #BookEqualSemiBoundedArea({[1,1],[1,-1],[1,0],[2,2],[2,-2],[3,3],[3,-1]},40,true); BookEqualSemiBoundedArea:=proc(Steps,K) local t0,nonTrivialCount,i,sectionCount,steps,result: t0:=time(): print(`Generating Functions of Area-Counting Excursions Drawn From`): print(Steps): print(``): print(`By Bryan Ek’s Maple Package ScoringPathsStats`): print(``): print(`------------------------------------------------------------------------------------------------------------------------------------------------------------------`): print(``): print(`Chapter 1: Introduction`): print(`This book includes results for all excursions built from subsets of size >=2 of the step set:`): print(Steps): print(``): print(`Results include finding relations for the generating function (g.f.) of original interest plus other building blocks.`): print(cat(`and the first `,K+1,` terms of each sequence (starting at n=0).`)): print(`-------------------------------------------------------------------------------------------------------------------------------`): print(``): nonTrivialCount:=0: for i from 2 to nops(Steps) do print(cat(`Chapter `,i,`: Walks built from `,i,` steps.`)): print(`----------------------------------------------------------------------------------------------------------------`): sectionCount:=0: for steps in choose(Steps,i) do sectionCount:=sectionCount+1: print(cat(`Section `,i,`.`,sectionCount)): result:=PaperEqualSemiBoundedArea(steps,K): if result<>FAIL then nonTrivialCount:=nonTrivialCount+1: fi: print(``): od: print(`-------------------------------------------------------------------------------------------------------------------------------`): print(``): od: print(cat(`This ends this book with `,nops(Steps),` Chapters and `,2^(nops(Steps))-nops(Steps)-1,` sections, `,nonTrivialCount,` of which are nontrivial, that took `,time()-t0, ` seconds to generate.`)): end: ########################################################################################################################################### #PaperEqualSemiBoundedPairArea(u,d,K): inputs positive integers u and d that are relatively prime, and a positive integer K, outputs an article about the #generating function of walks from the origin back to [(u+d)*n,0] for some n that never go below the x-axis. #Includes information about the area under the curve of each walk encoded in z^a. #c*t^n*z^a indicates there are c paths of length n with area a under the walk. #It also outputs the first K terms, for the sake of the OEIS. #Try: #PaperEqualSemiBoundedPairArea(2,3,40); PaperEqualSemiBoundedPairArea:=proc(u,d,K) local t0,gu,eq: if gcd(u,d)<>1 then print(`u and d should be coprime.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(): elif u<=0 or d<=0 then print(`u and d should both be positive.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(): fi: t0:=time(): print(cat(`On the Generating Functions of Area-Counting Enumerating Sequences for Generalized Dyck Paths with steps [1,`,-d,`] and [1,`,u,`].`)): print(``): print(`By Bryan Ek's Maple Package ScoringPathsStats`): print(``): print(`Theorem:`): print(cat(`Let A(n,a) be the number of ways of walking from (0,0) to `, ((u+d)*n,0), `using the steps `, {[1,u],[1,-d]}, `, never going below the x-axis, and having area a under the curve.`)): print(``): print(`Let f(x,z) be its (ordinary) generating function`): print(f(x,z)=Sum(Sum(A(n,a)*x^n*z^a,n=0..infinity),a=0..infinity)): print(``): gu:=EqualSemiBoundedScoringPathsAreaEqsVars({[1,u],[1,-d]},0,x,z,f,g)[1]: print(`Then f(x,z) satisfies`): print(``): print(f(x,z)=subs(f[0,0]=f,subs(gu,f[0,0](x,z)))): print(``): print(`The rest of the system satisfies`): for eq in gu minus {f[0,0](x,z)=subs(gu,f[0,0](x,z))} do print(subs(f[0,0]=f,eq)): od: print(``): print(`and in Maple input format`): for eq in gu do lprint(subs(f[0,0]=f,eq)): od: print(``): print(cat(`For the sake of the OEIS, here are the first `, K+1,` nonzero terms (starting at n=0).`)): # lprint(CodeTools[Usage](EqualSemiBoundedScoringPathsAreaCoefficients({[1,u],[1,-d]},0,z,K*(u+d)))): #The following is typically faster (better at handling larger step sizes). lprint([seq(add(SpecificEqualSemiBoundedScoringPathsAreaNumber({[1,u],[1,-d]},0,n1*(u+d),0,a1/2)*z^(a1/2),a1=0..n1^2*(u+d)*u*d),n1=0..K)]): print(``): print(`----------------------------`): print(cat(`This ends this paper that took `, time()-t0, ` seconds to generate.`)): print(`----------------------------------------------------------------------------------------------------------------`): end: ########################################################################################################################################### #PaperUnBoundedArea(Steps,K): inputs a set of steps, Steps, and a positive integer K, outputs an article about the #generating function of walks from the origin back to [n,0] for some n. #Includes information about the area under the curve of each walk encoded in z^a. #c*t^n*z^a indicates there are c paths of length n with area a under the walk. #It also outputs the first K terms, for the sake of the OEIS. #Try: #PaperUnBoundedArea({[1,1],[1,-1],[1,0]},40); PaperUnBoundedArea:=proc(Steps,K) local t0,positiveStep,zeroSteps,negativeStep,upstep,downstep,maxRateUp,maxRateDown,step,gu,eq: t0:=time(): print(cat(`On the Generating Functions of Area-Counting Enumerating Sequences for Unbounded Paths with set of steps `, Steps,`.`)): print(``): print(`By Bryan Ek's Maple Package ScoringPathsStats`): print(``): print(`Theorem:`): print(cat(`Let A(n) be the number of ways of walking from (0,0) to (n,0) using the steps `, Steps)): print(``): positiveStep:=false: # zeroStep:=false: zeroSteps:={}: negativeStep:=false: upstep:=false: downstep:=false: maxRateUp:=0: maxRateDown:=0: for step in (convert(Steps,set) minus {[0,0]}) while not (upstep and downstep) do #while not (positiveStep and negativeStep and zeroStep) do #This doesn’t actually save time since we would need all of the zero steps anyway. if step[2]>0 then positiveStep:=true: if step[1]=0 then upstep:=true: maxRateUp:=infinity: else maxRateUp:=max(maxRateUp,step[2]/step[1]): fi: elif step[2]<0 then negativeStep:=true: if step[1]=0 then downstep:=true: maxRateDown:=-infinity: else maxRateDown:=min(maxRateDown,step[2]/step[1]): fi: else zeroSteps:=zeroSteps union {step}: fi: od: if upstep and downstep then print(`There are an infinite number of ways to have bridges of length n since you included step(s) directly up and down.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(): elif not (negativeStep and positiveStep) then if nops(zeroSteps)=0 then print(`The problem is trivial. There is no walk back to the x-axis.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(): elif nops(zeroSteps)=1 then print(cat(`The problem is trivial. Walks returning to the x-axis consist of only repeated use of the one step `, zeroSteps[1])): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(FAIL): else print(`The only relevant steps are:`): print(zeroSteps): print(`The problem is equivalent to summing to n in different combinations using parts of size:`): print(seq(st[1],st in zeroSteps)): print(``): print(`The generating function (all walks have area 0 under the curve) is given by`): print(1/(1-add(zs[1],zs in zeroSteps))): print(`And in Maple input format:`): lprint(1/(1-add(zs[1],zs in zeroSteps))): return(FAIL): fi: else gu:=EqualUnBoundedScoringPathsAreaEqsVars(Steps,x,z,B,h,f,g)[1]: fi: print(`Let B(x,z) be its (ordinary) generating function:`): print(B(x,z)=Sum(Sum(A(n,a)*x^n*z^a,n=0..infinity),a=0..infinity)): print(``): print(`Then B(x,z) satisfies`): print(``): print(B(x,z)=subs(gu,B(x,z))): print(``): print(`The rest of the system satisfies`): for eq in gu minus {B(x,z)=subs(gu,B(x,z))} do print(eq): od: print(``): print(`and in Maple input format`): for eq in gu do lprint(eq): od: print(``): print(cat(`For the sake of the OEIS, here are the first `, K+1,` terms (starting at n=0).`)): # lprint(CodeTools[Usage](EqualUnBoundedScoringPathsAreaCoefficients(Steps,z,K))): #The following is typically faster (better at handling larger step sizes). if maxRateUp=infinity then #maxRateDown<>-infinity lprint([seq(SpecificUnBoundedScoringPathsAreaNumber(Steps,n1,0,0)+add(SpecificUnBoundedScoringPathsAreaNumber(Steps,n1,0,a1/2)*(z^(a1/2)+z^(-a1/2)),a1=1..n1^2*(-maxRateDown)),n1=0..K)]): elif maxRateDown=infinity then #maxRateUp<>infinity lprint([seq(SpecificUnBoundedScoringPathsAreaNumber(Steps,n1,0,0)+add(SpecificUnBoundedScoringPathsAreaNumber(Steps,n1,0,a1/2)*(z^(a1/2)+z^(-a1/2)),a1=1..n1^2*maxRateUp),n1=0..K)]): else lprint([seq(SpecificUnBoundedScoringPathsAreaNumber(Steps,n1,0,0)+add(SpecificUnBoundedScoringPathsAreaNumber(Steps,n1,0,a1/2)*(z^(a1/2)+z^(-a1/2)),a1=1..n1^2*maxRateUp*(-maxRateDown)/(maxRateUp-maxRateDown)),n1=0..K)]): fi: print(``): print(`----------------------------`): print(cat(`This ends this paper that took `, time()-t0, ` seconds to generate.`)): print(`----------------------------------------------------------------------------------------------------------------`): end: ########################################################################################################################################### #PaperUnBoundedPairArea(u,d,K): inputs positive integers u and d that are relatively prime, and a positive integer K, outputs an article about the #generating function of walks from the origin back to [(u+d)*n,0] for some n. #Includes information about the area under the curve of each walk encoded in z^a. #c*t^n*z^a indicates there are c paths of length n with area a under the walk. #It also outputs the first K terms, for the sake of the OEIS. #Try: #PaperUnBoundedPairArea(2,3,40); PaperUnBoundedPairArea:=proc(u,d,K) local t0,gu,eq: if gcd(u,d)<>1 then print(`u and d should be coprime.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(): elif u<=0 or d<=0 then print(`u and d should both be positive.`): print(`----------------------------------------------------------------------------------------------------------------`): RETURN(): fi: t0:=time(): print(cat(`On the Generating Functions of Area-Counting Enumerating Sequences for Unbounded Paths with steps [1,`,-d,`] and [1,`,u,`].`)): print(``): print(`By Bryan Ek's Maple Package ScoringPathsStats`): print(``): print(`Theorem:`): print(cat(`Let A(n,a) be the number of ways of walking from (0,0) to `, ((u+d)*n,0), `using the steps `, {[1,u],[1,-d]}, `, and having area a under the curve.`)): print(cat(`Since we care about area, we know longer have the simple solution: A(n)=`,(u+d),`*n choose `,u,`*n.`)): print(``): print(`Let B(x,z) be its (ordinary) generating function:`): print(B(x,z)=Sum(Sum(A(n,a)*x^n*z^a,n=0..infinity),a=0..infinity)): print(``): gu:=EqualUnBoundedScoringPathsAreaEqsVars({[1,u],[1,-d]},t,z,B,h,f,g)[1]: print(`Then B(x,z) satisfies`): print(``): print(B(x,z)=subs(gu,B(x,z))): print(``): print(`The rest of the system satisfies`): for eq in gu minus {B(x,z)=subs(gu,B(x,z))} do print(eq): od: print(``): print(`and in Maple input format`): for eq in gu do lprint(eq): od: print(``): print(cat(`For the sake of the OEIS, here are the first `, K+1,` nonzero terms (starting at n=0).`)): # lprint(CodeTools[Usage](UnBoundedScoringPathsAreaCoefficients([1,u],[1,-d],z,K))): #The following is typically faster (better at handling larger step sizes). lprint([seq(add(SpecificUnBoundedScoringPathsAreaNumber({[1,u],[1,-d]},n1,0,a1/2)*z^(a1/2),a1=-n1^2*(u+d)*u*d..n1^2*(u+d)*u*d),n1=0..K)]): print(`----------------------------`): print(cat(`This ends this paper that took `, time()-t0, ` seconds to generate.`)): print(`----------------------------------------------------------------------------------------------------------------`): end: