#OK to post homework
#Kent Mei, 10/18/20, Assignment 11

#---------------------------------
#Part 1

#Snk(11,5) = 246730 ways to partition 11 Russian dolls into 5 different "towers".
#Bell3(11) = 678570 ways to partition 11 Russian dolls into any number of towers.

#---------------------------------
#Part 2

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

Axn:=proc(x,n) local k: expand(add(Snk(n,k) * xn(x,k), k=0..n)): end proc:
#[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]
#The formula for Axn(x,n) for any non-negative integer n seems to be x^n.


#---------------------------------
#Part 3

#We wish to prove c(n,k)=c(n-1,k-1)+ (n-1)*c(n-1,k)

#Suppose we have a typical permutation (in cycle notation) of {1,...,n-1} and we want to insert an element n into the permutation. There are two possible cases:

#The first case is that there are k-1 cycles already of the elements from 1 to n-1 and in order to make a kth cycle, the element n forms a cycle with itself becoming a fixed point. The number of ways this could be accomplished would be the number of ways the n-1 elements could be put in k-1 cycles which is c(n-1,k-1).

#The second case is that there are k cycles of the n-1 elements. To get k cycles of n elements, we would need to insert n into one of the cycles. For any given cycle with j elements, there are j positions we can put n into to form unique cycles. Since n can be inserted into any cycle, it can be seen that there are n-1 positions we could place n into for any arbitrary permutation of n-1 elements with k cycles. Therefore, the number of possible permutations by inserting an element n into a permutation of {1,...,n-1} wiht k cycles can be determined by (n-1) * c(n-1,k).

#Since these are mutually exclusive events, we have that the total number of permutations of n elements with k cycles can be determined by c(n,k) = c(n-1,k-1) + (n-1)*c(n-1,k). 


#---------------------------------
#Part 4

cnk:=proc(n,k) option remember:
if n=1 then
 if k=1 then
  RETURN(1):
 else
  RETURN(0):
 fi:
fi:

cnk(n-1,k-1) + (n-1)*cnk(n-1,k):

end:


#---------------------------------
#Part 5

#Sum(c(n,k)*x^k, k = 1..n) = x * (x+1) * (x+2) * ... * (x+n-1)



#---------------------------------
#Part 6

#We proceed by induction.
#For the base case where n = 1, we have that Sum(c(n,k)*x^k, k = 1..n) = c(1,1)*x = x as desired.

#For the inductive hypothesis, we assume that for some natural number m > 1, Sum(c(m,k)*x^k, k = 1..m) = x * (x+1) * (x+2) * ... * (x+m-1).
#We need to show that Sum(c(m+1,k)*x^k, k = 1..m+1) = x * (x+1) * (x+2) * ... * (x+m).

#We know that:
#Sum(c(m+1,k)*x^k, k = 1..m+1) = Sum(c(m,k-1)*x^k, k = 1..m+1) + m * Sum(c(m,k)*x^k, k = 1..m+1)
#                              = x * Sum(c(m,k-1)*x^(k-1), k = 1..m+1) + m * (x*(x+1)*(x+2)*...*(x+m-1))
#                              = x * (x*(x+1)*(x+2)*...*(x+m-1)) + m * (x*(x+1)*(x+2)*...*(x+m-1)) 
#                              = (x + m) * (x*(x+1)*(x+2)*...*(x+m-1))
#                              = x*(x+1)*(x+2)*...*(x+m-1)*(x+m)

#Since we showed that Sum(c(m+1,k)*x^k, k = 1..m+1) = x * (x+1) * (x+2) * ... * (x+m), then by induction we have that 
#Sum(c(n,k)*x^k, k = 1..n) = x * (x+1) * (x+2) * ... * (x+n-1).

#Note that Sum(c(m,k)*x^k, k = 1..m+1) = Sum(c(m,k)*x^k, k = 1..m) since c(m,m+1) = 0.
#Also, note that Sum(c(m,k-1)*x^(k-1), k = 1..m+1) = Sum(c(m,k)*x^k, k = 1..m) since c(m,0) = 0.