Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

Cayley's mousetrap





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, ...


Related category

   • COMBINATORICS