#OK to post homework
#Tianyi Liu,Sept 20, Assignment 2
1.
Using mathematics induction to prove the formula F(a,b,c)=(a+b+c)!/(a!*b!*c!)

Base step: 
When a,b=0, F(a,b,c)=1!/1=1
When a,c=0, F(a,b,c)=1!/1=1
When c,b=0, F(a,b,c)=1!/1=1
Inductive hypothesis:
Assume it is true up to a-1,b-1 or c-1
F(a,b,c-1)=(a+b+c-1)!/(a!*b!*(c-1)!)
F(a,b-1,c)=(a+b-1+c)!/(a!*(b-1)!*c!)
F(a-1,b,c)=(a-1+b+c)!/((a-1)!*b!*c!)
Inductive step:
F(a,b,c)=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-1+c)!/(a!*(b-1)!*c!)+(a-1+b+c)!/((a-1)!*b!*c!)
=(a+b+c-1)!*(1/(a*(a-1)!*b*(b-1)!*(c-1)!)+1/(a*(a-1)!*(b-1)!*c*(c-1)!)+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)!)*((a+b+c)/(a*b*c))
=(a+b+c)!/(a!*b!*c!)
The proposition is proved

2.We can think of the k dimensional walks as how many steps it requires to get to a[i] where i=1...k in the ith dimension.
We do not allow negative steps which makes the walk can only go positively, so the number of steps to take is fixed. The 
number of letter i to show up a[i] times equals to the number of steps it takes to get to a[i] in ith dimension. The number 
of letters matches with the number of dimensions. So number of walks can be thought of as another form of words in the alphabet. 

3.
(a[1]+a[2]+...+a[k])!/(a[1]!a[2]!...a[k]!)
Using mathematics induction to prove the formula
Base step, we have proved the first three dimension in problem 1.
Inductive hypothesis:
Assume it is true up to a-1,b-1,c-1 or k-1
F(a-1,b,c...,k)=(a-1+b+c+...k)!/((a-1)!*b!*...k!)
...
F(a,b,c...,k-1)=(a+b+c+...k-1)!/(a!*b!*...(k-1)!)
Inductive step:
F(a,b,c...,k)=F(a-1,b,c...,k)+...F(a,b,c...,k-1)
=(a-1+b+c...k)!/((a-1)!*b!*c!...k!)+...(a+b+c...k-1)!/(a!*b!*c!...(k-1!))
=(a+b+c...k-1)!*(1/((a-1)!*b*(b-1)!*c*(c-1)!...k*(k-1)!)+...1/(a*(a-1)!*b*(b-1)!*c*(c-1)!...(k-1)!))
=(a+b+c...k-1)!/((a-1)!*(b-1)!*(c-1)!*...(k-1)!)*((a+b+c...k)/(a*b*c...k))
=(a+b+c...k)!/(a!*b!*c!...k!)
The proposition is proved

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

if member([m,n],S) then
 RETURN({}):
fi:

if m<0 or n<0 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:

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

if member([m,n],S) then
RETURN(0);
fi:

if m<0 or n<0 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: