#OK to post homework
#Kent Mei, 9/13/2020, Assignment 2

#---------------------------
#Part 1
#Let G(a,b,c) = (a+b+c)!/(a!*b!*c!). We want to prove that G(a,b,c) = F(a,b,c) where F is the number of walks from [0,0,0] to [a,b,c] in the 3D "Manhattan lattice".
#We proceed by induction. First we check initial conditions.
#G(0,b,c) = (0+b+c)!/(0!*b!*c!) = (b+c)! / (b!*c!) = F(0,b,c) since this is the same as the 2D case for number of walks.
#G(a,0,c) = (a+0+c)!/(a!*0!*c!) = (a+c)! / (a!*c!) = F(a,0,c).
#G(a,b,0) = (a+b+0)!/(a!*b!*0!) = (a+b)! / (a!*b!) = F(a,b,0).
#All the initial conditions have been verified, now we do the inductive step.
#We know that F(a,b,c) = F(a-1,b,c) + F(a,b-1,c) + F(a,b,c-1).
#So, we need to prove that G(a,b,c) = G(a-1,b,c) + G(a,b-1,c) + G(a,b,c-1). Dividing both sides by G(a,b,c), we get:
#1 = (G(a-1,b,c) / G(a,b,c)) + (G(a,b-1,c) / G(a,b,c)) + (G(a,b,c-1) / G(a,b,c)).
#G(a-1,b,c) / G(a,b,c) = ((a+b+c-1)! / (a-1)!*b!*c!) / ((a+b+c)! / a!*b!*c!) = a!*b!*c!/ (a+b+c) * (a-1)!*b!*c! = a / (a+b+c)
#G(a,b-1,c) / G(a,b,c) = ((a+b+c-1)! / a!*(b-1)!*c!) / ((a+b+c)! / a!*b!*c!) = b / (a + b + c)
#G(a,b,c-1) / G(a,b,c) = ((a+b+c-1)! / a!*b!*(c-1)!) / ((a+b+c)! / a!*b!*c!) = c / (a + b + c)
#(G(a-1,b,c) / G(a,b,c)) + (G(a,b-1,c) / G(a,b,c)) + (G(a,b,c-1) / G(a,b,c)) = (a / (a + b + c)) + (b / (a + b + c)) + (c / (a + b + c)) = (a + b + c) / (a + b + c) = 1 as desired.


#---------------------------
#Part 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 both can be thought of as arrangements of the same elements. For the walks, each walk can be thought of as a sequence of steps where you have to take a[i] steps in the ith direction for i = 1..k. Similarly for the words, each word can be thought of as a sequence of letters where there has to be a[i] amount of the ith letter for i = 1..k. Essentially, each direction for a walk can be thought of like a specific letter in the alphabet, and the amount of steps in a certain direction is the amount of times the letter appears in the word.

#---------------------------
#Part 3

#The explicit formula for G(a1,...,ak) = the number of words in the "alphabet" {1,2,...,k} with the letter i showing up a[i] times (i = 1..k) is:
#G(a1,...,ak) = (a1+a2+...+ak)! / a1!*a2!*...*ak!

#We proceed to prove this formula by induction
#We first verify the intial condition. Let ai = 0 for some i from 1..k. G(a1,...,ai,...,ak) = F(a1,...,ai,...,ak) for all i from 1..k is something we previously established as those are lower dimensional cases.
#Now we see if G follows the same reccurence relation as F
#F(a1,...,ak) = sum(F(a1,...,ai - 1,...,ak)) for i = 1..k.
#HTP: G(a1,...,ak) = sum(G(a1,...,ai - 1,...,ak)) for i = 1..k. 
#Divide both sides by G(a1,...,ak): 1 = sum(G(a1,...,ai - 1,...,ak)/G(a1,...,ak)) for i = 1..k.
#G(a1,...,ai - 1,...,ak)/G(a1,...,ak) = ((a1+...+ak-1)! / a1!*...*(ai-1)!*....*ak!) / ((a1+...+ak)! / a1!*...*ak!) = a1!*...*ak! / ((a1+...+ak) * (a1!*...*(ai-1)!*....*ak!)) = ai / (a1+...+ak).
#sum(ai / (a1+...+ak)) for i = 1..k = (a1+...+ak) / (a1+...+ak) = 1 as desired.

#---------------------------
#Part 4

RestrictedWalks:=proc(m,n,S) local W1,W2,w1,w2:
option remember:

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

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


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

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

{seq([op(w1),E],w1 in W1), seq([op(w2),N],w2 in W2)  }:

end:

RestrictedWalks(2,2,{[1,1]});
#Output is {[E, E, N, N], [N, N, E, E]}.

#---------------------------
#Part 5

RestrictedNuWalks:=proc(m,n,S) local W1,W2:
option remember:

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

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


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

W1:=RestrictedNuWalks(m-1,n,S):
W2:=RestrictedNuWalks(m,n-1,S):

W1+W2:
end:

RestrictedNuWalks(2,2,{[1,1]});
#Output is 2.

RestrictedNuWalks(50,50,{seq([i,i],i=1..50)});
#The answer is 0.