# OK to post homework
# Michael Saunders, 9/13/2020, Homework 2
#


# load packages
#
with(combinat):


# 1.0.0
#
# 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 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!)
#
# It is known that the length of any path between two points on a Cartesian plane (give an agent only moves one step at a time--
# moving exactly parallel to one axis--and each step has the same value of 1) is the same. 
# We are attempting to calculate the number of various paths (of the same length) from one point [0,0,0] to another [a,b,c].
# No matter the path, eventually the values of A, B, and C will always be consistent. The agent must
# (no matter the path) inevitably move 'a' paces East, 'b' paces North, and 'c' paces in whatever direction is perpendicular to
# the two-axis East and North (let's call this direction "In"; visualize looking at an (x,y) 2D-plane, the "In" direction would
# go in to the page (along the 'z' axis). 
# Anyway, we can calculate the values for A, B, and C by taking the difference between the destination(n) and the start(n)
# for n = {a, b, c}:

A := a - 0:
B := b - 0:
C := c - 0:
LENGTH_OF_A_WALK := (A + B + C):

# "Walks" can be considered to be the set of permutations of lists in the following format:
# { [1,0,0], [0,1,0], [0,0,1], ... [0,1,0] ... } untl eventually the target [a,b.c] is reached.
# So, so count the number of Walks, we count the number of different permutations of that set of lists.
# The number of permutations of the elements in a list is given by the known formula:

P := LENGTH_OF_A_WALK!:
P := (A+B+C)!:

# However, we can't leave it at that. We must take into consideration the fact that a step in one direction is indistinguishable
# from a completely different step in the same direction. To account for the indistinguishable steps, we adjust the formula as such:

# P := (A + B + C)!/(A! * B! * C!): # Proof.


# 2.0.0
# 
# 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).
#
# The number of walks in the k-th dimensional Manhattan lattice from [0,0,0] to [a[i], ..., a[k]] is the number of permutations
# of the set consisting of values for [a[i] = i, a[i + 1] = (i + 1), ..., a[k] = k} for i = 1, 2, ..., k.
# Considering the equivalency of the number of walks as mentioned and the number of words in the "alphabet" {1, ,2 ,3, ..., k}
# with the letter of showing up exactly a[i] times for i = {1 .. k}: 
# The number of words in the alphabet mentioned is the number of permutations of the set consisting of elements {i, i+1, ... i=k}.
# You will find those two equations to be equivalent. 


# 3.0.0
#
# 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.

# Proof:


print("------- 3.0.0 Proof -------"):
# Let B_i be the set of of all words made op of i letters. Each list in the set B_i represents a word.

B_1 := [[1]]:
B_2 := [[1,2,2], [2,1,2], [2,2,1]]:
# etc... it will be too laborious to manually write them out from B_3..B_k.

# But we can already see that the number of i-letter words from the alphabet {1,2,...,k} with the ith-letter repeating i times, is equal
# to the number of permutations of the list [1,2,3,...,k]. Let P be the set of all permutations of that list.
# 
# |P| := (1 + 2 + 3 + ... + k)! / (1! * 2! * 3! * ... * k!)
# 
# I will write a procedure Words(k) to construct the set of all words with the given conditions from the given alphabet.
# Then I will write a procedure NumWords(k) to compute the formula for the size of set P (written above).
# Finally, I will compare nops(Words(k)) to NumWords(k) to prove the formula is accurate. 

Words := proc(k) local P:
    P := [seq(i$(seq(i..i)), i=1..k)]:
    RETURN(permute(P)):
end proc:

NumWords := proc(k) local numerator, denominator, i, j:
    # loop generates (1 + 2 + ... + k)
    numerator := 0:
    for i from 1 to k do
        numerator := numerator + i:
    end do:
    # loop generates (1! * 2! * 3! * ... * k!)
    denominator := 1:
    for j from 1 to k do
        denominator := denominator * j!:
    end do:
    RETURN((numerator!)/denominator):
end proc:
# Run Words(n) for n=1..2 and compare to B_1 and B_2 respectively.
b_1 := Words(1):
b_2 := Words(2):
print("b_1", b_1):
print("B_1", B_1):
print("b_2", b_2):
print("B_2", B_2):
print("is my procedure correct? evalb(b_1 = B_1 and b_2 = B_2)"):
evalb(b_1 = B_1 and b_2 = B_2);
print("Comparing nops(Words(i)) to NumWords(i) to prove formula"):
# loop 
for i from 1 to 4 do
    a := nops(Words(i)):
    b := NumWords(i):
    print(i,a, b, evalb(a = b)):
end do:

# NumWords(i) is apparently exponential in growth as i increases.
# nops(Words(i)) will be too much for my PC to evaluate as i >= 5.
# But let the evaluation and comparison for i=1..4 PROVE the following formula for computing the number of i-letter
# words from the alphabet {1, 2, ..., k} with the ith-letter repeating i times:
# (1 + 2 + 3 + ... + k)! / (1! * 2! * 3! * ... * k!


# 4.0.0
#
# Generalize the procedure Walks(m.n) from Maple Code from Lecture 1 (M1.mw) to write procedure 
# RestrictedWalks(m,n,S) that takes non-negative integers m and n, as well as a finite set of lattice points S.
# RestrictedWalks(m,n,S) outputs the walks from [0,0] to [m,n] that never visits the points defined by S.

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):
    RETURN({seq([op(w1),E],w1 in W1), seq([op(w2),N],w2 in W2)  }):
end proc:


# Test RestrictedWalks(m,n,S)

RestrictedWalks(2,2,{[1,1]});

# 5.0.0
#
# Generalize procedure NuWalks(m.n) from Maple Code from Lecture 1 (M1.mw) to write procedure
# RestrictedNuWalks(m,n,S) that takes two non-negative integers m,n, and a finite set of lattice point S.
# RestrictedNuWalks(m.n.S) outputs the number of walks from [0,0] to [m,n] that never vists the points defined by S.

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 proc:

print("Test RestrictedNuWalks(m.n.S)"):
T := RestrictedNuWalks(2,2,{[1,1]}):
T;

# 5.1.0
#
print("What is RestrictedNuWalks(50,50,{seq([i,i],i=1..50)})?"):
RestrictedNuWalks(50,50,{seq([i,i],i=1..50)});