Combinatorics Worksheet3 – Recurrence Relations

  1. A rabbit is moving from the top-left corner to the bottom-right corner of a 5 x 5 grid (where he sits on the squares, not the corners). Each move, the rabbit can hop right one square, or hop down one square.
    The state can be defined in terms of two variables, the number of remaining squares right r, and the remaining squares down d. Since the right and down actions reduce r and d by 1 respectively, the recurrence is , with base cases for any k.
  2. Use this information to fill out the table for F values:
  3. Explain how we could have worked out the total number of paths through the grid without need for a recurrence relation, by considering each path as a sequence of symbols and the possible arrangement of symbols in the sequence.
  4. Recall the frog problem in which a frog has lily pads in front of it, and can either ‘hop’ on each step (onto the next lily pad) or ‘skip’ (jumping onto the pad 2 in front of it). Now let’s modify the problem such that the Lance the frog (on performance enhancing drugs) can jump ANY number of lily pads, including immediately to the end (but the jump must be at least one pad).
  5. Form a recurrence relation for the number of ways of getting to the end when there are lily pads in front of the frog.
  6. By considering the lily pads each as slots, give an equivalent simple position-to-term formula for the number of ways the frog can get into the end.
  7. Hence, find the number of ways when there are 20 lily pads.
  8. You have a bathroom of n by 2 units, and wish to tile it with 2 by 1 tiles. The diagram below indicates two possible tilings when n = 5. By considering the possible tilings (i.e. actions) at the end of the bathroom, form a recurrence relation. Hence find the possible number of arrangements when n = 10:
  9. [BMO Round 1]Twelve people are seated around a circular table. In how many ways can six pairs of people engage in handshakes so that no arms cross? (Nobody is allowed to shake hands with more than one person at once). [Hint: Focus on the possible actions of one particular person, and how this divides the table into 2 smaller but similar problems]
  10. Optional:[BMO Round 1]A set of positive integers is defined to be wicked if it contains no three consecutive integers. We count the empty set, which contains no elements at all, as a wicked set. Find the number of wicked subsets of the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
    [Hints: Let your state be where you’re considering the next available number to include (starting at 10 and going down), and make a key property of the state that you haven’t used the number immediately prior to the state (i.e. we’ve reset a ‘potential run’). Your actions are whether you include the next number in the set or not. But remember that for each action (or sequences of actions), each need to end up in a state where a run of consecutive numbers has been reset.]

CombinatoricsWorksheet3 – Recurrence Relations - ANSWERS

  1. –
  2. Use this information to fill out the table for F values:
  3. Explain how we could have worked out the total number of paths through the grid without need for a recurrence relation, by considering each path as a sequence of symbols and the possible arrangement of symbols in the sequence.
    Each path across the grid consists of 8 movements. This sequence of moves must consist of 4 right movements and 4 down movements. Of the 8 slots in the sequence, there’s ways of choosing which of these slots will be say the right movements.
  4. Recall the frog problem in which a frog has lily pads in front of it, and can either ‘hop’ on each step (onto the next lily pad) or ‘skip’ (jumping onto the pad 2 in front of it). Now let’s modify the problem such that the Lance the frog (on performance enhancing drugs) can jump ANY number of lily pads, including immediately to the end (but the jump must be at least one pad).
  5. Form a recurrence relation for the number of ways of getting to the end when there are lily pads in front of the frog.
    If is the number of lily pads left, we could jump 1 pad and then have pads left, or 2 and have left, and so on:
  6. By considering the lily pads each as slots, give an equivalent simple position-to-term formula for the number of ways the frog can get into the end.
    For each pad except the last, it could either be jumped on or not, i.e. 2 possibilities. Thus the total number of ways of getting to the end is .
  7. Hence, find the number of ways when there are 20 lily pads.
    Clearly using our formula for (b) requires much less work than using the recurrence in (a)! So there’s ways.
    Incidentally, it’s not difficult to prove the two formulas are equivalent. If (by part b) and (by the recurrence in part a), the latter contains a geometric series (which comes up in the C2 A Level module) where the first term is and the common ratio is and the number of terms is . Thus . Thus .
  8. You have a bathroom of n by 2 units, and wish to tile it with 2 by 1 tiles. The diagram below indicates two possible tilings when n = 5. By considering the possible tilings (i.e. actions) at the end of the bathroom, form a recurrence relation. Hence find the possible number of arrangements when n = 10:
    There are only two possible arrangements of tiles at the bottom of the bathroom:

    If is the possible number of tilings where is the height of the bathroom, then in the first case, we reduce the height by 1, then consider all the arrangements with height . Similarly in the second we consider all arrangements where the height is 2 less.
    Thus .
    The bases cases are and . This is the Fibonacci Sequence! (except starting one number later).
    Using these base cases and the recurrence, we can work out for successive :
  9. [BMO Round 1] Twelve people are seated around a circular table. In how many ways can six pairs of people engage in handshakes so that no arms cross? (Nobody is allowed to shake hands with more than one person at once).
    JAF’s solution: Perhaps one of my favourite questions on this topic!
    By sketching out a 12-agon, I could quickly see that a person could only shake someone’s hand if there are an even number of people to the left and right of his shake (since those on his left-hand-side can’t shake hands with those on his RHS because the shakes would crossover, and if there’s an odd number of people to one side of them, then they can’t all be paired). So a given person can shake hands with the person 1 to his left, or 3 to his left, or 5 to his left, or 7 to his left, or 9 to his left, or 11 to his left. For each of these cases, we’ve essentially reduced the problem into two equivalent ones smaller in size: As indicated on the diagram, if for example he shakes the hand with the person 3 to his left, then there’s 2 people to the left of his handshake who can shake hands in different ways (obviously only 1 way), and independently 8 people to the right of his handshake who can shake hands in a circle-like arrangement.

    This gives us the recurrence relation (where represents the number of people to the left of someone’s shake):

That is, we focus on a particular person, consider different numbers of people he might have to the left of his shake (which might be 0, if they shake the hand of the person immediately to their left), and we can then consider the possibilities independently of possible shakes of people to their left and people to their right.
, since if there’s 2 people there’s only one possible way they can shake! But we could make our base case , because then our recursion relation works (since if we have 0 people to the left and 10 to the right say, that we want to make sure , i.e. we would just consider arrangements to the right.
We can then work out :

  • (which by observation we can see is correct).

So the answer is 132 ways.
By putting these numbers into , I discovered that these are in fact the Catalan numbers numbers I had encountered in other combinatorial contexts, but not this one! The Wikipedia article contains this specific example (although presented more geometrically).

  1. A set of positive integers is defined to be wicked if it contains no three consecutive integers. We count the empty set, which contains no elements at all, as a wicked set. Find the number of wicked subsets of the set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
    Let be the number of wicked sets for 1 to . Consider the last number 10. There’s three possible scenarios:
  2. 10 is in our set. 9 could also be put in our set. But then we’re not allowed the 8 because we’d have three consecutive numbers. This in this scenario, we’d then be interested in the number of wicked sets using 1 to 7. That’s ways.
  3. 10 is in our set, but 9 isn’t. Then we’ve ‘reset’ our run and can now consider the number of wicked sets for the numbers 1 to 8. That’s ways.
  4. It’s not in our set. Then we haven’t even started a run, and can just consider the number of wicked sets using 1 to 9. That’s ways.

So . We can see generally that:
We also know that (since an empty set is itself a wicked set). And clearly (we either have the empty set of a set with a 1 in it) and (we have either or the elements, both, or neither).
Now using this recursion: