# Transforming puzzle to graph theory?

I am trying to solve the puzzle below and am thinking that there ought to be some way of formulating it as a problem about counting matchings, but I can not make it work. I would appreciate a hint or a different strategy.

N premier league footballers, all with different birth dates, and a single female, Natasha, are to be seated at a round table. To avoid any footballers getting ignored, each footballer must either sit next to a younger footballer or to Natasha. In how many ways can the footballers and Natasha be seated?

-
Here is a hint: First seat Natasha. The youngest player must sit next to Natasha (why?). Once you seated Natasha and the youngest player, what can you say about the rest of the players? –  Michael Ulm Jun 10 '11 at 10:38
I can't beat Michael's hint, but if it's a (directed) graph you want, set one up with a vertex for each person, an arc from each player to each younger player, and two-way arcs joining each player to Natasha; then you're asking for a Hamiltonian cycle. –  Gerry Myerson Jun 10 '11 at 12:21

Let's elaborate the hint of Michael Ulm:

• We first seat Natasha, there are $N+1$ possibilities.
• The youngest footballer cannot sit next to a younger footballer, so we must seat him next to Natasha. There are two possibilities.
• The second youngest footballer can either sit next to Natasha or next to the youngest footballer. There are two possibilities.
• The third youngest footballer must sit next to Natasha or to one the two youngest footballers. Since those three are already seated in a row, there are again two possibilities (the two empty seats next to them).

Going on like this, we have 2 possibilities for all footballers up to the second oldest one. The oldest footballer goes to the last empty seat.

So the total number of possibilities is $$(N+1)\cdot 2^{N-1}.$$

-