#OK to post homework
#Sam Minkin, 10/18, Assignment 11

QUESTION #1:

Suppose we have 11 dolls of differing sizes:
#11 - largest size
#10
#9
...
#1 - smallest size

We want to assemble the dolls into 5 different "towers". Equivalently, we want to partition the set {1,2,3,4,5,6,7,8,9,10,11} into 5 sets.

Running Snk(11,5) will return the set of set-partitions with exactly 5 members:
246730

QUESTION #2:

xn:=proc(x,n):

if n=0 then
	RETURN(1):
fi: 

expand((x-(n-1))*xn(x,n-1)):

end:


Axn:=proc(x,n):

add(Snk(n,k)*xn(x,k),k=0..n):

end:


We can get Axn(x,i), for I=1..20 using 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

Based on the above results, it seems that the formula for Axn(x,n) for any non-negative integer n is Axn(x,n) = x^n.



QUESTION #3:

We want to find the number of permutations with exactly k cycles.

We can construct a permutation with exactly k cycles in the following way:
First, consider a particular element in {1,..,n}. For example, we will consider the element n.
We have two cases: first, either n is in a cycle with itself: (n), or n belongs to one of the other k cycles.
In the first case, if n is in a cycle with only itself, then the remaining elements {1,..,n-1} must have k-1 cycles, given by c(n-1,k-1).
In the second case, we want to add n to one of the k cycles existing for the elements {1,..,n-1}. Although there are k cycles, we may place n into any position within one of the k cycles. For example, if we have {1,2,3,4,5} and k = 2, then we can place 5 into any position of (12)(34), such as (512)(34), (152)(34), (12)(534), (12)(354). Hence, there are n-1 options, giving us (n-1)*c(n-1,k)

Putting our two cases together, we get the recurrence c(n,k) = c(n-1,k-1) + (n-1)*c(n-1,k) as desired.


QUESTION #4:

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:


QUESTION #5:

For n = 5, running factor(add(cnk(5, k)*x^k, k = 1 .. 5)) returns
x*(x + 4)*(x + 3)*(x + 2)*(x + 1),
Which is equivalent to xn(x,5). Furthermore, for n = 6, running factor(add(cnk(6, k)*x^k, k = 1 .. 6)) returns
x*(x + 5)*(x + 4)*(x + 3)*(x + 2)*(x + 1)

Therefore, it seems that add(cnk(n,k)*x^k, k=1..n) = x(n,k) for all n,k.