Exercise 4.

The two richest families in Westeros have decided to enter into an alliance by marriage. The first family has 10 sons, the second has 10 girls. The ages of the kids in the two families match up. To avoid impropriety, the families insist that each child must marry someone either their own age, or someone one position younger or older. In fact, the graph representing agreeable marriages looks like this:

A bipartite graph with 20 vertices in two sets of ten.  Each vertex in the top row is adjacent to the vertices directly below it and those vertices below and one position left or right of it.

The question: how many different acceptable marriage arrangements which marry off all 20 children are possible?

  1. How many marriage arrangements are possible if we insist that there are exactly 6 boys who marry girls not their own age?

  2. Could you generalize the previous answer to arrive at the total number of marriage arrangements?

  3. How do you know you are correct? Try counting in a different way. Look at smaller family sizes and get a sequence.

  4. Can you give a recurrence relation that fits the problem?

in-context