#OK to post homework
#Soham Palande, 09/10/2020, Assignment 2


#Part 1- Human Proof

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:

We showed that F(m,n) for a 2-d Manhattan lattice is (m+n)!/(m!*n!).

Let G(m,n)=(a+b+c)!/(a!*b!*c!)

To show that for every m and n , F(m,n)=G(m,n)

Then we have,

F(0,b,c)= (b+c)!/(b!*c!)
F(a,0,c)= (a+c)!/(a!*c!)
F(a,b,0)= (a+b)!/(a!*b!)

By inductive hypothesis we assume:

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

Then we know,

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

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

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

Using transformation m!=(m-1)!*m

F(a,b,c)= (a+b+c-1)! * [(1/((a-1)!*b*(b-1)!*c*(c-1)!)) + (1/(a*(a-1)!*(b-1)!*c*(c-1)!)) +  (1/(a*(a-1)!*b*(b-1)!*(c-1)!))]

Factoring out denominator,

F(a,b,c)= [(a+b+c-1)!/((a-1)!*(b-1)!*(c-1!))] * [(1/(b*c)) + (1/(a*c)) +  (1/(a*b))]


F(a,b,c)= [(a+b+c-1)!/((a-1)!*(b-1)!*(c-1!))] * [(a+b+c)/(a*b*c)]
   
        = (a+b+c)!/(a!*b!*c!)
        = G(m,n)
Hence Proven!





#Part 2-

The number of walks in the K-dimensional Manhattan Lattice is the same as the
Number of words in the "alphabet" {1, 2, ..., k} or any k-dimensional alphabet.

We initially considered the two dimensional walk in the 2-d Manhattan lattice and modeled it as a walk from the origin (0,0) to some arbitrary point (m.n) where m and n were non negative. The walks could be modeled as a word in the "alphabet" {E,N} (where E and N corresponds to the steps (1,0) and (0,1) respectively). Each list or "word" we produced (i.e. a walk from (0,0) to (m.n)) had m E's and n N's and thus could be considered as a rearrangement of the word from the "alphabet" {E,N} having m E's and n N's. 

Now, if we consider walks in the K-dimensional Manhattan lattice, from (0,0,...,0) to (a[1],a[2],...a[k]) taking only positive steps in each dimension, each such walk must have a[1] steps in the first dimension, a[2] steps in the second dimension,... a[k] walks in the kth dimension. Then if each dimension corresponds to a letter, the walks can be thought of as the rearrangement of a word having a[1] occurrences of some arbitrary letter 1, a[2] occurrence of some distinct letter 2, ... and a[k] occurrences of some distinct letter k. Thus we can say the a walk in the k-dimensional Manhattan lattice from (0,0,...,0) to (a[1],a[2],...a[k]) can be though of as the rearrangements of the word from the "alphabet" {1,2,...k} with a[1] 1's, a[2] 2's, .... and a[k] k's. 


#Part 3- 

The number of words in the "alphabet" {1,2,...k} with the letter i showing up a[i] times (i=0,1,...k) can be given by:  

F(a[0],a[1],...a[k]) = (a[0] + a[1] + ... + a[k])! / (a[0]! * a[1]! * ... * a[k]!)

PROOF:
 
Let G(a[1],a[2],...a[k])= (a[0] + a[1] + ... + a[k])! / (a[0]! * a[1]! * ... * a[k]!)

We know 

F(a[1],0,0,...,0) = 1 (since there is only one way to go from (0,0,...0) to     
                       (a[1],0,0,...0) )
F(0,a[2],0,...,0) = 1 (since there is only one way to go from (0,0,...0) to     
                       (0,a[2],0,...0) )
.
. for a[i]; i=3,...k-1
.

F(0,0,0,...,a[k]) = 1 (since there is only one way to go from (0,0,...0) to     
                       (0,0,...a[k]) )

By inductive hypothesis, we assume:

F(a[1]-1,a[2],...a[k]) = (a[1]-1+a[2]+...a[k])! / [(a[1]-1)! * a[2]! * ... * a[k]!]

