## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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.1 Now and there ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required