Learning Objectives

These problems relate to the course learning outcomes:

● Prove combinatorial identities by counting a set of objects in two ways,

● Describe solutions to iterated processes by relating recurrences to combinatorial identities; and

●  Construct counting problems which show the usefulness or limitations of combinato- rial tools.

1. Let fn  denote the number of binary strings that do not contain “000”. So f3  = 7 and f7  = 81. Which of these equations does fn  satisfy? For each, either give a combinatorial proof that both sides are equal, or find values of fn  that do not satisfy the equation.

(a)  fn+1  = 2fn − fn  3

(b)  fn+1  = fn + fn  1 + fn  2

(c)  fn+1  = 2n+1 − (n − 1)2n  2

2. Let En  denote the number of strings of length n using [5] with an even number of 1s, and let On  denote those strings with an odd number of 1s.

(a) Explain why En + On  = 5n  for every n.

(b) Explain why En+1  = 4En + On  and On+1  = 4On + En .

(c) Prove that En  =  [5n + 3n].

3. Let an  denote the number of length n sequences of blocks, using any of 7 types of blocks with length 2 or 6 types of blocks of length 3. The same type of block can be used any number of times. For example, a5  = 84 and a6  = 379.

(a) Find a recurrence relation for an .

(b) Prove that an  =  [3n+2 + ( −2)n+4 + 5( − 1)n+1].

(c) Find a recurrence relation bn  = cbn  2 +dbn  3 , where bn  =  [5n+2 + 2( −4)n+2 + 3( − 1)n+1], and c, d are integers.

4. A Texas Hold’em poker tournament has 1557 players, in 9 distinct positions at 173 tables. Each table has a standard 52 card deck, and each player is dealt 2 cards. Hands are considered “the same” if they have the same rank of cards and same number of different suits. For example, the nine of hearts and three of hearts is the same as the nine of clubs and three of clubs, but neither are the same as the nine of spades and three of diamonds.

(a)  Show that there are two people in the tournament with the same starting hand

and position.

(b)  Show that, for every position, there are two people with the same starting hand.

(c)  Show that there are two people who are dealt identical cards (not just “the same”, but with ranks and suits matching).