#Homework by Mike Murr
#OK to post
#HW6

currentdir();
currentdir("/Users/michaelmurr/Documents/Mike/Experimental Math");
read `C6.txt`;
Help6();

#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 intermediate 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); 
end if;
 
if pt = [0, 0] then 
  RETURN(1); 
end if; 

W := 0; 

for i to nops(A) do 
  W1 := GNuWalks2D(A, pt - A[i]); 
  W := W + W1; 
end do; 
W; 

end proc;
NuWalks2D([[1, 0], [0, 1]], [2, 2]);
seq(NuWalks2D([[1, 0], [0, 1]], [i, i]), i = 1 .. 20);
#i) A000984, central binomial coefficients, 2*n choose n
seq(GNuWalks2D([[1, 0], [0, 1]], [i, i]), i = 1 .. 20);
#ii) A000108, Catalan numbers, (2*n choose n)/(n+1)
seq(NuWalks2D([[1, 0], [0, 1], [2, 0], [0, 2]], [i, i]), i = 1 .. 20);
#iii) A036692
seq(GNuWalks2D([[1, 0], [0, 1], [2, 0], [0, 2]], [i, i]), i = 1 .. 20);
#iv) A122951
seq(NuWalks2D([[1, 0], [0, 1], [2, 0], [0, 2], [0, 3], [3, 0]], [i, i]), i = 1 .. 20);
#v) A122680
seq(GNuWalks2D([[1, 0], [0, 1], [2, 0], [0, 2], [0, 3], [3, 0]], [i, i]), i = 1 .. 20);
#vi) A175883
seq(NuWalks2D([[1, 0], [0, 1], [1, 1]], [i, i]), i = 1 .. 20);
#vii) A001850, Central Delannoy numbers
seq(GNuWalks2D([[1, 0], [0, 1], [1, 1]], [i, i]), i = 1 .. 20);
#viii) A006318
FootBall();
seq(NuWalks2D(FootBall(), [i, i]), i = 1 .. 20);
#ix) not in OEIS: 0,2,2,6,24,62,206,712,2076,7284,22684,…
seq(GNuWalks2D(FootBall(), [i, i]), i = 1 .. 20);
#x) not in OEIS: 0,1,1,2,7,16,45,144,368,1189,3379,10331,31444,…

#3 i) Thanks to a few words in the OEIS, regarding the answers to 2 i and 2 ii, the probability is
#     1/(n+1)

#4 
seq(evalf(GNuWalks2D(FootBall(), [i, i])/NuWalks2D(FootBall(), [i, i])), i = 2 .. 40);
seq(evalf(1/i^0.5), i = 2 .. 40);
seq(evalf(1/i^0.9), i = 2 .. 40);
seq(evalf(1/i^0.88), i = 2 .. 40);
seq(evalf(1/i^0.82), i = 2 .. 40);
seq(evalf(1/i^0.85), i = 2 .. 60);
seq(evalf(GNuWalks2D(FootBall(), [i, i])/NuWalks2D(FootBall(), [i, i])), i = 2 .. 60);

#4 Exploring up to n=60 (a 60-60 tie), the probability is close to 1/(n^0.85)
#
#

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

if pt[1] < 0 or pt[2] < 0 or pt[3] < 0 then 
  RETURN(0); 
end if; 

if pt = [0, 0, 0] then 
  RETURN(1); 
end if;
 
W := 0;
 
for i to nops(A) do 
  W1 := NuWalks3D(A, pt - A[i]); 
  W := W + W1; 
end do; 

W; 
end proc;

NuWalks3D([[1, 0, 0], [0, 1, 0], [0, 0, 1]], [1, 1, 1]);

#GNuWalks3D(A,pt): Inputs a list A of `atomic' steps A
#in the form [a,b,c] (with a,b,c non-neg. and a+b+c>0) and
#a final location (final score in game, e.g. [31,9,15]).
#OUTPUTS the NUMBER of all GOOD (subdiagonal) WALKS from [0,0,0]
#to pt, described by giving the intermediate location
#[[0,0,1],[0,0,2],[0,1,2],[1,1,2],[1,1,3]]

