Lecture 11: Due Oct. 18, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment

hw11FirstLast.txt

OK to Post

	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.

		Asnwer: Using SnK(11,5), we derive the answer: 246730

	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)
	   [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?

		Answer: 
			xn:=proc(x,n) local k:
				prod(x-k,k=1..(n-1)):
			end:

			Axn:=(x,n) local k:
				SSum(Snk(n,k)*xn(x,k),k=0..n):
			end:
			
			Unable to get Snk(x,i) in general, let alone Axn(x,i) as there are too many levels of recursion. Cannot answer question


    	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)

		Answer:
			from {1,...,n} into k cycles, we get two different possibilites
				[1-cycle]
					we get that the remaing cycles form a permutation of length n-1 with k-1 cycles, thus we have c(n-1,k-1)
				[not 1-cycle]
					then we get that n is a cyccle greater than or equal to 2. Thus we get permutations of {1,...,n-1} with k cycles, thus c(n-1,k). 	
					However, since k has n-1 different options, we get (n-1) * c(n-1,k)
			Thus, together, we get 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)

		Answer:
			cnk:=proc(n,k)
			option remember:

			  if k = 0 then
			   if n = 0 then
			    return 1:
                           fi:
			  fi: 
			  
			  if k = 0 then
			   return 0:
			  fi:
			
			  if n = 0 then
			   return 0:
			  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]

		Answer:(x) * (x+1) * ... * (n+x-1) = ((n+x-1)!/(x-1)!