Discrete Mathematics for Computer Science

Ideas of Chance in Computer Science 487

Proof Since 0 = E U E expresses Q as a union of disjoint sets,

P(Q) = P(E) + P(E)

Since P(Q2) = 1, P(E) = 1 - P(E). M

Example 13. Two parts are chosen at random from a bin containing 10 parts, three of

which are defective. What is the probability that at least one of the parts chosen is good?

Solution. Consider the sample space Q2 to be the set of all C(10, 2) pairs of items, and

give 02 a uniform probability density. Let E be the set of all pairs of parts in which at least

one is good. Then, E = Q - E is the set of all pairs of parts in which both are bad. There

are C(3, 2) pairs in E, so P(E) = C(3, 2)/C(10, 2). Hence,

P(E) =I- (C((3, 2) (3)

=14

P(E)(10, 2C--,)) =^45 =^15 0

Of course, P(E) could also be computed directly: E can be written as the disjoint

union of A, the set of all pairs containing two good items, and B, the set of all pairs
containing exactly one good item. Set A contains C(7, 2) pairs, and set B contains 7 • 3
pairs. Hence,

(C(7, 2) + 21) (21+21) ^14

C(10, 2) 45 15

In the preceding example, finding 1 - P(E) provided an alternative to computing

P (E) directly. In the next example (a classic), this idea is extremely useful.

Example 14. (The Birthday Problem) What is the probability that in a group of n
people, at least two have the same birthday? (Leap years are ignored, and all combinations
of birthdays are assumed to be equally likely.)

Solution. Represent the birthdays of the group by an n-tuple with components that are
integers in the range I through 365. Take QŽ to be the 365n possible n-tuples, and put the
uniform probability density on Q. If E is the event that at least two people have the same
birthday, then E = Q - E is the event that no two people have the same birthday. Hence,
E consists of all possible n-tuples of distinct birthdays.

If n > 365, there are no such n-tuples. Then, E = 0, P(E) = 0, and P(E) = 1.

If n < 365, there are C(365, n) ways to choose n distinct birthdays and n! ways to

assign the chosen birthdays to the n people. Hence, E contains C(365, n) • (n!) n-tuples,

and

P(E) =1 - P(E)

I C(365, n) .(n!)
365n
Alternatively, the number of elements in E can be counted by imagining that the first
person has any of 365 birthdays, the second has any of the 364 remaining possibilities, and
so on. Hence, there are 365 • 364 .... (365 - n + 1) n-tuples in E. In fact, this is just the
number of k-permutations of a 365-element set, as defined in Section 7.5.1, where k = n
in the present case. The reader can check that this is equal to C(365, n) • (n!). Thus, the
two methods of calculating I E I give the same result.