GNuWalks3D := proc(A, pt) local i, W, W1, w; 
option remember; 

if pt[1] < 0 or pt[2] < 0 or pt[3] < 0 or pt[1] < pt[2] or pt[2] < pt[3] or pt[1] < pt[3] then 
  RETURN(0); 
end if; 

if pt = [0, 0, 0] then 
  RETURN(1); 
end if; 

W := 0;
 
for i to nops(A) do 
  W1 := GNuWalks3D(A, pt - A[i]); 
  W := W + W1; 
end do; 

W; 
end proc;


GNuWalks3D([[1, 0, 0], [0, 1, 0], [0, 0, 1]], [1, 1, 1]);

seq(NuWalks3D([[1, 0, 0], [0, 1, 0], [0, 0, 1]], [i, i, i]), i = 1 .. 10);

#i) A006480 De Bruijn’s S(3,n) (3n)!/(n!n!n!)

seq(GNuWalks3D([[1, 0, 0], [0, 1, 0], [0, 0, 1]], [i, i, i]), i = 1 .. 10);

#ii) A005789 3-dimensional Catalan numbers 2*(3n)!/((n!)(n+1)!(n+2)!)

#NuWalks4D(A,pt): Inputs a list A of `atomic' steps A
#in the form [a,b,c,d] (with a,b,c,d non-neg. and a+b+c+d>0) and
#a final location (final score in game, e.g. [31,9,15,4]).
#OUTPUTS the NUMBER of all WALKS from [0,0,0,0]
#to pt, described by giving the intermediate location
#[[0,0,0,1],[0,0,0,2],[0,0,1,2], [0,1,1,2],[1,1,1,2],[2,1,1,2]]


NuWalks4D := proc(A, pt) local i, W, W1, w; 
option remember;
 
if pt[1] < 0 or pt[2] < 0 or pt[3] < 0 or pt[4] < 0 then 
  RETURN(0); 
end if; 

if pt = [0, 0, 0, 0] then 
  RETURN(1); 
end if; 

W := 0; 

for i to nops(A) do 
  W1 := NuWalks4D(A, pt - A[i]); 
  W := W + W1; 
end do; 

W; 

end proc;

#GNuWalks4D(A,pt): Inputs a list A of `atomic' steps A
#in the form [a,b,c,d] (with a,b,c,d non-neg. and a+b+c+d>0) and
#a final location (final score in game, e.g. [31,9,15,4]).
#OUTPUTS the NUMBER of all GOOD (subdiagonal) WALKS from [0,0,0,0]
#to pt, described by giving the intermediate location
#[[0,0,0,1],[0,0,0,2],[0,0,1,2], [0,1,1,2],[1,1,1,2],[2,1,1,2]]

GNuWalks4D := proc(A, pt) local i, W, W1, w; 
option remember; 

if pt[1] < 0 or pt[2] < 0 or pt[3] < 0 or pt[4] < 0 or pt[1] < pt[2] or pt[2] < pt[3] or pt[3] < pt[4] then 
  RETURN(0); 
end if; 

if pt = [0, 0, 0, 0] then 
  RETURN(1); 
end if; 

W := 0; 

for i to nops(A) do 
  W1 := GNuWalks4D(A, pt - A[i]); 
  W := W + W1; 
end do;
 
W; 

end proc;

seq(NuWalks4D([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]], [i, i, i, i]), i = 1 .. 10);


#iii) A008977 (4n)!/(n!n!n!n!)

seq(GNuWalks4D([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]], [i, i, i, i]), i = 1 .. 10);

#iv) A005790 4-dimensional Catalan numbers 12*(4n)!/(n!(n+1)!(n+2)!(n+3)!)