Four ways of counting draws

Proposition taught in Random experiments and probability, part of Probability

Four ways of counting draws

The probability that at least two people in a group of n share a birthday. From Random experiments and probability.
Type Proposition
Taught in Random experiments and probability
Part Probability
Worked examples 4
Order recorded Replacement Number of outcomes
yes yes n^k
yes no n!/(n-k)!
no no \binom{n}{k}
no yes \binom{n+k-1}{k}

Ordered outcomes are written as vectors, so (1,2,3)\ne(3,2,1). Unordered outcomes are written as sets, so \{1,2,3\}=\{3,2,1\}.

Examples

The birthday problem

Worked example from Random experiments and probability

A group has n people. Ignore leap days and assume each birthday is equally likely to be any of 365 days, independently.

Question. What is the probability that at least two people share a birthday?

Solution. The birthday count is the second row of the table against the first. The probability that all birthdays differ is

\frac{365\times 364\times\cdots\times(365-n+1)}{365^n},

provided n\le 365, and zero otherwise. The numerator is the number of injective assignments of days, and the denominator is the number of assignments with replacement. The probability of a shared birthday is one minus this. It passes one half at n=23, where it is 0.507, and reaches 0.891 at n=40 and 0.970 at n=50.

The surprise comes from counting the wrong thing. 23 people seem few against 365 days, but they form \binom{23}{2}=253 pairs, and any one of those pairs can match.

Five balls out of twenty

Question page: Five balls out of twenty

Five balls are drawn from an urn of 20 distinct balls, without replacement and without regard to order. How many outcomes are there?

\binom{20}{5}.

Three cards in order

Question page: Three cards in order

Three cards are drawn in order, without replacement, from a deck of 52. The cards are labelled 1,\ldots,52.

  1. Describe the sample space. Are the outcomes equally likely?

  2. Find the probability that the three cards are three aces.

  3. Find the probability that the three cards are one ace, one king and one queen, in any order.

  4. Find the probability that none of the three cards is an ace, king, queen or jack.

  1. \Omega is the set of ordered triples of distinct labels from 1 to 52. The draw is without replacement and no card is preferred, so the outcomes are equally likely.

  2. 4\times 3\times 2/(52\times 51\times 50).

  3. The first card may be any of the 12 aces, kings or queens, the second any of the 8 cards in the two ranks still missing, and the third any of the 4 cards in the last rank: 12\times 8\times 4/(52\times 51\times 50).

  4. There are 36 cards that are not aces, kings, queens or jacks, so the probability is 36\times 35\times 34/(52\times 51\times 50).

Ten balls in three boxes

Question page: Ten balls in three boxes

Ten balls are thrown independently into boxes 1, 2 and 3, with probabilities 1/4, 1/2 and 1/4.

  1. Find the probability that the counts are (2,5,3).

  2. Find the probability that box 1 is empty.

  1. The count vector is multinomial:

\frac{10!}{2!\,5!\,3!}\Bigl(\frac14\Bigr)^2\Bigl(\frac12\Bigr)^5\Bigl(\frac14\Bigr)^3=\frac{315}{4096}\approx 0.0769.

  1. Each ball misses box 1 with probability 3/4, independently, so the probability is (3/4)^{10}\approx 0.0563.

Used in

See also

Sample space · Event · Probability measure · Properties of a probability · Equally likely outcomes · Conditional probability · Product rule · Law of total probability

Glossary and index