#OK to post homework
#William Wang, 9/7/2020, Assignment 2

#1.
#Give a full human proof of the fact that the number of walks from [0,0,0] to [a,b,c] in the 3D "Manhattan lattice" (where each step is either [1,0,0],[0,1,0], or [0,0,1]) is given by the explicit formula (a+b+c)!/(a!*b!*c!)

#Theorem: F(a,b,c) = (a+b+c)!/(a!b!c!)
#Proof: Induction on a,b,c

#if b = 0, c = 0, F(a,0,0) = 1, since there is only 1 way to walk from (0, 0, 0) to (a, 0, 0)
#if a = 0, c = 0, F(0,b,0) = 1, since there is only 1 way to walk from (0, 0, 0) to (0, b, 0)
#if a = 0, b = 0, F(0,0,c) = 1, since there is only 1 way to walk from (0, 0, 0) to (0, 0, c)

#By the induction hypotbesis we assume:
#F(a,b,c-1) = (a+b+c-1)!/(a!*b!*(c-1)!)
#F(a,b-1,c) = (a+b+c-1)!/(a!*c!*(b-1)!)
#F(a-1,b,c) = (a+b+c-1)!/(b!*c!*(a-1)!)

#Hence
#F(a,b,c) = F(a,b,c-1) + F(a,b-1,c) + F(a-1,b,c)
#         = (a+b+c-1)!/(a!*b!*(c-1)! + (a+b+c-1)!/(a!*c!*(b-1)!) + (a+b+c-1)!/(b!*c!*(a-1)!)
#         = (a+b+c-1)!*(1/(a!*b!*(c-1)!) + 1/(a!*c!*(b-1)!) + 1/(b!*c!*(a-1)!))
#         = (a+b+c-1)!*(1/(a*(a-1)!*b*(b-1)!*(c-1)!) + 1/(a*(a-1)!*(b-1)!*c*(c-1)!) + 1/((a-1)!*b*(b-1)!*              c*(c-1)!))
#         = ((a+b+c-1)!/((a-1)!*(b-1)!*(c-1)!))*(1/(a*b) + 1/(a*c) + 1/(b*c))
#         = ((a+b+c-1)!/((a-1)!*(b-1)!*(c-1)!))*((c+b+a)/(a*b*c))
#         = (a+b+c)!/(a!*b!*c!)

#2.
#Explain, in plain English, why the number of walks in the k-dimensional Manhattan lattice from {0,0,...,0} to {a[1],a[2],...,a[k]} is the same number of words in the "alphabet" {1,2,...,k} with the letter i showing up exactly a[i] times (i=1..k)

#The number of walks in the k-dimensional Manhattan lattice from (0,0,...,0) to (a[i],a[2],...,a[3]) is as the same number of words in the alphabet {1,2,...,k} with the letter i showing up exactly a[i] times because different letters in the alphabet are essentially different dimensions, with additional repetitions of a letter i being like additional steps in the ith direction.

#3.
#State the explicit formula for the number of words in the "alphabet" {1,2,...,k} with the letter i showing up exactly a[i] times(i=1..k) and prove it completely.

#Number of words = (a[1]+a[2]+...+a[i])!/(a[1]*!a[2]!*...*a[i]!)
#Let n = total number of letters
#Out of n letters, we need to choose a[1] of them to be 1's,
#then out of n-a[1] letters, we need to choose a[2] of be 2's,
#then out of n-a[1]-a[2] letters, we need to choose a[3] of them to be 3's,
#and so on...
#until out of n-a[1]-a[2]-a[3]-...-a[k-1] = a[k] letters, we need to choose a[k] of them to be k's
#This can be represented by:
#binomial(n, a[1]) * binomial(n-a[1], a[2]) * binomial(n-a[1]-a[2], a[3]) * ... * binomial(a[k], a[k])

#This is equivalent to:
#n!/((n-a[1])!*a[1]!) * (n-a[1])!/((n-a[1]-a[2])!*a[2]!) * (n-a[1]-a[2])!/((n-a[1]-a[2]-a[3])!*a[3]!)... * (n-a[1]-a[2]-...-a[k-1])!/((n-a[1]-a[2]-a[3]-...-a[k])!*a[k]!)

#As you can see, the denominators of a term partially cancel out with the numerators of the next term, until we are left with:
#n!/(a[1]!*a[2]!*a[3]!*...*a[k]!)

#4.
#Generalalize procedure Walks(m,n) from the Maple Code for Lecture 1 to write a procedure RestrictedWalks(m,n,S) that inputs nonnegative integers m and n as before, but also a finite set of lattice points S, and outputs the set of walks from [0,0] to [m,n] (with the same fundamental steps as before, i.e. [1,0](E) and [0,1](N)) that never visit the members of S.
#For example, RestrictedWalks(2,2,{[1,1]})); should output {[E,E,N,N],[N,N,E,E]}.

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

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

#we put this condition before the m=0 and n=0 condition, because what if [0,0] is in the restricted set? Then we want {} as the answer, not {[]}
if [m,n] in S 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]})
                  {[E, E, N, N], [N, N, E, E]}


#5.
#Generalalize procedure NuWalks(m,n) from the Maple Code for Lecture 1 to write a procedure RestrictedNuWalks(m,n,S) that inputs nonnegative integers m and n as before, but also a finite set of lattice points S, and outputs the set of walks from [0,0] to [m,n] (with the same fundamental steps as before, i.e. [1,0](E) and [0,1](N)) that never visit the members of S.
#For example, RestrictedNuWalks(2,2,{[1,1]}); should output 2.
#What is RestrictedNuWalks(50,50,{seq([i,i], i=1..50)});?

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

if m < 0 or n < 0 then
 RETURN(0);
end if;

if [m, n] in S then
 RETURN(0);
end if;

if m = 0 and n = 0 then
 RETURN(1);
end if;

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

W1 + W2; 
end proc;

RestrictedNuWalks(2, 2, {[1, 1]});
                               2

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