# OK to post hw
# Michael Yen, 9/13/20, Assignment 2

# 1. 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 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!)

# Let G(a,b,c) be the RHS, namely G(a,b,c):=(a+b+c)!/(a!*b!*c!)
# We need to prove that for every a, b, and c
# F(a,b,c) is the same as G(a,b,c)
# Proof: Induction on a+b+c
# if a=0 F(0,b,c)=(b+c)!/(b!c!) (we know this from the 2D Manhattan lattice formula proved in 2nd
# lecture)
# if b=0 F(a,0,c)=(a+c)!/(a!c!)
# if c=0 F(a,b,0)=(a+b)!/(a!b!)
# By the Inductive Hypothesis we assume
# F(a,b,c-1)=(a+b+c-1)!/(a!b!(c-1)!)
# F(a-1,b,c)=(a+b+c-1)!/((a-1)!b!c!)
# F(a,b-1,c)=(a+b+c-1)!/(a!(b-1)!c!)
# Hence
# F(a,b)=F(a,b,c-1)+F(a,b-1,c)+F(a-1,b,c)=(a+b+c-1)!/(a!b!(c-1)!)+(a+b+c-1)!/(a!(b-1)!c!)+(a+b+c-1)!/((a-1)!b!c!)
# (a+b+c-1)!/(a(a-1)!b(b-1)!(c-1)!)+(a+b+c-1)!/(a(a-1)!(b-1)!c(c-1)!)+(a+b+c-1)!/((a-1)!b(b-1)!c(c-1)!)
# (a+b+c-1)!/((a-1)!(b-1)!(c-1)!)(1/ab+1/ac+1/bc)
# (a+b+c-1)!/((a-1)!(b-1)!(c-1)!)((c+b+a)/abc)
# (a+b+c!)/(a!b!c!) 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)

# In the alphabet problem you can map k to the number of dimensions and a[i] as how many "steps" you need to 
# take in the ith dimension. Example: for a six letter word with alphabet {A,O,P,T} and array a = {1,2,1,2}
# you can treat it like a 4-dimensional Manhattan lattice where you need to reach the point (1,2,1,2) from 
# (0,0,0,0). In both problems you are deciding "when" to put your a[i] moves in a specific dimension / "when" 
# to place some letter that you have a[i] copies of. Additionally, they can both be mapped onto the
# rearrangement of a word problem.

# 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

# The formula would be same as the Manhattan Lattice problem, so (a[1]+a[2]+...+a[k])!/(a[1]!a[2]!...a[k]!)
# Proof: map onto the rearrangement of a word problem
# We know from the 2nd lecture that the number of rearrangements of a word with alphabet of length l with l[1]
# first letters, l[2] second letters, ... l[k] kth letters, is (l[1]+l[2]+...+l[k])!/l[1]!l[2]!...l[k]!). We can 
# map the k dimensions from the number of word problem onto the rearrangement problem, and do the same with the 
# array a onto array l. Thus it is proved that the formula should be the same.

# 4. [A bit of a challenge] Generalize procedure
# Walks(m,n)
# from the Maple Code for Lecture 1 to write a procedure
# RestrictedWalks(m,n,S)
# that inputs non-negative integers, m and n, as before, but also a finite set of lattice points S, and outputs 
# the SET of walks from [0,0] to [m,n] (with the same fundamental steps as before, i.e. [1,0] (E) and [0,1] (N))
# that NEVER visit the members of S.
# For example
# RestrictedWalks(2,2,{[1,1]});
# should output {[E,E,N,N],[N,N,E,E]}

# To do this you should find all the walks from (0,0) to (m,n). Keep these, maybe call it set A. Then find all the 
# walks from (0,0) to all the points in S, and all the walks from all the points in S to (m,n), and combine them 
# and put them in a set B. These are all the walks that go through all the points in S. Finally take the set 
# difference A-B and you have the answer. Unfortunately, I don't know how to put this into Maple. :(

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

end:

# 5. [A bit of a challenge] Generalize procedure
# NuWalks(m,n)
# from the Maple Code for Lecture 1 to write a procedure
# RestrictedNuWalks(m,n,S)
# that inputs non-negative integers, m and n, as before, but also a finite set of lattice points S, and outputs
# the NUMBER of walks from [0,0] to [m,n] (with the same fundamental steps as before, i.e. [1,0] (E) and [0,1] 
# (N)) that NEVER visit the members of S.
# For example
# RestrictedNuWalks(2,2,{[1,1]});
# should output 2.
# What is
# RestrictedNuWalks(50,50,{seq([i,i],i=1..50)}); ? 
# Not sure how to implement this into Maple either.

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

W1:=NuWalks(m,n);

end: