Problem Sheet 1
Exercises
1. Ordering the Letters of ABSTEMIOUSLY:
How many ways are there to order the letters of the word ABSTEMIOUSLY? In how many
of these do the letters A and B remain next to each other? In how many do the six
vowels (A, E, I, O, U, Y) remain in alphabetical order?
2. Celia the Centipede:
Celia the centipede has 100 feet, 100 socks, and 100 shoes. How many orders can she
choose from to put on her socks and shoes? (She must put a sock on foot i before
putting a shoe on foot i.)
3. Die Rolls:
A fair die is rolled nine times. What is the probability that 1 appears three times, 2
and 3 each appear twice, 4 and 5 appear once each, and 6 does not appear at all?
4. Subsets and a Binomial Identity:
Let [n + 1] = {1, 2, . . . , n + 1}. Call a subset of [n + 1] with r + 1 distinct elements
an (r + 1)-subset. How many (r + 1)-subsets of [n + 1] have (k + 1) as their largest
element? Deduce that
n
X k n+1
= .
r r+1
k=r
5. The Birthday Problem:
There are n people in a room. Assume that birthdays are equally likely to fall on any
of the 365 days of the year.
(a) What is the probability that at least two people share the same birthday? How
large must n be for this probability to exceed 21 ?
(b) What is the probability that at least one person has the same birthday as you?
How large must n be for this probability to exceed 12 ?
6. An Urn Problem:
An urn contains m red balls and n blue balls. Two balls are drawn uniformly at random
from the urn, without replacement.
(a) What is the probability that the first ball drawn is red?
(b) What is the probability that the second ball drawn is red?
1
(c) What is the probability that the first ball is red given that the second is red?
7. Coin Tosses and Card Dealing:
(a) A fair coin is tossed 26 times. Write an expression for the probability of obtaining
exactly 13 heads and 13 tails.
(b) A deck of 52 cards (with 26 red and 26 black cards) is shuffled, and 26 cards are
dealt. Write an expression for the probability of obtaining exactly 13 red and 13
black cards.
Without calculating, which of the two probabilities do you expect to be larger? Use
Stirling’s formula,
√ n n
n! ∼ 2πn ,
e
to justify your answer.
8. A Laboratory Test:
A laboratory test is 95% effective in detecting a certain disease when it is present,
but it yields a false positive in 1% of healthy individuals. Suppose that 0.5% of the
population has the disease. What is the probability that a randomly tested individual
actually has the disease, given that their test result is positive?
9. Confused College Porter:
A confused college porter tries to hang n keys on their n hooks. He manages to hang
one key per hook, but all arrangements of keys on hooks are equally likely. Let Ai be
the event that key i is on its correct hook.
(a) Explain why
(n − 1)! (n − 2)! (n − 3)!
P (A1 ) = , P (Ai ∩Aj ) = for i < j, and P (A1 ∩A2 ∩A3 ) = .
n! n! n!
(b) Using the inclusion-exclusion principle:
n n
!
[ X X
P Ai = (−1)r+1 P (Ai1 ∩ · · · ∩ Air ) .
i=1 r=1 1≤i1 <···<ir ≤r
find the probability that at least one key is on the correct hook.
(c) Let pn (r) denote the probability that exactly r keys are on the correct hook, for
0 ≤ r ≤ n. Find an expression for pn (0), the probability that no key is on the
correct hook.
