#OK to post homework
#William Wang, 10/14/2020, Assignment 11

#1.
#The number of ways you can assemble 11 Russian dolls of different sizes into 5 different "towers":
Snk(11, 5);
                             246730

#Into 1,2,3,4,5,... (any number of towers up to n):
Bell2(11);
                             678570


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

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

Axn(x, 1);
                               x

Axn(x, 2);
                                2
                               x 

Axn(x, 3);
                                3
                               x 

Axn(x, 20);
                               20
                              x  

#Axn(x,i) for i=1..20 is x, x^2, x^3, x^4, x^5, x^6, ... , x^20
#Formula for Axn(x,n) for any non-negative integer n can be given by x^(n).

#3.
#Splitting {1,...,n} into k cycles of two types: those which are 1-cycle and those that are not.
#If (n) is a 1-cycle, then the remaining cycles form a permutation of length n-1 with k-1 cycles, so there are binomial(n-1,k-1) of these.
#If (n) is not a 1 cycle, then (n) is a cycle of length >=2 , and removing (n) leaves a permutation of length n-1 with k cycles.
#Thus, c(n,k) = c(n-1,k-1)+(n-1)*c(n-1,k).

#4.
cnk := proc(n, k) option remember:
if n = 1 then
 if k = 1 then
  RETURN(1):
 else
  RETURN(0):
 end:
end:
cnk(n - 1, k - 1) + (n - 1)*cnk(n - 1, k):
end:

cnk(1, 1);
                               1

cnk(2, 1);
                               1

cnk(2, 2);
                               1

cnk(5, 5);
                               1

cnk(10, 6);
                             63273


#5.
cnk(5, 1)*x + cnk(5, 2)*x^2 + cnk(5, 3)*x^3 + cnk(5, 4)*x^4 + cnk(5, 5)*x^5;
                5       4       3       2       
               x  + 10 x  + 35 x  + 50 x  + 24 x

factor(%);
               x (x + 4) (x + 3) (x + 2) (x + 1)

#Explicit formula for Sum(c(n,k)*x^k,k=1..n): (x + n - 1)!/(x - 1)!