#OK to post homework
#Blair Seidler, 2021-02-14, Assignment 6

with(combinat):

Help:=proc():
print(`GNuWalks2D(A,pt)`,`GRandWalk2D(A,pt)`): 
print(`NuWalkskD(A,pt)`,`GNuWalkskD(A,pt)`):
end:

# 1.

#GNuWalks2D(A,pt): Inputs a list A of `atomic' steps A
#in the form [a,b] (with a,b non-neg. and a+b>0) and
#a final location (final score in game, e.g. [31,9]).
#OUTPUTS the NUMBER of all GOOD (subdiagonal) WALKS from [0,0] to
#to pt, described by giving the intermedite location
#[[0,0],[2,0],[10,0],[10,2],[10,10]]
GNuWalks2D:=proc(A,pt) local i,W,W1,w:
option remember:

if pt[1]<0 or pt[2]<0 or pt[1]<pt[2] then
 RETURN(0):
fi:

if pt=[0,0] then
 RETURN(1):
fi:

W:=0:

for i from 1 to nops(A) do
 W1:=GNuWalks2D(A,pt-A[i]):
 W:=W + W1:
od:

W:
end:

#GRandWalk2D(A,pt): inputs a list of atomic steps A and 
# a final destination pt, outputs UNIFORMLY at random
#a GOOD (subdiagonal) walk from [0,0] to pt using the steps in A
GRandWalk2D:=proc(A,pt) local i,W1,Die1,r:
if pt[1]<0 or pt[2]<0 or pt[1]<pt[2] then
 RETURN(FAIL):
fi:

if pt=[0,0] then
   RETURN([[0,0]]):
fi:

Die1:=[seq(GNuWalks2D(A,pt-A[i]),i=1..nops(A))]:

#Let r be the index in A of the last step in our uniform-random walk
#that ended at pt 
r:=LD(Die1):

W1:=GRandWalk2D(A,pt-A[r]):

[op(W1),pt]:

end:

# 2.

#(i) seq(NuWalks2D([[1,0],[0,1]],[i,i]),i=1..20):
#2, 6, 20, 70, 252, 924, 3432, 12870, 48620, 184756, 705432, 2704156, 10400600,
#40116600, 155117520, 601080390, 2333606220, 9075135300, 35345263800, 137846528820

#This is A000984 - Central Binomial Coefficients

#(ii) seq(GNuWalks2D([[1,0],[0,1]],[i,i]),i=1..20):
#1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845,
#35357670, 129644790, 477638700, 1767263190, 6564120420

#This is A000108 - Catalan Numbers

#(iii)seq(NuWalks2D([[1,0],[0,1],[2,0],[0,2]],[i,i]),i=1..20):
#2, 14, 84, 556, 3736, 25612, 177688, 1244398, 8777612, 62271384, 443847648, 3175924636,
#22799963576, 164142004184, 1184574592592, 8567000931404, 62073936511496, 450518481039956,
#3274628801768744, 23833760489660324

#This is A036355

#(iv) seq(GNuWalks2D([[1,0],[0,1],[2,0],[0,2]],[i,i]),i=1..20):
#1, 5, 22, 117, 654, 3843, 23323, 145172, 921508, 5942737, 38825546, 256431172, 1709356836,
#11485249995, 77703736926, 528893901963, 3619228605738, 24884558358426, 171828674445330, 
#1191050708958096

#This is A122951, which includes the link:
#Arvind Ayyer and Doron Zeilberger, The Number of [Old-Time] Basketball games with Final Score
#n:n where the Home Team was never losing but also never ahead by more than w Points

#(v) seq(NuWalks2D([[1,0],[0,1],[2,0],[0,2],[3,0],[0,3]],[i,i]),i=1..20):
#2, 14, 106, 784, 6040, 47332, 375196, 3001966, 24190148, 196034522, 1596030740, 13044459766,
#106961525744, 879512777006, 7249483605580, 59881171431050, 495545064567260, 4107666916668414,
#34099685718629264, 283454909832384416

#This is A122680 - Multiple Dr. Z references in the OEIS for this one!

#(vi) seq(GNuWalks2D([[1,0],[0,1],[2,0],[0,2],[3,0],[0,3]],[i,i]),i=1..20):
#1, 5, 29, 170, 1093, 7346, 50957, 362476, 2629150, 19371533, 144585146, 1090886362,
#8306621114, 63752890716, 492671044866, 3830272606911, 29937476853483, 235104315621495,
#1854181694878573, 14679397763545597

#This is A175883

#(vii) seq(NuWalks2D([[1,0],[0,1],[1,1]],[i,i]),i=1..20):
#3, 13, 63, 321, 1683, 8989, 48639, 265729, 1462563, 8097453, 45046719, 251595969, 1409933619,
#7923848253, 44642381823, 252055236609, 1425834724419, 8079317057869, 45849429914943,
#260543813797441

#This is A001850 - Central Delannoy numbers

