O'Reilly logo

Classic Problems of Probability by Prakash Gorroochurn

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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 img (j = 1, 2, . . . , n) be the property that, in a given permutation, the jth ball drawn has label j, and let img denote the set of permutations with property img. We now compute the total number of permutations, img, for which at least one ball is drawn in the order indicated by its label. We have

img

In the last line, we have used the principle of inclusion and exclusion.1 Now img 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.

Start Free Trial

No credit card required