#Ok to post homework
#Tifany Tong, October 18th, 2020, HW #11

# Question 1:

# You can assemble 11 Russian dolls of different sizes into 5 different "towers" in Snk(11,5) = 246730 ways.
# To get the number of ways in which you can assemble the 11 Russian dolls of different sizes into any number
# of towers you do is to do sum up Snk(11,k) where k goes from 1 to n. This is also the 11th Bell Number, 
# which is 678570. 

# Question 2

xn := proc(x, n) local i,ans:
product(x-i,i=0..n-1):
end:

Axn := proc(x, n) local i, k:
add(expand(Snk(n, k)*xn(x, n)), k = 0 .. n):
end:

#Axn(x, 1) = x
#Axn(x, 2) = x^2
#Axn(x, 3) = x^3
# .....
#Axn(x,19) = x^19
#Axn(x,20) = x^20

#Axn(x,n) appears to equal x^n. 

# Question 3:
# c(n,k)=c(n-1,k-1)+ (n-1)*c(n-1,k)

# We will consider a proof by induction, so we should prove that c(n-1,k) = n*c(n-1,k) + c(n-1,k-1).
# Let's look at forming a permutation of n object from a permutation of n-1 objects by adding 
# a new object. There are 2 cases to consider here:

# There are exactly two ways in which this can be accomplished. We could do this by forming a singleton cycle, leaving the newest object on its own,
# to add to the already present cycles. To count the number of already present cycles for n-1 objects and k-1 cycles.
# This singleton cycle increases the number of cycles by 1, so this accounts for the c(n-1,k-1) term in the 
# recurrence formula. 

# We could also insert the new object into one of the existing cycles. To form a new permutation of n objects and k cycles,
# we'd have to insert the new object into one of the k existing cycles. Then, there are n-1 ways to perform this insertion
# as we can insert the new object immediately after any of the n-1 already existing terms. 
# This explains the n * c(n,k) term of the recurrence relation. 

#These two cases include all possibilities, so the recurrence relation follows.


# Question 4
cnk := proc(n, k) option remember:
if n = 0 and k = 0 then return 1: fi:
if n = 0 or k = 0 then return 0: fi:
cnk(n - 1, k - 1) + (n - 1)*cnk(n - 1, k): 
end:


# Question 5
# x(x+1)(x+2)...(x+n-1) is the explicit form