# Cayley's mousetrap

Cayley's mousetrap is a permutation problem invented by Arthur Cayley. Write the numbers 1, 2, ..., *n* on a set of cards, and shuffle the deck. Now, start counting using the top
card. If the card chosen does not equal the count, move it to the bottom
of the deck and continue counting forward. If the card chosen does equal
the count, discard the chosen card and begin counting again at 1. The game
is won if all cards are discarded, and lost if the count reaches *n* + 1. The number of ways the cards can be arranged such that at least one
card is in the proper place for *n* = 1, 2, ..., are 1, 1, 4, 15,
76, 455, ...