#OK to post homework
#Karnaa Mistry, 09/13/20, Assignment HW #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 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!)

# F(a,b,c) = (a+b+c)!/(a!*b!*c!)
# Let G(a,b,c) be the RHS, so G(a,b,c) = (a+b+c)!/(a!*b!*c!)
# Prove for every a,b,c F(a,b,c), and thus G(a,b,c).

# Proof: Induction on a,b,c
# if a,b = 0 then F(a,b,c) = 1 (there is only one way to walk from [0,0,0] to [0,0,c]
# if b,c = 0 then F(a,b,c) = 1 (" from [0,0,0] to [a,0,0]
# if a,c = 0 then F(a,b,c) = 1 (" from [0,0,0] to [0,b,0]
# By the Inductive Hypothesis we assume
# F(a,b,c-1) = (a+b+c-1)!/(a!*b!*(c-1)!)
# F(a,b-1,c) = (a+b-1+c)!/(a!*(b-1)!*c!)
# F(a-1,b,c) = (a-1+b+c)!/((a-1)!*b!*c!)
# And so,
# 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-1+c)!/(a!*(b-1)!*c!) + (a-1+b+c)!/((a-1)!*b!*c!)
# = (a+b+c-1)! * ( 1/(a!*b!*(c-1)!) + 1/(a!*(b-1)!*c!) + 1/((a-1)!*b!*c!) )
# = (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/(ab) + 1/(ac) + 1/(bc) )
# = (a+b+c-1)!/((a-1)!*(b-1)!*(c-1)!) * ( (a+b+c)/(a*b*c) )
# = (a+b+c)! / (a! * b! * c!)
# We have concluded that it is true



# 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 there are k unique letters in that "alphabet"
# just as there are k unique positive "directions" to move 1 unit in the k-dimensional Manhattan lattice.  The final path will can some arrangement
# of these unique letters, and we will have to travel a certain number of times in each of those k directions, similar to how we have a
# certain frequency for each unique letter.  So, it's just like "writing" out the path in the k-dimensional lattice out of moves in each
# of the positive k directions, and writing the path is the same as arranging letters as if they were a word, as well.



# 3.


# The explicit formula is  (a[1]+...a[k])! / (a[1]!*...*a[k]!)

# Conceptually, let F(a[1],...,a[k]) = (a[1]+...+a[k])!/(a[1]!*...*a[k]!)
# Let G(a[1],...,a[k]) be the RHS, so G(a[1],...,a[k]) = (a[1]+...+a[k])!/(a[1]!*...*a[k]!)
# Prove for every a[1],...,a[k] F(a[1],...,a[k]), and thus G(a[1],...,a[k]).

# Proof: Induction on a[1],...,a[k]
# let i be an integer from 1 to k:
# for each i, when ALL elements of the list EXCEPT a[i] are 0, there is only 1 way to walk from [0_1,...,0_k] to [a[i],...,a[k]]
# this is because we only need to walk in 1 direction to get to that particular a[i]

# By the Inductive Hypothesis we assume
# F(a[1]-1,...,a[k]) = (a[1]-1+...+a[k])!/((a[1]-1)!*...*a[k]!)
# ... etc. (replace a[i] with a[i]-1 for particular i from 1 to k)
# F(a[1],...,a[k]-1) = (a[1]+...+a[k]-1)!/(a[1]!*...*(a[k]-1)!)

# And so,
# F(a[1]-1,...,a[k]) = (a[1]-1+...+a[k])!/((a[1]-1)!*...*a[k]!) + ... + (a[1]+...+a[k]-1)!/(a[1]!*...*(a[k]-1)!)
# = (a[1]+...+a[k]-1)! * ( 1/((a[1]-1)!*...*a[k]!) + ... + 1/(a[1]*...*(a[k]-1)!) )
# = (a[1]+...+a[k]-1)! * ( 1/((a[1]-1)!*...*a[k]*(a[k]-1)!) + ... + 1/(a[1]*(a[1]-1)!*...*(a[k]-1)!) )
# = (a[1]+...+a[k]-1)!/((a[1]-1)!*...*(a[k]-1)!) * ( 1/(a[2]*...*a[k]) + 1/(a[1]*...*a[k-1]) )
# = (a[1]+...+a[k]-1)!/((a[1]-1)!*...*(a[k]-1)!) * ( (a[1]+...+a[k])/(a[1]*...*a[k]) )
# = (a[1]+...+a[k])! / (a[1]! * ... * a[k]!)
# We have concluded that the generalized formula is true



# 4.


#RestrictedWalks(m,n,S): inputs non-negative integers m and n and finite set S of lattice points, and outputs the
#SET of walks from [0,0] to [m,n] with fundamental steps [0,1] and [1,0], that NEVER visit the members of S.
RestrictedWalks:=proc(m,n,S) local W1,W2,w1,w2:
option remember:

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

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

if member([0,0],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:



# 5.


#RestrictedNuWalks(m,n,S): inputs non-negative integers and finite set of lattice points S and outputs the NUMBER of walks from [0,0]
# to [m,n] following the restrictions in RestrictedWalks
RestrictedNuWalks:=proc(m,n,S) local W1,W2,w1,w2:
option remember:

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

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

if member([0,0],S) 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:

# The answer to RestrictedNuWalks(50,50,{seq([i,i],i=1..50}); is 0, because the point [50,50] is contained in the sequence, and thus
# [50,50] is contained in S.  So, there are no walks to a destination where the destination point itself is restricted from access.