#Ok to post homework
#Tifany Tong, September 12th, 2020, HW #2

#Question 1:
# We will be proving that F(a,b,c) = (a+b+c)/(a!*b!*c!) is the number of walks to go from [0,0,0] to [a,b,c].
# We will use proof by induction to do this. 
# Looking at our base cases, we see that if a = 0 and b = 0, then F(a,b,c) = 1. If a = 0 and c = 0, then F(a,b,c) = 1. If b = 0 and c = 0, then F(a,b,c) = 1.
# By our inductive hypothesis, we assume that F(a,b,c-1) = F(a+b+c-1)!/(a!*b!*(c-1)!), F(a,b-1,c) = F(a+b+c-1)!/(a!*(b-1)!*c!), and F(a-1,b,c) = F(a+b+c-1)!/((a-1)!*b!*c!).
# Then, F(a,b,c) = F(a-1,b,c) + F(a,b-1,c) + F(a,b,c-1) = (a+b+c-1)!/((a-1)!*b!*c!) + (a+b+c-1)!/(a!*(b-1)!*c!) + (a+b+c-1)!/(a!*b!*(c-1)!) =
# (a+b+c-1)! *(1/(a! * (b-1)! * c!) + 1/((a-1)!*b!*c!) + 1/(a!*b!*(c-1)!)) =
# (a+b+c-1)! *(1/ac * 1/((a-1)! * (b-1)! * (c-1)!) + 1/bc * 1/((a-1)! * (b-1)! * (c-1)!) + 1/ab * 1/((a-1)! * (b-1)! * (c-1)!)) =
# (a+b+c-1)!/(1/((a-1)!*(b-1)!*(c-1)!)) * ((a+b+c)/abc) = (a+b+c)!/(a!*b!*c!) QED. 


#Question 2

#The number of walks in the k-dimensional Manhattan lattice is the same as the number of words in the "alphabet" with the letter i showing
# up exactly a[i] times is because we can represent the the directions we need to walk in the k-dimensional Manhattan lattice as letters. For example,
# in class when we were doing the number of walks in the 2-D grid, we represented the direction as N and E. To get from (0,0) to (a,b), we would need
# a N's and b E's to reach (a,b). In 3-D, we'd need a N's (representing moving in (1,0,0 direction)), b E's (representing moving in (0,1,0 direction)),
# and c Z's (representing moving in (0,0,1 direction)) to go from (0,0,0) to (a,b,c). The letters (N, E, and Z) are used to show that 
# going in a direction is like a choosing a letter. As a result, the walks question boils down to a question of the number of unique rearrangements 
# of letters in a word. 

#Question 3: 

# The formula is (a[1] + a[2] + a[3] + ... + a[k])!/(a[1]!*a[2]!*a[3]!* ... *a[k]!).
# Let's let the total number of letters be N. So, N = a[1] + a[2] + .... + a[k]. Of these n letters, a[1] of them will be chosen to be 1.
# Then, of N-a[1] letters (the remaining letters after 1's are chosen), N-a[1]-a[2] letters will be chosen to be 2. For N-a[1]-a[2] letters 
#(the remaining letters after 1 and 2 are chosen). This continues until we need N-a[1]-a[2]-a[3]-a[4].....-a[k-1] letters to be k. 
# All of this can be represented as (N Choose a[1]) * (N-a[1] Choose a[2]) * .... (N-a[1]-a[2]-....-a[k-1] choose a[k]). 
# This is then equivalent to N!/((n-a[1])! * a[1]!) * (N-a[1])!/((N-a[1]-a[2])! * a[2]!) * ..... * (N-a[1]-a[2]-a[3]-...-a[k-1])!/(N-a[1]-a[2]-...-a[k])! * a[k]!).
# Part of the denominator in the previous term cancels out with the numerator of a term. For example, (n-a[1])! appears in both the numerator and denominator.
# This pattern continutes of being able to cancel out a term in the denominator and numerator. By the end, we get
# N!/(a[1]! * a[2]! * a[3]! * a[3]! * ... *a[k-1]! * a[k]!). By substituing the value we have as N, we finally get:
# (a[1] + a[2] + a[3] + .... + a[k])!/(a[1]! * a[2]! *a[3]! * ... * a[k]!), which is the formula we set out for. 

#Question 4:

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

if m < 0 or n < 0 then RETURN({}): fi:
curr:=[m,n]:
if member(curr,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:

#Question 5:

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

if m < 0 or n < 0 then RETURN(0): fi:
curr:= [m,n]:
if m = 0 and n = 0 and member(curr,s) then RETURN(0): fi:
if m = 0 and n = 0 then RETURN(1): fi:
if member(curr,s) then RETURN(0): fi:
W1:= RestrictedNuWalks(m-1,n,s):
W2:= RestrictedNuWalks(m,n-1,s):
W1+W2:
end:

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