> #ok to post homework
;
> #Yifan Zhang 09/09/2020 Assignemnt2
;
> 
;
> #Q1. 
;
> #Theorem we need to prove that F(a, b, c):= (a+b+c)!/(a!*b!*c!)
;
> 
;
> # Let G(a1,a2,a3) be the RHS, namely G(a1,a2,a3) := (a1+a2+a3)!/(a1!*a2!*a3!)
;
> #We need to prove that for every a1, a2, a3 in non-negative integer, F(a1,a2,a3) = G(a1,a2,a3).
;
> #Proof: By induction on a1, a2, a3
;
> #Base Case: If a1=0, F(0, a2, a3) = (a2+a3)!/(a2!*a3!), since a1 is 0, and we know for two variables, the number of ways from (0,0) to that point is (a2+a3)!/(a2!*a3!) , and since a1=0, then from the RHS, (0+a2+a3)!/(0!*a2!*a3!) => (a2+a3)!/(a2!*a3!), LHS=RHS. Similarly, for a2=0, and for a3=0,  we also have LHS=RHS. 
;
> #Induction Hypothesis: We assume that for a1, a2 and a3 is not 0, F(a1-1,a2,a3) = (a1-1+a2+a3)!/((a1-1)!*a2!*a3!); F(a1,a2-1,a3) = (a1+a2-1+a3)!/(a1!*(a2-1)!*a3!); F(a1,a2,a3-1) = (a1+a2+a3-1)!/(a1!*a2!*(a3-1)!); 
> #Hence, F(a1,a2,a3) = F(a1-1,a2,a3) + F(a1,a2-1,a3)+F(a1,a2,a3-1) = (a1-1+a2+a3)!/((a1-1)!*a2!*a3!)+(a1+a2-1+a3)!/(a1!*(a2-1)!*a3!)+(a1+a2+a3-1)!/(a1!*a2!*(a3-1)!) = (a1+a2+a3)!/(a1!*a2!*a3!)
;
> (a1-1+a2+a3)!/((a1-1)!*a2!*a3!)+(a1+a2-1+a3)!/(a1!*(a2-1)!*a3!)+(a1+a2+a3-1)!/(a1!*a2!*(a3-1)!) - (a1+a2+a3)!/(a1!*a2!*a3!);
(a1-1+a2+a3)!/(a1-1)!/a2!/a3!+(a1-1+a2+a3)!/a1!/(a2-1)!/a3!+(a1-1+a2+a3)!/a1!/
a2!/(a3-1)!-(a1+a2+a3)!/a1!/a2!/a3!

;
> simplify(%);
0

;
> #Hence we proved that F(a1,a2,a3) = (a+b+c)!/(a!*b!*c!) by induction. QED.
;
> 
;
> 
;
> #Q2. 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) 
;
> #Because these questions are similar. Both of them calculate the "number of ways" for a selected list. And we can use the same procedure. 
;
> 
;
> 
;
> #Q3. 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 is (a[1]+a[2]+...+a[k])!/(a[1]!*a[2]!*...*a[k]!). 
;
> #Prove:
> #Since there are k alphabets in a total of S = sum(a[i] times(i=1..k)), namely S.
;
> #numbcomb(k,1)*numbcomb(k-1,2)*numbcomb(k-(1+2),3)*numbcomb(k-(1+2+3),4)...*numbcomb(k(1+2+...+n-1),n)
;
> #which is equivalent to  (a[1]+a[2]+...+a[k])!/(a[1]!*a[2]!*...*a[k]!). 
;
> #For example, when k = 4,
;
> with(combinat);
[Chi, bell, binomial, cartprod, character, choose, composition, conjpart, 
decodepart, encodepart, eulerian1, eulerian2, fibonacci, firstcomb, firstpart,
firstperm, graycode, inttovec, lastcomb, lastpart, lastperm, multinomial, 
nextcomb, nextpart, nextperm, numbcomb, numbcomp, numbpart, numbperm, partition
, permute, powerset, prevcomb, prevpart, prevperm, randcomb, randpart, randperm
, rankcomb, rankperm, setpartition, stirling1, stirling2, subsets, unrankcomb,
unrankperm, vectoint]

;
> (numbcomb(10,1)*numbcomb(9,2)*numbcomb(7,3)*numbcomb(4,4)) = ((1+2+3+4)!/(1!*2!*3!*4!))
12600 = 12600

;
> 
;
> #Q4. 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]}
;
>  
;
> RestrictedWalks:=proc(m,n, V) 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 V=[m,n] then
> RETURN({});
> fi:
> 
> W1:=RestrictedWalks(m-1,n,V):
> W2:=RestrictedWalks(m,n-1,V):
> 
> {seq([op(w1),E],w1 in W1), seq([op(w2),N],w2 in W2)  }:
> 
> end:
> 
;
> RestrictedWalks(2,2,[1,1]);
{[E, E, N, N], [N, N, E, E]}

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

;
> 
;
> 
;
> #Q5. 
;
> #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]});
> 
;
> 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 [m,n]=S then
> RETURN(0)
> fi:
> 
> W1:= RestrictedNuWalks(m-1,n,S):
> W2:= RestrictedNuWalks(m,n-1,S):
> 
> W1+W2
> 
> end:
> 
;
> RestrictedNuWalks(2,2,[1,1]);
2

;
> RestrictedNuWalks(3,3,[0,1]);
10

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

;
> 
;