This homework is due on gradescope Friday October 14th at 11:59pm pacific time. Remember to justify your  work  even  if  the  problem  does  not  explicitly  say  so.   Writing  your  solutions  in  LATEXis  recommend though not required.

Question 1 (Dice Designs, 35 points). When making a die one must put the numbers 1 through 6 on the six faces of a cube so that each number appears on a distinct face. We say that two such designs are the same if it is possible to rotate one of the cubes so that the numbers on its faces agrees with the others’. How many di↵erent designs are there?

Hint: Relate the number of designs to the number of ways of labelling six faces 1 through 6. Not every labelling is a distinct design, but can you quantify the di↵erence?

Question 2 (Composition Counting, 30 points). .

(a) How many compositions of n into k parts of size 1 and 2 are there? [10 points]

(b) How many compositions of n into any number of parts with one of the parts colored red are there? [10 points]

(c) What is the sum over compositions of n into k parts of the product of the sizes of the parts? Hint: Count the number of stars and bars configurations with one star in each part highlighted. [10 points]

Question 3 (Set Partition Identity, 35 points). Prove that for any positive integer n that:

X 2^kS(n, k) = X

✓ n ◆

B(n — m)B(m).