232?9 MATHEMATICAL ASSOCIATION OF AMERICA The Poisson Variation of Montmort's Matching Problem

solved the following problem: Matching problem From the top of a shuffled deck of n cards having face values 1, 2,..., n, cards are drawn one at a time. A match occurs if the face value on a card coincides with the order in which it is drawn. For instance, if the face values of a five-card deck appear in the order 2 5 3 4 1, then there are two matches (3 and 4). What is the probability that no match occurs? Known as le probleme des rencontres, Montmort's problem has become a classic. Treated in almost every modern text on combinatorics, it has been recast in a variety of amusing guises including the random switching of n hats by a possibly tipsy cloakroom attendant, the random placement of n letters in n envelopes by a secretary apparently having a bad day, and even in terms of a wager on the ordering in which the horses finish in a given race (for instance, see [3], [4], and [8]). As is well known (e.g., see [2, p. 107]), the principle of inclusion-exclusion may be used to show that the probability M, k of k matches occurring with an n-card deck is 1 n (k) l j=O For k = 0, of course, (1) gives the solution to Montmort's problem. The celebrated fact that the probability of no match occurring is asymptotic to e- 1, that is, lim M0 = e- (2) U ~00 also follows from (1). Incidentally, the distribution of matches {M, k}o < k <, has applications in psychology and in testing psychic powers (e.g., see [1], [2, p. 108], or [9]). The Poisson variation: marking the cards The following twist, henceforth re-ferred to as the Poisson variation, is added to Montmort's problem: Suppose that as each card is drawn it is marked (by underlining its face value) with probability (1- t) where t is a real number between 0 and 1. As underlined integers are evidently distinct from ordinary ones, they cannot be involved in a match. So, if from a five-card deck the sequence of marked and unmarked face values 1 2 5 4 3 appear, then the only match involves 2. Perhaps odd at first glance, this twist gives rise to some aesthetically pleasing mathematics. To be precise, it leads to the following natural extensions of (1) and (2) from t = 1 to the entire interval [0, 1]