PART 1:

We will prove that the number of walks from [0,0,0] to [a,b,c] is given by (a+b+c)!/(a!*b!*c!) for any a,b,c positive integers using mathematical induction.

Let F(m,n,k) = (m+n+k)!/(m!*n!*k!).

Base Case:
If k = 0, F(m, n, 0) = (m+n)!/(m!*n!) by our theorem for the number of walks in 2 dimensions.
Similarly, if n = 0, F(m, 0, k) = (m+k)!/(m!*k!).
Similarly, if m = 0, F(0, n, k) = (n+k)!/(n!*k!).

By the inductive hypothesis, we assume:
F(m-1,n,k) = (m+n+k-1)!/((m-1)!*n!*k!),
F(m,n-1,k) = (m+n+k-1)!/(m!*(n-1)!*k!),
F(m,n,k-1) = (m+n+k-1)!/(m!*n!*(k-1)!).

The number of walks given by F(m,n,k) = F(m-1,n,k) + F(m,n-1,k) + F(m,n,k-1): 

(m+n+k-1)!/((m-1)!*n!*k!) + (m+n+k-1)!/(m!*(n-1)!*k!) + (m+n+k-1)!/(m!*n!*(k-1)!) =
(m+n+k-1)! * (1 / n*k*(m-1)!*(n-1)!*(k-1)!  + 1 / m*k*(m-1)!*(n-1)!*(k-1)!  + 1 / (m*n*(m-1)!*(n-1)!*(k-1)!) =
(m+n+k-1)!/(n-1)!*(m-1)!*(k-1)! * (1/n*k + 1/m*k + 1/m*n) = 
(m+n+k-1)!/(n-1)!*(m-1)!*(k-1)! * ( m+n / m*n*k  + 1/m*n ) =
(m+n+k-1)!/(n-1)!*(m-1)!*(k-1)! * ( m*n*(m+n+k) / m^2*n^2*k) = 
(m+n+k-1)!/(n-1)!*(m-1)!*(k-1)! * ( m+n+k / m*n*k) = 
(m+n+k)!/(m!*n!*k!).

Thus, by induction the equality holds in the 3 dimensional case.

PART 2:

In the number of walks in the k-dimensional Manhattan lattice, we find the number of walks from [0,0,0,…,0] to [x_1, x_2, x_3, …, x_k]. In the first dimension we have to walk x_1 units, in the second dimension we have to walk x_2 units, in the third dimension we have to walk x_3 units, and so on. However, we can rearrange the order in which we walk those units as long as we end up walking the required amount of units in each direction. In the number of words in the "alphabet" {1,2,...k} with the letter i showing up exactly a[i] times (i=1..k), we do something very similar. For the letter 1, we have to have a[1] copies of 1. For the letter 2, we have the have a[2] copies of 2 and so on. However, we can arrange the letters in any order we want as long as each letter i occurs a[i] times. Say that we have x_i = a[i] for all i, then we have the same problem of rearranging i, x_i times in any order. Therefore, they are the same problem.

PART 3:

Since the number of words in the "alphabet" {1,2,...k} with the letter i showing up exactly a[i] times (i=1..k) problem is equivalent to the number of walks in the k-dimensional Manhattan lattice from [0,0...,0] to [a[1], ..., a[k]] problem, we would expect that explicit formula would be (a[1] + a[2] + … + a[k])! / a[1]! * a[2]! * … * a[k]!. We want to prove this for all k >= 2. We will do so using mathematical induction.

Let F(x_1, x_2, …, x_k) = (x_1 + … + x_k)! / (x_1! * … * x_k!).

Base case:
For k=2, we have shown that F(x_1, x_2) = (x_1 + x_2)! / (x_1! * x_2!).

By strong induction, assume that the equality holds for k = 3…n-1, n > 2. We want to show that the equality holds for k = n, namely, F(x_1, x_2, …, x_n) = (x_1 + … + x_n)!/(x_1 * … * x_n)!. We can attempt to do so using a similar approach as in part 1 - by inducting on x_1,…, x_n.

In our base case, let x_1 = 0.
Then we have, F(0, x_2, …, x_n), which is equivalent to F(x_2, …, x_n) which by our inductive hypothesis is (x_2 + … + x_n)! / (x_2! * … * x_n!), as we desired to show. The cases for x_i = 0, for i = 2…n use similar reasoning.

Now, assume that the equalities for all of F(x_1 - 1, x_2, …, x_n), F(x_1, x_2 - 1, …, x_n), …, F(x_1, x_2, …, x_n -1) are true. We know that F(x_1, x_2, …, x_n) = F(x_1 - 1, x_2, …, x_n), + F(x_1, x_2 - 1, …, x_n) +  … + F(x_1, x_2, …, x_n -1), so we have:

F(x_1, x_2, …, x_n) = (x_1 + x_2 + … + x_n - 1)! / ((x_1 - 1)! * x_2! *… * x_n!) + (x_1 + x_2 + … + x_n - 1)! / (x_1! * (x_2 - 1)! *… * x_n!) + … + (x_1 + x_2 + … + x_n - 1)! / (x_1! * x_2! *… * (x_n - 1)!) =

(x_1 + x_2 + … + x_n- 1)! * sum_{i=1..n) ( 1 / x_1 * x_2 * … x_{i-1} * x_{i+1} * … x_n * (x_1 - 1)! * (x_2 - 1)! * … * (x_n - 1)! ) =

(x_1 + x_2 + … + x_n - 1)! / (x_1 - 1)! * (x_2 - 1)!  * … (x_n - 1)! * sum_{i=1..n} ( 1 / x_1 * x_2 * … x_{i-1} * x_{i+1} * … x_n ) = 

(x_1 + x_2 + … + x_n - 1)! / (x_1 - 1)! * (x_2 - 1)!  * … (x_n - 1)! * ( x_1 + x_2 + … + x_n / x_1*x_2*…*x_n ) =

(x_1 + … + x_n)! / (x_1! * … * x_k!) as desired. Therefore, the equality holds for F(x_1, x_2, …, x_n), which further implies that the equality holds for all k >= 2 as we wanted to show.


PART 4:

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:

PART 5:

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:=NuWalks(m-1,n):
W2:=NuWalks(m,n-1):

W1+W2:
end:

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