There are no restrictions here on the number of balls in an urn, or the number of empty urns. To get the answer, let us identify each possible allocation with a string of bars and circles, of the form
with the only condition being that the string should start and end with a bar. The spaces between bars represent urns. Thus, in the arrangement above, the first urn contains balls, the second none, the third 4 balls, and so on. Clearly, the number of distinct arrangements equals —the number of distinct arrangements of bars and circles. Indeed, we have a string of symbols (not counting the two extreme bars), and each arrangement is obtained by specifying places for the symbol .
Example 3.10 shows that the binomial coefficient can be interpreted in two ways. On the one hand, is the number of distinct sets of size that can be chosen out of a set of size . On the other hand, is also the number of distinct strings of indistinguishable elements of one kind and indistinguishable elements of another kind. To see this, it suffices to think of the string as being determined by the choice of “ out of total of ” slots into which we assign elements of the first kind.
Example 3.11 Matching Problem
A secretary typed letters and addressed envelopes. For some reason, the letters were put into envelopes at random. What is the probability of at least one match, that is, of at least one letter being put into the correct envelope?
Solution
This problem appears in many textbooks under various formulations (e.g., of guests receiving their hats at random). One could expect the probability of at least one match to vary greatly with . However, the contrary is true: this probability is almost independent of . Let be the event that th letter is placed in the correct envelope. Using formula (2.6), we have
By symmetry, the probability of each intersection depends only on the number of events in the intersection,2, so we let denote the probability of the intersection of events, Clearly, the numbers of terms in the consecutive sums are
To evaluate we can argue as follows: Assume that the envelopes are ordered in some way. The total number of ways one can order letters is . If specific events, say are to occur (perhaps in conjunction with other events), then the letters number must be at their appropriate places in the ordering (to match their envelopes). The remaining letters can appear in any of the orders. Thus,
Consequently, the th term in the sum (3.25) equals (up to the sign)
and we obtain
Since
we have
with the accuracy increasing as . The approximation is actually quite good for small СКАЧАТЬ
