> #Weiji Zheng, 10/18/2020
;
> #OK TO POST HOMEWORK
;
> 
;
> #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.
;
> 
;
> #SHOULD USE Snk(n,k): The Stirling numbers of the second-kind, aka the NUMBER of set-partitions of an n-element set
;
> 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
;
> #246730 FOR 5 towers
;
> Snk(11,1)+Snk(11,2)+Snk(11,3)+Snk(11,4)+Snk(11,5)+Snk(11,6)+Snk(11,7)+Snk(11,8)+Snk(11,9)+Snk(11,10)+Snk(11,11)
678570
;
> #246730 FOR any number of towers
;
> 
;
> #Q2
;
> #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))
;
> #write another one-line procedure, call it Axn(x,n)that inputs a variable x and a non-negative integer n and outputsSum(Snk(n,k)*xn(x,k),k=0..n)
;
> 
;
> xn := proc(x,n) local i: product(x-i,i=0..n-1):end proc:
> 
;
> Axn := proc(x,n) local i: expand(add(Snk(n,i)*xn(x,i),i=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]
;
> #So I know  Axn(x,n) = x^n
;
> 
;
> #Q3
;
> #prove c(n,k)=c(n-1,k-1)+ (n-1)*c(n-1,k)
;
> #c(n-1,k-1)+ (n-1)*c(n-1,k)
;
> #for the case n is or is not part of set, we have Set partions {1..n-1} with exactly k or k-1 cycles, which is c(n-1,k-1) and (n-1)*c(n-1,k),
;
> #which is c(n,k) = c(n-1,k-1)+(n-1)*c(n-1,k) after adding up
;
> 
;
> #Q4
;
> #Write a Maple procedure cnk(n,k) analogous to Snk(n,k) 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:
> 
;
> #Q5
;
> #Can you get an explicit expression for Sum(c(n,k)*x^k,k=1..n) ?
;
> 
;
> #Found c(4,1)*x^1+c(4,2)*x^2+c(4,3)*x^3+c(4,4)*x^4 =  x^4+6x^3+11x^2+6x = x(x+1)(x+2)(x+3)
;
> #So, Sum(c(n,k)*x^k,k=1..n) = x*(x+1)*(x+2)*...*(x+n-1)
;