F(a[1],a[2]-1,...a[k]) = (a[1]+a[2]-1+...a[k])! / [(a[1]! * (a[2]-1)! * ... * a[k]!]
.
.  For a[i] i=3,...k-1
.
F(a[1],a[2],...a[k]-1) = (a[1]+a[2]+...a[k]-1)! / [a[1]! * a[2]! * ... * (a[k]-1)!]


Then we know, 

F(a[1],a[2],...a[k]) = F(a[1]-1,a[2],...a[k]) + F(a[1],a[2]-1,...a[k]) + F(a[1],a[2],...a[k]-1)

		     = (a[1]-1+a[2]+...a[k])! / [(a[1]-1)! * a[2]! * ... * a[k]!] +     
                       (a[1]+a[2]-1+...a[k])! / [(a[1]! * (a[2]-1)! * ... * a[k]!] +
		       (a[1]+a[2]+...a[k]-1)! / [a[1]! * a[2]! * ... * (a[k]-1)!]


Factoring out the numerator,

F(a[1],a[2],...a[k]) = (a[1]+a[2]+...a[k]-1)! * [ (1/(a[1]-1)! * a[2]! * ... * a[k]!) + (1/(a[1]! * (a[2]-1)! * ... * a[k]!) + (1/a[1]! * a[2]! * ... * (a[k]-1)!)]


Using formula m!= m*(m-1)!, for all a[i] in the denominator,

F(a[1],a[2],...a[k]) = (a[1]+a[2]+...a[k]-1)! * [ (1/(a[1]-1)! * a[2]* (a[2]-1)! * ... * a[k] * (a[k]-1)!) + (1/(a[1]*(a[1]-1)! * (a[2]-1)! * ... * a[k]*(a[k]-1)!) + (1/a[1]* (a[1]-1)! * a[2]*(a[2]-1)!      
                       
                       *...*(a[k]-1)!)]


F(a[1],a[2],...a[k]) = (a[1]+a[2]+...a[k]-1)! * [ (1/(a[1]-1)! * a[2]* (a[2]-1)! * ... * a[k] * (a[k]-1)!) + (1/(a[1]*(a[1]-1)! * (a[2]-1)! * ... * a[k]*(a[k]-1)!) + (1/a[1]* (a[1]-1)! * a[2]*(a[2]-1)!      
                       
                       *...*(a[k]-1)!)]

Factoring the denominator, 

F(a[1],a[2],...a[k]) = [(a[1]+a[2]+...a[k]-1)! / ((a[1]-1)! * (a[2]-1)! * ...(a[k]-1)!)] * [ (1/(a[2]* ... * a[k])) + (1/(a[1] * ... * a[k])) + (1/(a[1]* a[2]*...*a[k-1]))]


F(a[1],a[2],...a[k]) = [(a[1]+a[2]+...a[k]-1)! / ((a[1]-1)! * (a[2]-1)! * ...(a[k]-1)!)] * [ (a[1] + a[2] + ...+ a[k]) / (a[1] * a[2]* ... * a[k]) ]

Simplifying we get, 

F(a[0],a[1],...a[k]) = (a[0] + a[1] + ... + a[k])! / (a[0]! * a[1]! * ... * a[k]!)
                     =G(a[1],a[2],...a[k])

If we let a[1]+a[2]+...a[k]=n then we have 

F(a[0],a[1],...a[k]) = n! / (a[0]! * a[1]! * ... * a[k]!)


Hence Proven!


#Part 4- Challenge Maple Procedure


#RestrictedWalks(m,n,S): inputs two non-negative integers m and n and a finite #set of lattice points S
#and outputs the SET of all walks that do not visit the points in S- {E,N} #from [0,0] to [m,n] 

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

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


if m=0 and n=0 then
 RETURN({[]}):
fi:

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




#Part 5- Challenge Maple Procedure

#RestrictedNuWalks(m,n,S):inputs two non-negative integers m and n and a #finite set of lattice points S
#and outputs the TOTAL NUMBER of all walks that do not visit the points in #S- {E,N} from [0,0] to [m,n]  
RestrictedNuWalks:=proc(m,n,S) local W1,W2,w1,w2:
option remember:

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


if m=0 and n=0 then
 RETURN(1):
fi:

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


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


W1+W2:
end:

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