#OK to post homework
#TaerimKim,9/10/2020,Assignment 2\

#1. Theorem: F(a,b,c)=(a+b+c)!/(a!*b!*c!)
#Proof: Induction on a,b,c
#Let f(a,b,c) be the RHS, which is f(a,b,c):=(a+b+c)!/(a!*b!*c!)
#I am going to show that for every a,b,c
#If a=0, F(0,b,c) is equal to 2-dimensional Walk -> F(0,b,c)=(b+c)!/(b!*c!)
#This is same for other two possibilities
#F(a,0,c)=(a+c)!/(a!*c!) : F(a,b,0)=(a+b)!/(a!*b!):
#So by the inductive hypotheses we assume
#F(a-1,b,c) = (a-1+b+c)!/((a-1)!*b!*c!)
#F(a,b-1,c) = (a+b-1+c)!/(a!*(b-1)!*c!)
#F(a,b,c-1) = (a+b+c-1)!/(a!*b!*(c-1)!)
#Then, F(a,b,c)=F(a-1,b,c)+F(a,b-1,c)+F(a,b,c-1) = (a-1+b+c)!/((a-1)!*b!*c!)+(a+b-1+c)!/(a!*(b-1)!*c!)+(a+b+c-1)!/(a!*b!*(c-1)!)
#(a+b+c-1)!*(1/((a-1)!*b!*c!)+1/(a!*(b-1)!*c!)+1/(a!*b!*(c-1)!))
#(a+b+c-1)!*(a/(a*(a-1)!*b!*c!)+b/(a!*b*(b-1)!*c!)+c/(a!*b!*c*(c-1)!))
#(a+b+c-1)!*((a+b+c)/(a!*b!*c!))
#((a+b+c-1)!*(a+b+c))/(a!*b!*c!)
#(a+b+c)!/(a!*b!*c!) QED

#2.We can intuitively understand that multidimentional lattice corresponds with total inventory of alphabet from a to z.
#so, if there is no ave we can take, we can denote that in the alphabet as certain alphabet is not used.
#so, k-dimention is same as k-length as well as the # of ave in a[i] dimension can be understood as # of certain alphabet used.
#As a sum. the both cases indicates multinomial coefficient so they basically mean the same thing.

#3. Explicit Formula -> F(a,b,..,k) = (a+b+..+k)!/(a!*b!*..*k!) for kth alphabet
#Proof by mathematical Induction:
#1)Show true when k=3,3rd alphabet is c
#F(a,b,c) = (a+b+c)!/(a!*b!*c!) -> problem 2 proves it is correct
#2)assume it is true when k = n
#So,  F(a,b,..,n) = F(a-1,b,..,n)+F(a,b-1,..,n)+..+F(a,b,..,n-1) = (a+b+..+n)!/(a!*b!*..*n!)
F(a,b,..,n)-(F(a-1,b,..,n)+F(a,b-1,..,n)+..+F(a,b,..,n-1)) = 0
#3)Show it is true for k=n+1
#For k=n+1, F(a,b,..,n+1) = F(a-1,b,...,n,n+1)+F(a,b-1,..,n,n+1)+..+F(a,b,..,n-1,n+1)+F(a,b,..,n,n)
#(a+b+..+n+n+1-1)!/(1/((a-1)!*b!*..*(n+1)!)+1/(a!*(b-1)!*..*(n+1)!)+1/(a!*b!*..*n!*n!))
#(a+b+..+2n)!/((a+b+c+..+2n+1)/(a!*b!*..*n*(n+1)!))
#(a+b+..+n+n+1)!/(a!*b!*..*n*(n+1)!)
#As it is true for k=n+1, So our Assumption is True
#Our Formula is proven QED

#4. For this new condition, we can put it under our 'if' condition to return [] for the specific point indicated by S(S={[m.n]}) so that we rule out any set that contains the S point

> RestrictedWalks := proc(m, n, S) local W1, W2, w1, w2; option remember; if m < 0 or n < 0 then RETURN({}); end if; if S = {[m, n]} then RETURN({}); end if; if m = 0 and n = 0 then RETURN({[]}); end if; 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 proc;

> RestrictedWalks(2, 2, {[1, 1]});
                  {[E, E, N, N], [N, N, E, E]}

#5. Same principle is apply to Problem 5 as Problem 4 -> new condition on point S(S={[m.n]} -> Return (0))
> RestrictedNuWalks := proc(m, n, S) local W1, W2, w1, w2; option remember; if m < 0 or n < 0 then RETURN(0); end if; if S = {[m, n]} then RETURN(0); end if; if m = 0 and n = 0 then RETURN(1); end if; W1 := RestrictedNuWalks(m - 1, n, S); W2 := RestrictedNuWalks(m, n - 1, S); W1 + W2; end proc;

> RestrictedNuWalks(50, 50, {seq([i, i], i = 1 .. 50)});
                 100891344545564193334812497256
;
> RestrictedNuWalks(2, 2, {[1, 1]});
                               2