> #ok to post
;
> #Yifan Zhang, 10/13/2020, hw11
;
> 
;
> 
;
> #Q1. 
;
> #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:=proc(n,k)  option remember:
> if n=1 then
>  if k=1 then
>  RETURN(1):
>  else
>  RETURN(0):
>  fi:
> fi:
> 
> Snk(n-1,k-1)+k*Snk(n-1,k):
> end:
> Snk(11,5)
246730

;
> add(Snk(11,i), i=1..11)
678570

;
> #There are 246730 ways for 5 different towers. And there are total of 678470 ways with any number of towers.
;
> 
;
> 
;
> #Q2.
;
> #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)
> 
> #[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?
> 

;
> xn:=proc(x,n): local i: expand(product(x-(n-i), i=1..n)): end:
> Axn:= proc(x,n) local i: expand(add(Snk(n,i)*xn(x,i), i=0..n)):end:
> 
;
> Axn(x,1)
x

;
> Axn(x,2)
x^2

;
> Axn(x,3)
x^3

;
> Axn(x,4)
x^4

;
> Axn(x,5)
x^5

;
> Axn(x,6)
x^6

;
> #Axn(x,n):= x^n
;
> 
;
> 
;
> 
;
> 
;
> #Q3.
;
> #
;
> #
;
> #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) 
;
> #c(3,2)=c(2,1)+1*c(2,2)
;
> #c(4,2)=c(3,1)+3*c(3,2)
;
> #Prove: 
> #Consider forming a permutation of n object from a permutation of n-1 object by adding 1 object. Assuming a permutation of n-1 object is c(n-1,k-1) with k-1 cycles. We can add the new object as a single cycle, so the number of the cycle will increase 1 which is c(n-1,k-1), and also we can insert the new object into an existing cycle, and since there are k cycles now with n-1 ways to insert, so (n-1)*c(n-1,k). Then add two conditions up, c(n,k)=c(n-1,k-1)+(n-1)*c(n-1,k).
;
> 
;
> 
;
> 
;
> #Q4.
;
> #Write a Maple procedure cnk(n,k) (don't forget to use "option remember") analogous to Snk(n,k) in
;
> #
;
> #
;
> c:= proc(n,k) 
> option remember:
> if n = 1 then
> if k = 1 then 
> RETURN(1):
> else RETURN(0):
> fi:fi:
> 
> c(n-1,k-1)+(n-1)*c(n-1,k):
> 
> end:
> c(3,2)
3

;
> 
;
> 
;
> 
;
> #Q5.
;
> #Can you get an explicit expression for
> #Sum(c(n,k)*x^k,k=1..n) ?
;
> #
;
> #n=3
;
> c(3,1)*x^1+c(3,2)*x^2+c(3,3)*x^3
x^3+3*x^2+2*x

;
> expand(x*(x+1)*(x+2))
x^3+3*x^2+2*x

;
> #The generating function of unisigned Stiling numbrt of first kind
;
> #Hence the expression for Sum(c(n,k)*x^k,k=1..n) = x*(x+1)*(x+2)*...*(x+n-1)
;
> 
;
> 
;
> 
;
> #Q6.
;
> #By the definition of unsigned Stiling number:
> #
;
> #x*(x+1)*(x+2)*...*(x+n-1) is a rising factorial (x)^(n)=(x+n-1)!/(x-1)! 
;
> #Sum(c(n,k)*x^k,k=1..n) = (x)^(n)
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;
> 
;