OK to post

#Eshaan Gandhi, 09/13/2020, Assignment 2
#Q. 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!)


#answer to the above question:

#We will use the method of mathematical induction to prove the above statement

We want to prove that F(a, b, c) = (a+b+c)!/(a!*b!*c!)

F(1, 0, 0) = 1!/1!0!0! = 1
F(0, 1, 0) = 1!/1!0!0! = 1
F(0, 0, 1) = 1!/1!0!0! = 1

We assume that F(a-1, b, c)= (a+b+c-1)!/((a-1)!b!c!)
 F(a, b-1, c)= (a+b+c-1)!/(a!(b-1)!c!)
 F(a, b, c-1)= (a+b+c-1)!/(a!b!(c-1)!)

F(a, b, c)= F(a-1, b, c)+F(a, b-1, c)+F(a, b, c-1)

=(a+b+c-1)!*( 1/((a-1)!b!c!)+1/(a!(b-1)!c!)+1/a!b!(c-1)!)
=(a+b+c-1)!/((a-1)!(b-1)!(c-1)!)(1/a+1/b+1/c)
=(a+b+c-1)!/((a-1)!(b-1)!(c-1)!)((a+b+c)/abc)
=(a+b+c)!/(a!b!c!)

QED

2. When we think about making a word we basically are going through a maze to construct whatever word we have to make. For eg. if we want to make the word that contains "112223" we just walk through a lattice taking the step "1" whenever we want to, just like a k dimensional manhattan lattice. 

3. #a[i] = {1,2,...k}

#number of words = (1+2+3+...+k)!/(1!2!3!...k!)




#4. Walks(m,n)

#from the Maple Code for Lecture 1 to write a procedure

#RestrictedWalks(m,n,S)

#that inputs non-negative 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]}


Answer to following:

RestrictedWalks := proc(m, n, S) local W1, W2, w1, w2, l1, i; 
option remember; 
l1 = [m, n]; 
if m < 0 or n < 0 then 
RETURN({}); end if; 
if member([m, n], S) then 
RETURN({}); 
end if; 
if m = 0 and n = 0 
then RETURN({[]}); 
end if; 

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 proc

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

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

if member([m, n], 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