#OK to post homework

#Zidong Zhang, 14/2/2021, Assignment 6




#GNuWalks2D(A,pt), inputs a list of atomic steps A (in 2 dimensions) and  output the #number of subdiagonal steps using A and ending at pt

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):  that inputs a list of atomic steps A (in 2 dimensions) and output a #(uniformally) at random such good walk.

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(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:=GRandWalk2D(A,pt-A[r]):

[op(W1),pt]:

end:


#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


#seq(GNuWalks2D([[1,0],[0,1]],[i,i]),i=1..10)

#1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796

#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

#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

#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

#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

#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

#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

#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
##########This one is not in OEIS!!##################

#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
##########This one is not in OEIS!!##################


# I have tested for n from 1 to 20, and the answer is 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 my conjecture is the probablity that in a soccer game that ended with a tie #[n,n], the visiting team was Never (striclty) leading is 1/(1+n).

# I haven't thought out a very precicely proof of this formula. 




#NuWalkskD(A,pt) : a generalization of NuWalks2D(A,pt).


NuWalkskD := proc(A,pt) local i,W,W1,w:

if ormap(`<` , pt , 0) then
	return(0):
fi:

if ormap(`=` , 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 := proc(A,pt) local i,W,W1,w,j:
for j from 1 to nops(pt)-1 do

	if (pt[j]<0 or pt[j+1]<0 or pt[j]<pt[j+1] )then
		return(0):
	fi:
od:

if ormap(`=` , 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:




#seq(NuWalkskD([[1,0,0],[0,1,0],[0,0,1]],[i,i,i]),i=1..6)

##10 is too big and run so long time. So I run for i =1..6

#3, 33, 543, 10497, 220503, 4870401
#OEIS A209245



#seq(GNuWalkskD([[1,0,0],[0,1,0],[0,0,1]],[i,i,i]),i=1..8)
#1, 3, 18, 162, 1851, 24661, 365613, 5863881
#OEIS A065058


#seq(NuWalkskD([[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]],[i,i,i,i]),i=1..4)
#4, 196, 22096, 3323092
#OEIS A209288


#seq(GNuWalkskD([[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]],[i,i,i,i]),i=1..5)
#1, 4, 59, 1971, 103685
#this is not a OEIS number.