Title

Staircase Rook Polynomials and Cayley's Game of Mousetrap

Document Type

Article

Publication Date

2009

Publication Title

European Journal of Combinatorics

Department

Mathematics and Computer Science

Abstract

First introduced by Arthur Cayley in the 1850’s, the game of Mousetrap involves removing cards from a deck according to a certain rule. In this paper we find the rook polynomial for the number of Mousetrap decks in which at least two specified cards are removed. We also find a new expression for the rook polynomial for the number of decks in which exactly one specified card is removed and give expressions for counts of two kinds of Mousetrap decks in terms of other known combinatorial numbers.

In the mid-1800’s Arthur Cayley [4] and [5] described a game called Mousetrap that is played as follows: A deck contains cards numbered 1 through nn. Cards are turned over, one by one, and are counted. If a card with the same number as the current count is turned over then it is removed from the deck, and the counting begins again from 1 with the next card. Otherwise, the card is placed on the bottom of the deck and the counting is continued. The game is won if all cards are removed from the deck and lost if the count ever reaches n+1n+1. The major questions concerning the game are these: (1) How many ways are there to win an nn-card game of Mousetrap? (2) How many permutations of the cards 1,2,…,n1,2,…,n result in the removal of exactly kk cards?

Mousetrap has proved surprisingly difficult to analyze. Steen [14] found expressions for the number of permutations of nn cards in which card jj, 1?j?n1?j?n, is the first card removed, the number of permutations in which card 1 and then card jj, j?1j?1, are the first two cards removed, and the number of permutations in which card 2 and then card jj, j?2j?2, are the first two cards removed. Unfortunately, his paper contains some errors. Over one hundred years later these were corrected in apparently independent papers by Mundfrom [10] and Guy and Nowakowski [8]. The latter also found an expression for the number of permutations in which only card jj is removed, and they raised some additional questions about the game of Mousetrap. (See also Guy and Nowakowski [9] and Problem E37 of Guy [7].) The questions of Guy and Nowakowski have, in turn, been partially addressed by Bersani [1], [2] and [3]. However, the results of all of these authors are still far from answering the major questions.

In this paper we determine the rook polynomial for the number of permutations in which card jjis the only card removed and for the number of permutations in which card jjfollowed by card kkare the first two cards removed. The first result contains the same information as was obtained by Guy and Nowakowski, but it is expressed in a more compact form. The second result is the major result in the paper, as it extends the work on Mousetrap to the general case of the removal of the first two cards. Finally, we discuss two sets of numbers arising in the study of Mousetrap that are closely related to other known combinatorial numbers.

ISSN

0195-6698

Link to Full Text

Share

COinS