Counting Set Partitions For each of these problems, write down the permutation/combination expression and then sim-

plify to a final number. Let S and S1,S2,Sn be sets. S1,S2, ,Sn partition S if and only if

The union of all n sets is exactly S: ni=1 Si = S and Every pair of subsets share no elements

We call S1,S2,Sn a partition of S. For example, let S = {1, 2, 3, 4}. Then

{1, 2}, {3, 4} partition S. {1}, {2, 4}, {3} also partition S. However, {1, 3, 4}, {2, 4} do not partition S.

Finally, two partitions are the same if they have the same subsets. For example, {1, 2}, {3, 4} is the same partition as {3, 4}, {1, 2}.

Say we have a set A = {1,2,5,14,42}.

i. Show there are 25 ways to partition A into 3 sets, assuming none of the sets used are empty without writing down any of the sets as your answer That is, do not list the 25 sets. Show all of your work. (Hint: Think about how you are going to count these sets before you think about which tools to use.)

ii. How many ways can we partition A, assuming none of the sets used are empty without writing down the sets as part of your answer? That is, do not list and then count all of the sets as your answer. Show all of your work.