#OK to post homework
#Michael Yen, 10/18/20, Assignment 11
#1)In how many ways can you assemble 11 Russian dolls of different sizes into 5 different "towers"? In how many ways 
#can you do it with any number of towers.

#Snk(11,5) = 246730
#Bell1(11) = 678570

#2)First Write a one-line procedure xn(x,n) that inputs a variable x and a non-negative integer n and outputs
#x*(x-1)*(x-2)*...*(x-(n-1))
#using this, write another one-line procedure, call it Axn(x,n) that inputs a variable x and a non-negative integer 
#n and outputs
#Sum(Snk(n,k)*xn(x,k),k=0..n)

xn:=proc(x,n) local k: option remember: 
mul(x-k, k=0..n-1):
end:

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

#[Don't forget to use the Maple command "expand" so that you get the expanded form]

#What are Axn(x,i) for i=1..20? Can you get the formula for Axn(x,n) for any non-negative integer n?

#[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]

#Axn(x,n)=x^n

#3) The (unsigned) Stirling number of the first kind, c(n,k) are defined as the number of permutations of
#{1,...,n} with exactly k cycles. By looking at a typical permutation (in cycle notation) of {1, ..., n-1} 
#and figuring how to "insert" n into it, prove the recurrence
#c(n,k)=c(n-1,k-1)+ (n-1)*c(n-1,k)

#Suppose we want to add an nth element to a permutation of n-1 elements.
#We can see that there are two possibilities. 
#The first one is that n becomes the only member of its cycle in the permutation. Then this would be 
#equivalent to increasing n and k both by one, accounting for the case of c(n-1,k-1).
#The second possibility is that n is added to a cycle that has other members. This gives us (n-1)*c(n-1,k) 
#because there are n-1 ways to do this (you can add the nth element after any of the other (n-1)th members, 
#and k did not change. This accounts for all of the ways to count the number of permutations of length n 
#with exactly k cycles. Thus it is shown that c(n,k)=c(n-1,k-1)+ (n-1)*c(n-1,k).

#4) Write a Maple procedure cnk(n,k) (don't forget to use "option remember") analogous to Snk(n,k) in
#M11.txt
#that inputs positive integers n and k (1 ≤ k ≤ n) and outputs c(n,k)

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:

#5) Can you get an explicit expression for
#Sum(c(n,k)*x^k,k=1..n) ?

#[Hint: don't forget to factor it at the end]

#[seq(factor(add(cnk(n, k)*x^k, k = 1 .. n)), n = 1 .. 10)]

#Tested for n=1..10
#[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), x*(x + 5)*(x + 4)*(x + 3)*(x + 2)*(x + 1), x*(x + 6)*(x + 5)*(x + 4)*(x + 3)*(x + 2)*(x + 1), x*(x + 7)*(x + 6)*(x + 5)*(x + 4)*(x + 3)*(x + 2)*(x + 1), x*(x + 8)*(x + 7)*(x + 6)*(x + 5)*(x + 4)*(x + 3)*(x + 2)*(x + 1), x*(x + 9)*(x + 8)*(x + 7)*(x + 6)*(x + 5)*(x + 4)*(x + 3)*(x + 2)*(x + 1)]

#Explicit Expression: 
#Mul(x+i,i=0..n-1)