#OK to post homework
#Ariana Yousafzai, 9/20/2020, Assignment 2


#Question 1


Theorem: The number of walks from [0,0,0] to [a,b,c] in the 3D "Manhattan lattice" (where you each step is either [1,0,0],[0,1,0],[0,0,1], is given by the explicit formula
(a+b+c)!/(a!*b!*c!)


Proof: 


Let F(x, y, z) be a point in the “Manhattan lattice” such that F(x, y, z) = (x + y + z)!/(x!*y!*z!)


If x = 0 and y = 0, F(0, 0, z) = 1
If x=0 and z=0, F(0,y,0) = 1
If y=0 and z=0, F(x,0,0) = 1


We assume that 


F(x-1, y, z) = (x+y+z-1)!/((x-1)!y!z!)
F(x, y-1, z) = (x+y+z-1)!/(x!(y-1)!z!)
F(x, y, z-1) = (z+y+z-1)!/(x!y!(z-1)!)


F(x, y, z)= F(x-1, y, z)+F(x, y-1, z)+F(x, y, z-1)


=(x+y+z-1)!*( 1/((z-1)!y!z!)+1/(z!(y-1)!z!)+1/x!y!(z-1)!)
=(x+y+z-1)!/((x-1)!(y-1)!(z-1)!)(1/x+1/y+1/z)
=(x+y+z-1)!/((x-1)!(y-1)!(z-1)!)((x+y+z)/xyz)
=(x+y+z)!/(x!y!z!)


QED


#Question 2


The number of walks in the k-dimensional Manhattan lattice from [0,0...,0] to [a[1], ..., a[k]] is
the same as the number of words in the "alphabet" {1,2,...k} with the letter i showing up exactly a[i] times (i=1..k) because the directions that one walks when traveling the Manhattan lattice can be modeled as letters. 


When calculating the number of paths taken from point A to point B, or counting the number of paths taken using specific letters in the alphabet, the number of paths are being counted and therefore use the same procedure for each of the two scenarios. 




#Question 3


The formula is (a[1]+a[2]+...+a[k])!/(a[1]!*a[2]!*...*a[k]!) for the number of words in the “alphabet,” a, with letter i howing up exactly a[i] times (i=1..k). 


The number of possible words with an alphabet of length L with L[1] first letters, L[2] second letters, ... L[k] kth letters, is (L[1]+L[2]+...+L[k])!/L[1]!L[2]!...L[k]!). 


In question 2, we noted that the formula for calculating the number of walks in the k-dimensional Manhattan lattice from [0,0...,0] to [a[1], ..., a[k]] is the same as the number of words in the "alphabet" {1,2,...k} with the letter i showing up exactly a[i] times (i=1..k) because the directions that one walks when traveling the Manhattan lattice can be modeled as letters. 


Therefore, the formulas are the same and (a[1]+a[2]+...+a[k])!/(a[1]!*a[2]!*...*a[k]!) is the number of words in the “alphabet,” a, with letter i howing up exactly a[i] times (i=1..k). 


#Question 4


RestrictedWalks:=proc(m,n, S) local X1,X2,x1,x2:


option remember:


if m<0 or n<0 then
RETURN({}):
fi:


if m=0 and n=0 then
RETURN({[]}):
fi:


if S=[m,n] then
RETURN({});
fi:


W1:=RestrictedWalks(m-1,n,V):
W2:=RestrictedWalks(m,n-1,V):


{seq([op(x1),E],x1 in X1), seq([op(x2),N],x2 in X2)}:


end: 








#Question 5


RestrictedNuWalks:=proc(m,n,S) local X1,X2,x1,x2:


option remember:


if m<0 or n<0 then
RETURN(0):
fi:


if m=0 and n=0 then
RETURN(1):
fi:


if member([m,n],S) then
RETURN(0);
fi:


X1:=RestrictedNuWalks(m-1,n,S):
X2:=RestrictedNuWalks(m,n-1,S):


X1+X2:
end: