Let [12] denote the set {1, 2, 3, . . . , 12}. A matching of [12] is a way of partitioning the elements into pairs so that each element is in exactly one pair. For example, one matching is {1, 3}, {2, 7}, {4, 10}, {5, 6}, {8, 11}, {9, 12}. For each of the following count the number of matchings with the given property both as a formula and by giving the exact number. Remember to justify your answer.

(a) The number of all matchings of [12].

(b) The number of matchings of [12] where each even number is paired with another even number.

(c) The number of matchings of [12] where each even number is paired with an odd number.

(d) The number of matchings of [12] where each number is paired with another number at most 2 away from it (for this you will want to relate the number of such pairings of [2n] to the number of such pairings of [2(n 1)] and of [2(n 2)] and produce a recurrence).

(e) The number of matchings of [12] where each of 1, 2, 3 is paired to one of 1, 2, 3, 4, 5, 6, 7, 8, 9.

(f ) The number of matchings of [12] where there are exactly 2 pairs of even numbers that are matched together.