# 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

• We first seat Natasha, there are $N+1$ possibilities.
So the total number of possibilities is $$(N+1)\cdot 2^{N-1}.$$