# Please do not post homework
# Ravali Bommanaboina, 9/13/2020, HW2

# Question 1--------------------------------------------------------------------
# The total number of walks from [0,0,0] to [a,b,c] in the 3D "Manhattan lattice"
# we can represent a step in the first dimension by xi where i=1..a
# we can represent a step in the second dimension by yj where j=1..b
# we can represent a step in the third dimension by zk where k=1..c
# The total number of steps can be represented by a+b+c to determine the total number of paths
# we must find the total number of combinations of steps (a+b+c)
# if we take one step in an arbitrary direction then we will have a+b+c-1 more steps to choose from
# if two steps are taken then we will have a+b+c-2 more steps to choose from
# so the total number of combinations of a+b+c steps can be represented like this
# (a+b+c)*(a+b+c-1)*(a+b+c-2)*....*(1)
# this is equivalent to (a+b+c)!
# however this will overestimate the number of walks
# lets say path1 = [x1,..,xa,y1,...,yb,z1,...,zc]
# lets say path2 = [x2,x1,x3,...,xa,y1,...,yb,z1,...,zc]
# both of these paths are counted by (a+b+c)! but both take a steps in the first dimension, b steps in the second dimension, and c steps in the third dimension
# so we can't count both paths because they are the same
# we must only count unique paths from [0,0,0] to [a,b,c]
# the number of ways we can arrange [x1,...,xa] is a! because once we take one step in the first dimension then we have a-1 more steps to choose from
# another way to write it is (a)(a-1)*...*(1)
# the number of ways we can arrange [y1,...,yb] is b!
# the number of ways we can arrange [z1,...,zc] is c!
# so a!*b!*c! gives us the number of duplicate arrangements of xi,yj, and zk because for each unique arrangement of [x1,...,xa] there are b!*c! more combinations of steps to make
# this is why we must divide out the duplicates from the total number of combinations and we get this formula
# (a+b+c)! / (a!*b!*c!)

# Question 2--------------------------------------------------------------------

# 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) because the number of walks calculates the number of combinations of k numbers (or letters)
# that can occur. So in this case each letter can correlate to a number 1...k.
#for example the number of words in the alphabet for this sequence aabb is the same as computing NuWalks(2,2)=6 where k=2
# there are two dimension and each letter appears twice.
# To calculate the number of walks we can do
#(a[1]+...+a[k])!/(a[1]! * ... * a[k]!)
# and the same formula can be applied to the number of words in the alphabet where a[i] is the number of times
# the letter i shows up (i=1..k)



# Question 3--------------------------------------------------------------------
# if theyre are k-dimensions then we want the number of walks from [0,0,...,0] to [a[1],...,a[k]]
# where a[i] i=1..k represents the number of steps in a particular dimension
# so the total number of steps can be represented by a[1]+...+a[k]
# and (a[1]+...+a[k])! represents the total number of combinations of steps from [0,0,...,0] to [a[1],...,a[k]]
# like in question 1 we must now divide out the duplicates
# the number of duplicate paths can be represented by a[1]! * ... * a[k]!
# so we get this formula
# (a[1]+...+a[k])!/(a[1]! * ... * a[k]!)

# Question 4--------------------------------------------------------------------

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

if m<0 or n<0 then
 RETURN({}):
fi:


if m=0 and n=0 then
 RETURN({[]}):
fi:
check:=[m-1,n];
W1:={};
W2:={};
if(member(check,S)=false) then
	W1:=RestrictedWalks(m-1,n,S):
fi:
check:=[m,n-1];
if(member(check,S)=false) then
	W2:=RestrictedWalks(m,n-1,S):
fi:

{seq([op(w1),E],w1 in W1), seq([op(w2),N],w2 in W2)  }:

end:

# Question 5--------------------------------------------------------------------

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

if m<0 or n<0 then
 RETURN(0):
fi:


if m=0 and n=0 then
 RETURN(1):
fi:
W1:=0;
W2:=0;
check:=[m-1,n];
if member(check,S)=false then
	W1:=RestrictedNuWalks(m-1,n,S):
fi:
check:=[m,n-1];
if member(check,S)=false then
	W2:=RestrictedNuWalks(m,n-1,S):
fi:

W1+W2:
end:

# RestrictedNuWalks(50,50,{seq([i,i],i=1..50)}) = 1019104490359234276109217144