Assignment 3-

1. (a) The game of Motzhee consists of rolling five 8-sided dice (each die of a differing color), each of whose faces are numbered with the integers {1, 2, 3, 4, 5, 6, 7, 8}. How many ways are there to roll a full house? A full house consists of five dice, three of which have the same number facing up, the other two of which have the same number facing up as well, but where the number facing up in the triple is different from that of the pair. You can leave your answer in terms of binomial coefficients.

(b) Give a brief combinatorial explanation why, for positive integers k, l, n with k + l ≤ n,

(c) At a party, certain pairs of individuals have shaken hands. Prove that there exist two people who have shaken the same number of hands.

2. A teacup ride at a county fair has 10 seats around a circular table. As the ride progresses, the table spins circularly. How many ways are there to seat 5 couples on this ride if no person is seated next to his/her partner? Seatings are considered equivalent if the table can be rotated to obtain one from the other.

3. Let m, n be positive integers, m < n.

(a) Give an algebraic proof that

(b) Give a combinatorial proof that

4. Let m, n be positive integers with m > n. Show that the number of functions f: {1, 2. . . . , m} → {1, 2, . . . , n} that are surjective (i.e. onto) is

5. Let T_n be the number of ways of tiling a 2 × n checkerboard with 1 × 1 square tiles and L shaped tiles. L shaped tiles are pictured below:

Determine a recurrence satisfied by T_n, and use it to find an explicit formula for T_n in terms of n. Check your formula works for n = 3.