Let n1 be an integer and let S={1,,n}. Use the Product Rule (Lecture 2) to answer these questions.

1. How many ways are there to partition S into four sets X, Y, Z, and W? [Partition means that each element of S is contained in exactly one of X, Y, Z, or W (and we allow any of these four sets to be empty)]
2. How many ways are there to pick three pairwise-disjoint sets X,Y,ZS? [Pairwise disjoint means that each element of S appears in at most one of X, Y, or Z.]
3. How many ways are there to make three subsets X,Y,ZS so that any element of S appears in at most 2 of the three sets?