> #Weiji Zheng, 09/18/20, Assignment 2
;
> #OK to post homework
;
> 
;
> #Q1
;
> 
;
> #Want to prove:  F(a, b, c) = (a+b+c)!/(a!*b!*c!)
;
> #BY THE INDUCTIVE HYPOTHESIS WE ASSUME
;
> #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!)
;
> #F(a, b, c-1)= (a+b+c-1)!/(a!b!(c-1)!)
;
> #Hence
;
> #F(a, b, c) = F(a-1, b, c) + F(a, b-1, c) + F(a, b, c-1)
;
> #=(a+b+c-1)!/((a-1)!(b-1)!(c-1)!)((a+b+c)/abc)
;
> #=(a+b+c)!/(a!b!c!)
;
> #QED!!!
;
> 
;
> #Q2
;
> 
;
> #Because we can consider the situation (pick a direction  in a k-d space) samely as the situation (pick a word from {1,2,......k}). We can even more imagine a direction just like a letter to be chosen from the alphanet.
;
> 
;
> #Q3
;
> 
;
> #With the help with the original formula and Q1, we can easily define
;
> #The formula is (a[1] + a[2] + a[3] + ... + a[k])!/(a[1]!*a[2]!*a[3]!* ... *a[k]!).
;
> #Then we start to prove it.
;
> #we make N denotes the total number of letters
;
> #then wen should
;
> #choose a[1] from N letters
;
> #choose a[2] from N-a[1] letters
;
> #choose a[3] from N-a[1]-a[2] letters
;
> #.
;
> #.
;
> #.
;
> #choose a[k] from (N-a[1]-a[2]-a[3]-...-a[k-1]=)a[k] letters
;
> #Then we have
;
> #n!/((n-a[1])!*a[1]!) * (n-a[1])!/((n-a[1]-a[2])!*a[2]!) * (n-a[1]-a[2])!/((n-a[1]-a[2]-a[3])!*a[3]!)... * (n-a[1]-a[2]-...-a[k-1])!/((n-a[1]-a[2]-a[3]-...-a[k])!*a[k]!)
;
> #Simplified to be
;
> #n!/(a[1]!*a[2]!*a[3]!*...*a[k]!) = (a[1] + a[2] + a[3] + ... + a[k])!/(a[1]!*a[2]!*a[3]!* ... *a[k]!)
;
> 
;
> #Q4
;
> 
;
> RestrictedWalks := proc(m,n,S) local W1,W2,w1,w2:
> option remember:
> 
> if m<0 or n<0 or [m, n] in S then
>  RETURN({}):
> fi:
> 
> 
> if m = 0 and n = 0 then
>  RETURN({[]}):
> fi:
> 
> 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:
> #test
;
> RestrictedWalks(2,2,{[1,1]});
{[E, E, N, N], [N, N, E, E]}
;
> RestrictedWalks(3,2,{[1,1]});
{[E, E, E, N, N], [E, E, N, E, N], [E, E, N, N, E], [N, N, E, E, E]}
;
> RestrictedWalks(1,1,{[1,1]});
{}
;
> 
;
> #Q5
;
> 
;
> RestrictedNuWalks := proc(m,n,S) local W1,W2,w1,w2:
> option remember:
> 
> if m<0 or n<0 or [m, n] in S then
>  RETURN(0):
> fi:
> 
> 
> if m = 0 and n = 0 then
>  RETURN(1):
> fi:
> 
> W1:=RestrictedNuWalks(m-1,n,S):
> W2:=RestrictedNuWalks(m,n-1,S):
> 
> W1+W2:
> end:
> #TEST
;
> RestrictedWalks(2,2,{[1,1]});
{[E, E, N, N], [N, N, E, E]}
;
> RestrictedNuWalks(2,2,{[1,1]});
2
;
> RestrictedWalks(3,2,{[1,1]});
{[E, E, E, N, N], [E, E, N, E, N], [E, E, N, N, E], [N, N, E, E, E]}
;
> RestrictedNuWalks(3,2,{[1,1]});
4
;
> #Now Solve
;
> RestrictedWalks(50,50,{seq([i,i],i=1..50)});
{}
;
> RestrictedNuWalks(50,50,{seq([i,i],i=1..50)});
0
;
> #The Answer is Zero Way
;