#OK to post homework 
#Zhizhang Deng, 09/22/2020, Assignment 2

1. Proof by induction 
Let F(a, b, c) be number of walks from [0,0,0] to [a,b,c] in 3D manhattan lattice
Let G(a, b, c) = (a + b + c)!/(a!*b!*c!)

Theorem left to prove: G(a, b, c) = F(a, b, c)
Prove by induction. In duce on a, b and c. 
3 Special cases 

F(0, b, c) = G(0, b, c), F(a, 0, c) = G(a, 0, c), F(a, b, 0) = G(a, b, 0) (we proved this already in NE walk problem)

Assume F(a - 1, b, c), F(a, b - 1, c), F(a, b, c - 1) are all true(equal to G). we need to prove F(a, b, c) = G(a, b, c) is also true 

F(a, b, c) = F(a - 1, b, c) + F(a, b - 1, c) + F(a, b, c - 1)
= G(a - 1, b, c) + G(a, b - 1, c) + G(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)!)
...
after simplify
= (a + b + c)!/(a!*b!*c!) = G(a, b, c)

What we have proved is that given F=G for (a-1,b,c) and (a,b-1,c) and (a,b,c-1). Then F=G for (a,b,c). The reason this would prove for all a,b,c is because that to prove F=G for arbitrary (a,b,c), I only need to prove all three (a-1,b,c), (a,b-1,c) and (a,b,c-1) are true. And keep recursing, at some point, at least one of a,b,c would be zero which would be our base case. which will be true. 

2. 
This is true because we can think of the each possible letter in the alphabet of an axis in the k-dimensional walk. For example, an alplabet 'aabbb' means that we can construct a manhattan lattice of width 2(we have 2 a) and height 3(we have 3 b). And then all the possible words that we can form using this alphabet is essentially the walk from 0,0  to (2, 3), and each time we walk upwards we are using a 'b', each time we are walking right side we are using a 'a'. After we reach the (2,3), we have used all the possible characters in the alphabet

3. (sum_(i=1->k)(a[i]))! / PI_(i = 1->k)(a[i]!)
By using answer to question 2, we can change this question to 'give number of walks possible to a point (a[1], a[2], ..., a[k]) in a k-dimensional manhattan lattice'. 
we know that number of walks possible to a point (a, b, c) in a 3-dimensional manhattan lattice is (a + b + c)!/(a!*b!*c!), which is equal to our proposed formula with k = 3, a[1] = a, a[2] = b, a[3] = b. Note that when we were proving this formula in question 1, we are actually utilizing the result of the prove of dimensional 2 walk. By using this concept we can prove dimensional 4 using result of dimensional 3, prove dimensional 5 using dimensional 4 etc. 

To prove The proposed formula is correct, we can assume that the formula is correct for dimension k - 1. 

And our dimension-3 result is our base case. 
So, we have assumed (sum_(i=1->k - 1)(a[i]))! / PI_(i = 1->k - 1)(a[i]!) is the number of possible walks in dimension k - 1. And we need to prove that in dimension k, our walk is (sum_(i=1->k)(a[i]))! / PI_(i = 1->k)(a[i]!). 

	To prove this, we need to use another layer of induction prove. 
	Let F(a[1], a[2], ... a[k]) = number of walks possible to the point a[1], a[2] ... a[k] from (0, ... k zero in here) in a k-dimensional lattice. 
	And let G(a[1], a[2], ... a[k]) = (sum_(i=1->k)(a[i]))! / PI_(i = 1->k)(a[i]!)
	we would have k base cases, 
	base case 1. F=G for point (0, a[2], a[3] ... a[k])
	base case 2. F=G for poitn (a[1], 0, a[3] ... a[k]).
	...
	these base cases are true because of our outer induction assumption. 

	now we assume that F=G for points (a[1] - 1, a[2], a[3] ... a[k]), (a[1], a[2] - 1, a[3] ... a[k]) ... (a[1], a[2], ... a[k] - 1)

	we need to prove that F=G for point (a[1], a[2], ... a[k])

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

	Thus, F(a[1], a[2], ... a[k]) = G(a[1] - 1, a[2], ... a[k]) + ... G(a[1], a[2], a[k] - 1) [ this is by our inner induction assumption ]

	Now if we expand this equation, we will have F(a[1], a[2], ... a[k]) = (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)!)

	Notice that in this equation we have k terms adding together. Denote each term be A[i], if we multiply A[i] by (a[i] / a[i]), all k terms denominator would have became a[1]!*a[2]!*...a[k]!. Also notice that at the top part of each term, before we multiply (a[i] / a[i]), they are exactly the same. So because after the multiplication, all these terms denominator are the same, we can concatenate top part and also factor out (a[1] + a[2] + ... a[k] - 1)!, since all these k terms have them. 

	Then we will have 
	F(a[1], a[2], ... a[k]) = ((a[1] + a[2] + ... a[k] - 1)! * (a[1] + a[2] + ... a[k])) / (a[1]! * a[2]! * ... a[k]!)
	By the definition of factorial, the top part of this fraction can be simplified, then we have
	F(a[1], a[2], ... a[k]) = (a[1] + a[2] + ... a[k])! / (a[1]! * a[2]! * ... a[k]!)

	which is G(a[1], a[2], ... a[k]). 
	Thus, F(a[1], a[2], ... a[k]) = G(a[1], a[2], ... a[k]) given F=G for points (a[1] - 1, a[2], a[3] ... a[k]), (a[1], a[2] - 1, a[3] ... a[k]) ... (a[1], a[2], ... a[k] - 1). 

	Combined with our base cases, F=G for all a[1], a[2] ... a[k] because during recursion, one of a[i] has to reach zero and our base cases would catch that. 

So in the inner induction prove, we proved that in dimension k, our walk is (sum_(i=1->k)(a[i]))! / PI_(i = 1->k)(a[i]!). given that (sum_(i=1->k - 1)(a[i]))! / PI_(i = 1->k - 1)(a[i]!) is the number of possible walks in dimension k - 1. Because this formular is true for our base case which k = 3, by induction prove, we have proven this for all k. 

4. 

===== CODE BELOW =====
RestrictedWalks := proc(m, n, S) local W1, W2, w1, w2; 
option remember; 
if m < 0 or n < 0 then 
	RETURN({}); 
end if; 
if [m, n] in 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
=====  CODE END  =====

5. 
===== CODE BELOW =====
RestrictedNuWalks := proc(m, n, S) local W1, W2, w1, w2; 
option remember; 
if m < 0 or n < 0 then 
	RETURN(0); 
end if; 
if [m, n] in 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;

=====  CODE END  =====