#(viii) seq(GNuWalks2D([[1,0],[0,1],[1,1]],[i,i]),i=1..20):
#2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, 1037718, 5293446, 27297738, 142078746, 745387038,
#3937603038, 20927156706, 111818026018, 600318853926, 3236724317174, 17518619320890

#This is A006318 - Large Schroeder numbers

#(ix) seq(NuWalks2D(FootBall(),[i,i]),i=1..20):
#0, 2, 2, 6, 24, 62, 206, 712, 2076, 7284, 22684, 75222, 246172, 805462, 2658588, 8763448,
#28932292, 95870878, 317416080, 1053931874

#Not in OEIS

#(x) seq(GNuWalks2D(FootBall(),[i,i]),i=1..20):
#0, 1, 1, 2, 7, 16, 45, 144, 368, 1189, 3379, 10331, 31444, 95903, 296812, 921138, 2870493,
#9014628, 28346277, 89641760

#Also not in OEIS

#A more traditional? football list of atomic steps
Football:=proc():
[[0,1],[0,2],[0,3],[0,6],[1,0],[2,0],[3,0],[6,0]]:
end:

#I reran the last two queries with this version of Football() and also got
#sequences not in the OEIS

# 3.

#Using NuWalks2D and GNewWalks2D (that you wrote), conjecture an explicit expression for
#the probability that in a soccer game that ended with a tie [n,n], the visiting team was 
#Never (strictly) leading.

#seq(GNuWalks2D([[1, 0], [0, 1]], [i, i])/NuWalks2D([[1, 0], [0, 1]], [i, i]), i = 1 .. 20)
#produces the output
#1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 1/8, 1/9, 1/10, 1/11, 1/12, 1/13, 1/14, 1/15, 1/16, 1/17, 1/18,
#1/19, 1/20, 1/21
#so the exact value seems to be 1/(n+1)

#This makes sense because the number of "good" walks is C(n)=(2n)!/((n)!(n+1)!) and the
#total number of walks is binomial(2n,n)=(2n)!/((n)!(n)!).
#The probability of a walk being "good" is C(n)/binomial(2n,n)=1/(n+1)

# 4.
#Estimate the analogous probability for an American football game. Try to conjecture a form
#for the asymptotics of that probability. Is it like 1/n^alpha for some alpha?

#If we consider the probability to be in the form 1/a, the denominator is increasing by
#about 0.5602417567 when we go far enough down the sequence. In the soccer case, the
#denominators are increasing by 1 always. I'm not sure what this number means.



# 5.

#Generalize to k-dimensional NuWalks2D(A,pt), GNuWalks2D(A,pt) to write procedures
#NuWalkskD(A,pt) and GNuWalkskD(A,pt) and ?????
#(let k=nops(pt), and assume that all the members of A are lists of length k)
#Assuming that the condition for a "Good" walk here is pt[i]<pt[i+1], i=1..k-1

#NuWalkskD(A,pt): Inputs a list A of `atomic' steps A
#in the form [a,b,...] (with a,b,... non-neg. and a+b>0) and
#a final location (final score in game, e.g. [31,9,...]).
#OUTPUTS the NUMBER of all WALKS from [0,0,...] to
#to pt, described by giving the intermedite location
NuWalkskD:=proc(A,pt) local k,i,W,W1,w:
option remember:
k:=nops(pt):
if not ({seq(evalb(pt[i]>=0),i=1..k)}={true}) then
 RETURN(0):
fi:

if add(op(pt))=0 then
 RETURN(1):
fi:

W:=0:

for i from 1 to nops(A) do
 W1:=NuWalkskD(A,pt-A[i]):
 W:=W + W1:
od:

W:
end:

#GNuWalkskD(A,pt): Inputs a list A of `atomic' steps A
#in the form [a,b,...] (with a,b,... non-neg. and a+b+...>0) and
#a final location (final score in game, e.g. [31,9,...]).
#OUTPUTS the NUMBER of all GOOD (subdiagonal) WALKS from [0,0,...] to
#to pt, described by giving the intermedite location
GNuWalkskD:=proc(A,pt) local k,i,W,W1,w:
option remember:
k:=nops(pt):
if not (({seq(evalb(pt[i]>=0),i=1..k)}={true}) and 
	({seq(evalb(pt[i]>=pt[i+1]),i=1..k-1)}={true})) then
 RETURN(0):
fi:

if add(op(pt))=0 then
 RETURN(1):
fi:

W:=0:

for i from 1 to nops(A) do
 W1:=GNuWalkskD(A,pt-A[i]):
 W:=W + W1:
od:

W:
end:

#(i) seq(NuWalkskD([[1,0,0],[0,1,0],[0,0,1]],[i,i,i]),i=1..10):
#6, 90, 1680, 34650, 756756, 17153136, 399072960, 9465511770, 227873431500, 5550996791340
#A006480 DeBruijn's S(3,n): (3n)!/(n!)^3

#(ii) seq(GNuWalkskD([[1,0,0],[0,1,0],[0,0,1]],[i,i,i]),i=1..10):
#1, 5, 42, 462, 6006, 87516, 1385670, 23371634, 414315330, 7646001090
#A005789 3-dimensional Catalan numbers

