# Daniel Yang, Due Sept. 13, 9:00pm
# OK to post Homwork
# 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 by Induction
# Let F(m,n,z) be the RHS such that F(m,n,z) = (m+n+z)!/(m!*n!*z!)
# if m=0 and n=0, F(0,0,z) = 1 
# if m=0 and z=0, F(0,n,0) = 1
# if n=0 and z=0, F(m,0,0) = 1
# (Only one possible direction to go with only one directional moves)
# using the Inductive Hypothesis, we can assume that
# F(m,n,z-1) = (m+n+z-1)!/(m!*n!*(z-1)!)
# F(m,n-1,z) = (m+n+z-1)!/(m!*(n-1)!*z!)
# F(m-1,n,z) = (m+n+z-1)!/((m-1)!*n!*z!)
# Thus,
# F(m,n,z) = F(m,n,z-1) + F(m,n-1,z) + F(m-1,n,z)
# 	  = (m+n+z-1)!/(m!*n!*(z-1)!) + (m+n+z-1)!/(m!*(n-1)!*z!) + (m+n+z-1)!/((m-1)!*n!*z!)
#	  = (m+n+z-1)!(1/(mn(m-1)!*(n-1)!*(z-1)!) + 1/(mz(m-1)!*(n-1)!*(z-1)!) + 1/(nz(m-1)!*(n-1)!*(z-1)!))
#	  = (m+n+z-1)!/((m-1)!*(n-1)!*(z-1)!) * (1/mn + 1/mz + 1/nz)
#	  = (m+n+z-1)!/((m-1)!*(n-1)!*(z-1)!) * ((m + n + z)/(mnz))
#	  = (m+n+z)!/(m!*n!*z!)
# QED 

# 2) 
# We can  be able to say that the k-dimensional Manhattan lattice is exactly 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). This is due to the fact that choosing a direction 
# in an k-dimensional space is the same as picking a word from a k sized alphabet 
# and then choosing another word/direction. In fact, we can represent a direction as 
# a letter in a k sized alphabet and the word created is the directions to get from 
# start to the end destination.


# 3) 
# Let S = sum(a[i],i=1..k)
# Since a[1] represents the number of occurences of the letter '1'. a[2] 
# represents the number of occurences of the letter '2', etc.
# We can say that the posssible choices for a[1] is binomial (S, a[1]), 
# and after removing letters '1', a[2] as binomial(S-a[1], a[2]), etc.
# Thus we get that for all a[i] from 1 to k, we get that for all occurences of a[i] as 
# binomial(S,a[1])*binomial(S-a[1],a[2])*binomial(S-a[1]-a[2],a[3])*...*binomial(S-a[1]-a[2]-a[3]-...-a[k-1], a[k])
# = S!/((S-a[1])!*(a[1])!)*(S-a[1])!/((S-a[1]-a[2])!*(a[2])!)*...*(S-a[1]-a[2]-...-a[k-1])!/((S-a[1]-a[2]-...-a[k])!(a[k])!)
# Since we can cancel out the numerator and denominator for most of this equation, we get
# = S!/(a[1]!a[2]!a[3]!...a[k]!)
# Thus, 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) is S!/(a[1]!a[2]!a[3]!...a[k]!)

# 4 & 5)

#
Help1:=proc():print(`RestrictedWalks(m,n,S), RestrictedNuWalks(m,n,S) `): end:

# RestrictedWalks(m,n): inputs two non-negative integers m, n and set S
# and outputs the SET of all walks {E,N} from [0,0] to [m,n]
# without reaching any coordinates in set S
# all the rearramgemets of E^m N^n [ Added 9/10/20: Correcting a typo noticed by Jehan  Abdul-Jabbar]
RestrictedWalks:=proc(m,n,S) local W1,W2,w1,w2,pair:
option remember:

pair:=[m,n]:

if member(pair, 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:


# RestrictedNuWalks(m,n,S): inputs two non-negative integers m, n and set S
# and outputs the SET of all walks {E,N} from [0,0] to [m,n]
# without reaching any coordinates in set S
# all the rearramgemets of E^nN^m
RestrictedNuWalks:=proc(m,n,S) local W1,W2,w1,w2,pair:
option remember:

pair:=[m,n]:

if member(pair, 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(50,50,{seq([i,i],i=1..50)});
# This function call results in  0, due to the fact that the ending coordinnates are
# restricted, resulting in 0 possible ways to reach the end result