#its ok to post
#TaerimKim,10/23/2020,Assignment 11

#############################################################################

#1. We can directly use the given Function Snk to seperate 11 dolls(respectively 1 to 11 as distinct numbers)
# into 5 parts. Similar case we did in the lecture. So,

Snk(11,5)
246730

#If we want to do this with any number of towers.
#this is same as saying for 11 dolls there can be as little as 1 tower to as many as 11 towers to arrange 11 dolls
#So meaning we need to add starting from Snk(11,1) to Snk(11,11)
#This is the same logic for the formula Bell1

Bell1(11)
678570


###################################################################################


#2.

xn:=proc(x,n) local i;
mul(x-(i-1),i=1..n);
end;

Axn:=proc(x,n) local k; #the given Sum statement doesnot expand. So, change to add instead
Expand(add(Snk(n,k)*xn(x,k),k=0..n));
end;

#lets check
seq(Axn(x, i), i = 1 .. 20)
x, x^2, x^3, x^4, x^5, x^6, x^7, x^8, x^9, x^10, x^11, x^12, x^13, x^14, x^15, x^16, x^17, x^18, x^19, x^20

#so it seems that Axn(x,i) gives x^i as a product
#So formula for Axn(x,n) = x^n for n>=0

###################################################################################

#3. To think it very simple, its like adding one more doll to the existing russian dolls of n-1.
#the new doll can be a "tower" itself and does not effect any other towers, just adding one more possibility into the count.
#This is also mathematically same as c(n-1,k-1) = 1 

#now, lets say the new doll should be inserted in the existing towers. now this becomes the situation of n-1 object with k cycles.
#And the position of this new doll can be placed into (n-1) different position within c(n-1,k) possible choices.
#So, from the assumptions into the two different cases, we know that they do not overlap each other(mutually exclusive).
#So, total is the sum of these two case giving
#c(n,k) = c(n-1,k-1) + (n-1)c(n-1,k) Q.E.D


#####################################################################################


#4. 

cnk:=proc(n,k)
option remember:

#the first condition is identical

if n=1 then
if k=1 then
return(1);
else
return(0);
fi;
fi;

#we use what we have learned from #3.

cnk(n-1,k-1)+(n-1)cnk(n-1,k);

end;

#lets check, cnk(3,2) is 3 like we know in the lecture
cnk(3, 2)
3
#true

####################################################################################

#5.just by looking at the formula it seems that it is a permutation formula defined by stirling number of first kind.
#lets find out

ho:=proc(n) local k;
factor(add(cnk(n, k)*x^k, k = 1 .. n));
end;

seq(ho(i),i=1..5)
x, x*(x + 1), x*(x + 2)*(x + 1), x*(x + 3)*(x + 2)*(x + 1), x*(x + 4)*(x + 3)*(x + 2)*(x + 1)

#looking at the result, my initial guess is wrong. this is stirling number defiinition by the rising factorials..

#So, the explicit formula for this should be x*(x+1)*...*(x+n-1)


#######################################################################################

#6. With a little help from internet, I will give a proof by induction.

#1) we assume that when n=l for arbitary number l, Sum(cnk(l,k)x^k,k=1..l) = x(x+1)...(x+l-1) <- we assume this is true
#
#2) now we have to prove that it is also true for n=l+1
#
#One useful notation we can use here is the #3 (c(n,k) = c(n-1,k-1) + (n-1)c(n-1,k))
#because this can be modified as sum(c(n,k)x^k,k=1..n) = sum(c(n-1,k-1)x^k,k=1..n)+(n-1) sum(c(n-1,k)x^k,k=1..n)
#
#so, Sum(cnk(l+1,k)x^k,k=1..l+1) = Sum(cnk(l,k-1)x^k,k=1..l+1)+(l+1-1)Sum(cnk(l,k)x^k,k=1..l) <- same as 1)
#=Sum(cnk(l,k-1)x^k,k=1..l+1)+ l * (x(x+1)...(x+l-1))
#= x*Sum(cnk(l,k-1)x^(k-1),k=1..l+1) + l * (x(x+1)...(x+l-1)) <- (Sum(cnk(l,k-1)x^(k-1),k=1..l+1) = Sum(cnk(l,k)x^k,k=1..l) = x(x+1)...(x+l-1))
#= x*((x(x+1)...(x+l-1)) + l * (x(x+1)...(x+l-1))
#=(x+l) * x(x+1)...(x+l-1) = x(x+1)...(x+l-1)(x+l)
#
#so, ultimately,
#Sum(cnk(l+1,k)x^k,k=1..l+1) = x(x+1)...(x+l-1)(x+((l+1)-1) which is proven

#so, By 1) and 2) proof by induction is complete
#meaning our initial statement of Sum(cnk(n,k)x^k,k=1..n) = x(x+1)...(x+n-1) is true by induction Q.E.D