# OK to post homework
# Hari Amoor, October 18th, 2020, HW #11

# Question 1

# You can assemble 11 dolls of different sizes into 5 different towers in Snk(11,5) = 246730 ways.
# In order to compute the number of ways in which you can assemble the dools into n towers, you simply compute
# sum(Snk(11, i), i=1..n). This is to the 11th Bell Number, which is 678570

# Question 2

xn := proc(x, n) local i:
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

# We obtain c(n,k) = c(n-1,k-1) + (n-1) * c(n-1,k)

# Consider the following proof with mathematical induction.

# The following are distinct cases:

# First, form 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.

# First, you can form a singleton cycle and leave it on its own for addition to the set of existing cycles. In order to enumerate
# the existing cycles for n-1 objects, apply the recurrence c(n-1, k-1).

# Second, you can insert the new object into one of the existing cycles. To form a new permutation of n objects and k cycles,
# insert the new object into any of the k existing cycles. Then, there are n-1 ways to perform this insertion,
# seeing as we can insert the new object immediately after any of the n-1 existing terms. From this, we obtain n * c(n-1,k) cycles. 

# These cases are exhaustive, 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

# The explicit form is x(x+1)(x+2)...(x+n-1).