# Please do not post homework
# Hari Amoor, 09/13/2020, Assignment 2

NOTE TO GRADER: Some of the harder-to-verbalize formulas are specified in unrendered LaTeX. Hopefully, this is easy to understand -- if not, please email me back at amoor.hari@rutgers.edu if possible so I can provide clarification. In any case, I will ask the instructor for permission to submit all future assignments in a PDF rendered via LaTeX.

1. Give a full proof that the number of walks from [0, 0, 0] to [a, b, c] in the 3D Manhattan lattice is given by the explicit formula F(a, b, c) = (a + b + c)!/(a! * b! * c!).

Claim: As supplied.

Proof:

It is explained in (2) that the set of walks from [0, ..., 0] to [a_{1}, ..., a_{k}] is isomorphic to words in a given k-letter alphabet with the i-th letter showing up i times. Thus, it suffices to quantify the the number of such words for some given k.

We show in (3) that the number of such words, for some k, is equal (specified in LaTeX format) to ${\sum_{i=1}^{k} a_{i} \choose a_{1}, \ldots, a_{k}}$. Thus, for k = 3, it follows that ${a + b + c \choose a, b, c}$ is equal to F(a, b, c) as given.

QED

2. Explain, in plain English why the number of walks in the k-dimensional Manhattan lattice from [0,0...,0] to [a[1], ..., a[k]] is 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).

We describe an isomorphism between the walks of the specified form in the k-dimensional Manhattan lattice and the words in the given "alphabet".

Suppose that there is a positive direction P and a negative direction N for each dimension in the Manhattan lattice. We provide the following description of the isomorphism.

Let W = w_{1}, ..., w_{n} be some word of the supplied format. Consider a "cursor" that starts at [0, ..., 0] in the lattice. For each letter w_{i} in W, consider the value j s.t. w_{i} = a_{j}, where a_{j} is the j-th letter in the alphabet. Iterate through the w_{i} and, in each step, move the cursor in direction P in the j-th dimension of the lattice.

It is clear that, on completion of the computation, the cursor would be at the point [a[1], ..., a[k]] in the lattice. Furthermore, we observe that each unique such W would lead to a unique walk in the lattice -- this proves injectivity. Finally, we observe that we can also do the reverse computation, i.e. construct W for an arbitrary walk -- this proves surjectivity.

Thus, the isomorphism holds.

3.  State 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) and prove it completely.

Claim: The supplied number of words is equal to $F(A, k) = {\sum_{i=1}^{k} a_{i} \choose a_{1}, \ldots, a_{k}} = (a_{1} + ... + a_{k})!/(a_{1}! * ... * a_{k}!)$.

Proof:

We know that each word is of length $n = \sum_{i=1}^{k} i = i(i + 1)/2$. From this, it follows combinatorially that number of ways you can permute the letters is n! -- thus, there are at least n! different words.

However, we note that some of the permutations are duplicates. Particularly, for each a_{i}, there are i! duplicates. Thus, there are combinatorially $\prod_{i=1}^{k} a_{i}!$ duplicates.

Hence, the number of words of the specified format constructed from some k-length alphabet A is equal to F(A, k) as given.

QED

4. Generalize WALKS(m, n) to RestrictedWalks(m, n, S) as given.

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

p:=[m,n]:

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

5. Use RestrictedWalks(m, n, S) to formulate NuWalks(m, n).

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

p:=[m,n]:

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