Classic Problems of Probability

Problem 7

Rencontres with Montmort (1708)

Problem. Suppose you have a jar containing n balls numbered 1, 2, 3, . . . , n, respectively. They are well mixed and then drawn one at a time. What is the probability that at least one ball is drawn in the order indicated by its label (e.g., the ball labeled 2 could be the second ball drawn from the jar)?

Solution. There are n! permutations (or ordered sequences) of the n balls {1, 2, . . . , n}. Assume that the jth element in a permutation represents the jth ball drawn. Let (j = 1, 2, . . . , n) be the property that, in a given permutation, the jth ball drawn has label j, and let denote the set of permutations with property . We now compute the total number of permutations, , for which at least one ball is drawn in the order indicated by its label. We have

In the last line, we have used the principle of inclusion and exclusion.¹ Now and there ...