#(iii) seq(NuWalkskD([[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]],[i,i,i,i]),i=1..10):
#24, 2520, 369600, 63063000, 11732745024, 2308743493056, 472518347558400,
#99561092450391000, 21452752266265320000, 4705360871073570227520
#A008977 a(n)=(4n)!/(n!)^4

#(iv) seq(GNuWalkskD([[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]],[i,i,i,i]),i=1..10):
#1, 14, 462, 24024, 1662804, 140229804, 13672405890, 1489877926680, 177295473274920,
#22661585038594320
#A005790 4-dimensional Catalan numbers







#### Code included from C6.txt ####
Help6:=proc(): print(`LD(L) , Walks2D(A,pt) , NuWalks2D(A,pt), FootBall()`): 
print(`RandWalk2D(A,pt)`):
end:

#Walks2D(A,pt): Inputs a list A of `atomic' steps A
#in the form [a,b] (with a,b non-neg. and a+b>0) and
#a final location (final score in game, e.g. [31,9]).
#OUTPUTS the SET of all WALKS from [0,0] to
#to pt, described by giving the intermedite location
#[[0,0],[2,0],[10,0],[10,2],[10,10]]
Walks2D:=proc(A,pt) local i,W,W1,w:
option remember:

if pt[1]<0 or pt[2]<0 then
 RETURN({}):
fi:

if pt=[0,0] then
 RETURN({[[0,0]]}):
fi:

W:={}:

for i from 1 to nops(A) do
 W1:=Walks2D(A,pt-A[i]):
 W:=W union {seq([op(w),pt], w in W1)}:
od:

W:
end:

FootBall:=proc():
[[0,2],[0,3],[0,6],[0,7],[0,8],[2,0],[3,0],[6,0],[7,0],[8,0]]:
end:

#NuWalks2D(A,pt): Inputs a list A of `atomic' steps A
#in the form [a,b] (with a,b non-neg. and a+b>0) and
#a final location (final score in game, e.g. [31,9]).
#OUTPUTS the NUMBER of all WALKS from [0,0] to
#to pt, described by giving the intermedite location
#[[0,0],[2,0],[10,0],[10,2],[10,10]]
NuWalks2D:=proc(A,pt) local i,W,W1,w:
option remember:

if pt[1]<0 or pt[2]<0 then
 RETURN(0):
fi:

if pt=[0,0] then
 RETURN(1):
fi:

W:=0:

for i from 1 to nops(A) do
 W1:=NuWalks2D(A,pt-A[i]):
 W:=W + W1:
od:

W:
end:

#RandWalk2D(A,pt): inputs a list of atomic steps A and 
# a final destination pt, outputs UNIFORMLY at random
#a walk from [0,0] to pt using the steps in A
RandWalk2D:=proc(A,pt) local i,W1,Die1,r:
if pt[1]<0 or pt[2]<0 then
 RETURN(FAIL):
fi:

if pt=[0,0] then
   RETURN([[0,0]]):
fi:

Die1:=[seq(NuWalks2D(A,pt-A[i]),i=1..nops(A))]:

#Let r be the index in A of the last step in our uniform-random walk
#that ended at pt 
r:=LD(Die1):

W1:=RandWalk2D(A,pt-A[r]):

[op(W1),pt]:

end:

 ##start GOOD (subdiagonal walks)
#GWalks2D(A,pt): Inputs a list A of `atomic' steps A
#in the form [a,b] (with a,b non-neg. and a+b>0) and
#a final location (final score in game, e.g. [31,9]).
#OUTPUTS the SET of all GOOD (subdiagonal) WALKS from [0,0] to
#to pt, described by giving the intermedite location
#[[0,0],[2,0],[10,0],[10,2],[10,10]]
GWalks2D:=proc(A,pt) local i,W,W1,w:
option remember:

if (pt[1]<0 or pt[2]<0 or pt[1]<pt[2]) then
 RETURN({}):
fi:

if pt=[0,0] then
 RETURN({[[0,0]]}):
fi:

W:={}:

for i from 1 to nops(A) do
 W1:=GWalks2D(A,pt-A[i]):
 W:=W union {seq([op(w),pt], w in W1)}:
od:

W:
end:

FootBall:=proc():
[[0,2],[0,3],[0,6],[0,7],[0,8],[2,0],[3,0],[6,0],[7,0],[8,0]]:
end:

#### End of code included from C6.txt ####


##FROM C4.txt
#LD(L): Inputs a list of positive integers L (of n:=nops(L) members)
#outputs an integer i from 1 to n with the prob. of i being
#proportional to L[i]
#For example LD([1,2,3]) should output 1 with prob. 1/6
#output 2 with prob. 1/3
#output 3 with prob. 3/6=1/2
LD:=proc(L) local n,i,su,r:
n:=nops(L):
r:=rand(1..convert(L,`+`))():
su:=0:

for i from 1 to n do
 su:=su+L[i]:
  if r<=su then
    RETURN(i):
  fi:
od:
end:
#END FROM C4.txt