Skip to main content

Ordered samples and the birthday problem

Draw k times from n things and keep the order: n^k ways with replacement and n!/(n - k)! without. Their ratio answers the birthday problem: among 23 people a shared birthday is more likely than not, the same sum that predicts hash collisions.
M06.2.2L1 Core25 min
In review

The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

Before this lesson: M06.2.1 Equally likely outcomes

What you will be able to do
  • Count ordered samples of size k from n items as n^k with replacement and n!/(n - k)! without, deriving both from the multiplication rule.
  • Compute the chance that k people all have different birthdays as a ratio of the two counts, by hand for a 5-day year.
  • Find in code that a shared birthday among 365 days passes one half at k = 23, with exact fractions and math.perm.
  • Explain why the number of pairs, not the number of people, drives collisions in hashes and in bootstrap samples.

The question

A room holds 23 people. Is it more likely than not that two of them share a birthday? Most people guess that you would need far more, perhaps half of 365. The same question, asked about a hash function instead of a calendar, decides how often two different files get the same fingerprint.

From the last lesson

1. When may you compute a probability as \(|A|/|\Omega|\)?

Show answer

When the sample space is finite and every outcome in it is equally likely.

2. How many outcomes does a 4-digit PIN have, and which rule gives the count?

Show answer

\({10^4 = 10{,}000}\), by the multiplication rule: four stages with 10 options each.

Intuition

Put three numbered balls in a bag. Draw one, write its number down, and draw again. The result is an ordered sample: a list such as 2 then 3, where 23 and 32 count as different results. Two questions decide how many lists there are: is the ball put back before the next draw, and does order matter? This lesson keeps order. The next one lets it go.

Two panels, each a 3 by 3 grid of ordered pairs from balls 1, 2 and 3, with the first draw along the columns and the second draw down the rows, and a column of three numbered balls beside it. Left, titled with replacement: every ball can come again, all nine cells 11, 21, 31, 12, 22, 32, 13, 23, 33 are blue, the balls are marked back in, and the caption reads 3 times 3 equals 9 ordered samples. Right, titled without replacement: no ball twice, the diagonal goes, the cells 11, 22 and 33 are dashed and struck through, the balls are marked kept out, and the caption reads 3 times 2 equals 6 ordered samples.
M06.2.2-F1

Two ordered draws from three balls. With replacement every one of the 9 pairs can happen. Without replacement the ball you drew is gone, so the 3 pairs that repeat a ball cannot happen, leaving 6.

With replacement, each draw sees the full bag. Without replacement, each draw sees one ball fewer. Both counts come straight from the multiplication rule, and both sample spaces are equally likely when every ball is equally likely to be drawn at each step.

Build it up

Step 1. With replacement. Draw \(k = 3\) times from \(n = 5\) balls, putting each ball back. Every draw has all 5 options, whatever came before, so there are \({5 \times 5 \times 5 = 125}\) ordered samples.

Step 2. Without replacement. Now keep each ball out. The first draw has 5 options, the second 4 (one ball is gone), the third 3. The number of options at each stage depends on nothing but how many balls are gone, so the multiplication rule still applies: \({5 \times 4 \times 3 = 60}\).

Two rows of three boxes labelled draw 1, draw 2 and draw 3, each with five small balls beneath it. Top row, titled with replacement: every draw has all 5 balls, all balls are filled, each draw has 5 options, and a box reads 5 times 5 times 5 equals 5 cubed equals 125. Bottom row, titled without replacement: one fewer ball each time, draw 2 has one hollow ball and draw 3 two hollow balls, the options read 5, 4 and 3, and a box reads 5 times 4 times 3 equals 5 factorial over 2 factorial equals 60. A note says hollow balls are already drawn and not available.
M06.2.2-F2

The same three draws, slot by slot. With replacement the options stay at 5. Without, they fall by one at each draw.

Step 3. Write the second count with factorials. The product \({5 \times 4 \times 3}\) is the start of \({5! = 5 \times 4 \times 3 \times 2 \times 1}\) with the tail \({2 \times 1 = 2!}\) cut off, so it equals \({5!/2!}\). In general the product stops after \(k\) factors, so the tail that is cut off is \({(n - k)!}\).

Step 4. The birthday question is a ratio. List \(k\) people’s birthdays in order. Each list is an ordered sample from \(n\) days with replacement, because two people may share a day. The lists in which no day repeats are ordered samples without replacement. So

\[ \Prob(\text{all different}) = \frac{\text{without}}{\text{with}}. \]

The formal statement

NoteOrdered samples

From \(n\) distinct items, the number of ordered samples of size \(k\) is

  • with replacement: \(n^k\);
  • without replacement (for \(k \le n\)):

\[ \begin{aligned} &n(n-1)\cdots(n-k+1) \\ &\quad= \frac{n!}{(n-k)!}. \end{aligned} \]

Proof. With replacement there are \(k\) stages, each with \(n\) options, so the multiplication rule gives \(n^k\). Without replacement, stage \(i\) (for \(i = 1, \dots, k\)) has \({n - (i - 1)}\) options, because \({i - 1}\) items are already gone, and that number does not depend on which items they were. The product of the \(k\) stages runs from \(n\) down to \({n - k + 1}\). Multiplying that product by \({(n - k)!}\) adds the missing factors from \({n - k}\) down to 1:

\[ \begin{aligned} &n(n-1)\cdots(n-k+1)\cdot(n-k)! \\ &\quad= n(n-1)\cdots 2 \cdot 1 = n!. \end{aligned} \]

Dividing both sides by \({(n - k)!}\) gives \({n!/(n-k)!}\).

For \({k > n}\) there are no samples without replacement: stage \({n + 1}\) has no item left.

NoteThe birthday problem

If each of \(k\) people’s birthdays is equally likely to be any of \(n\) days, independently, so that all \(n^k\) lists are equally likely, then

\[ \begin{aligned} p_k &= \Prob(\text{all } k \text{ differ}) \\ &= \frac{n!/(n-k)!}{n^k} \\ &= \frac{n}{n}\cdot\frac{n-1}{n}\cdots\frac{n-k+1}{n}, \end{aligned} \]

and the chance of at least one shared birthday is \({1 - p_k}\).

Why. \(\Omega\) is the set of \(n^k\) ordered lists, all equally likely. The event “all differ” is the set of lists with no repeat, of which there are \({n!/(n-k)!}\). Divide (lesson M06.2.1). The last line pairs each factor on top with one \(n\) underneath. The shared birthday is the complement.

For a 365-day year the chance of a shared birthday first passes one half at 23 people: \({1 - p_{23} \approx 0.507}\). The curve climbs fast after that, to 0.970 at 50 people.

A rising S-shaped black curve of the probability that at least two of k people share a birthday, for k from 1 to 70 and a 365-day year. A dashed horizontal line marks one half. An orange vertical line and dot at k equals 23 meet the curve just above the half line, labelled 23 people, P shared equals 0.507. A black dot at k equals 50 is labelled 50 people, 0.970. The curve is close to 1 by k equals 70.
M06.2.2-F4

The birthday curve for 365 days, from the formula above. It crosses one half between 22 and 23 people.

Worked example

A 5-day year. Suppose a year had only 5 days, all equally likely as birthdays. Take \({k = 3}\) people.

  • All ordered lists of birthdays: \({5^3 = 125}\).
  • Lists with three different days: \({5 \times 4 \times 3 = 60}\).
  • \({p_3 = 60/125 = 12/25 = 0.48}\), so a shared birthday has probability \({13/25 = 0.52}\).

Already with 3 people in a 5-day year a match is more likely than not. The same product, one factor per person, gives every \(k\):

A bar chart of the probability that k people all have different birthdays in a 5-day year, for k from 1 to 6. The bars are labelled 1, 4/5, 12/25, 24/125, 24/625 and 0; the bar for k equals 3 is yellow. Beside it the trace for k equals 3 reads: Omega has 5 cubed equals 125 lists; A has 5 times 4 times 3 equals 60; P of A equals 60 over 125 equals 12 over 25; P shared equals 13 over 25. A note says six people in a 5-day year must share, so the last bar is 0.
M06.2.2-F3

Each new person multiplies the chance by the share of days still free: 5/5, then 4/5, then 3/5, and so on. At 6 people it hits 0.

\[ \begin{aligned} p_1 &= 1, \qquad p_2 = \tfrac{4}{5}, \qquad p_3 = \tfrac{12}{25}, \\ p_4 &= \tfrac{24}{125}, \qquad p_5 = \tfrac{24}{625}, \qquad p_6 = 0. \end{aligned} \]

Six people in a 5-day year must share a day, so \({p_6 = 0}\): the factor \({(5 - 5)/5}\) is zero.

Code

From scratch, the product of the formula with exact fractions, then a search for the first \(k\) at which a shared birthday is more likely than not.

from fractions import Fraction
import math

def all_different(n, k):
    """P(k birthdays from n equally likely days are all different), as a product of k factors."""
    p = Fraction(1)
    for i in range(k):
        p *= Fraction(n - i, n)
    return p

print([str(all_different(5, k)) for k in range(1, 7)])

k = 1
while 1 - all_different(365, k) <= Fraction(1, 2):
    k += 1
print(k, round(float(1 - all_different(365, k)), 4), round(float(1 - all_different(365, 50)), 4))
['1', '4/5', '12/25', '24/125', '24/625', '0']
23 0.5073 0.9704

The library gives the counts directly. math.perm(n, k) is \({n!/(n - k)!}\), the ordered samples without replacement, and it returns 0 when \({k > n}\).

p23 = Fraction(math.perm(365, 23), 365 ** 23)
print(math.perm(5, 3), 5 ** 3, math.perm(5, 6), round(float(1 - p23), 4))
60 125 0 0.5073

Finally a simulation: 100,000 rooms of 23 people, each birthday a random day.

import numpy as np

rng = np.random.default_rng(7)
rooms = rng.integers(0, 365, size=(100_000, 23))
shared = np.mean([len(set(room)) < 23 for room in rooms])
print(round(float(shared), 3))
0.508

The simulated share lands within about a hundredth of 0.507, as it should with 100,000 rooms.

Explore

The counting explorer of this module lives in lesson M06.2.3. Set it to order matters, with replacement, and press the button that lights up the draws in which every ball is different: their share of all the draws is this lesson’s \(p_k\) for a tiny year.

Pitfalls

Two circles of 23 dots, each standing for a person, with one orange dot at the top. Left, marked with a cross and titled only pairs with me: the orange dot labelled me is joined by 22 vermillion lines to each other dot, and the caption reads 22 pairs, P equals 0.059. Right, marked with a tick and titled every pair counts: all 253 pairs of dots are joined by green lines, making a dense web, and the caption reads 253 pairs, P equals 0.507.
M06.2.2-F5

Wrong beside right. Matching your birthday involves only the 22 pairs that include you. A shared birthday can be any of the 253 pairs in the room.

“With 23 people, someone shares my birthday with probability about one half.”

That is a different event. The chance that none of the other 22 has your birthday is \({(364/365)^{22}}\), so someone matches you with probability about 0.059. You need 254 people before a match with you is more likely than not. The birthday problem asks about any pair, and 23 people make \({23 \times 22 / 2 = 253}\) pairs.

“Without replacement is \(n^k\) too: each draw still picks one of the items.”

Without replacement the items already drawn are not available, so the count falls by one at each draw. Using \(n^k\) counts lists that repeat an item, which cannot happen. Ask at every stage: how many options are really left?

“Collisions are rare when the space is huge.”

A hash function that gives one of \({2^{32}}\) (about 4.3 billion) values behaves like a year of \({2^{32}}\) days. The birthday formula says that a collision is more likely than not once about 77,000 items are hashed, a tiny fraction of the space. The same arithmetic warns that a bootstrap sample, \({n}\) rows drawn with replacement from \({n}\) (module S02.8), almost always repeats rows.

Check yourself

Recall

1. How many ordered samples of size \(k\) can be drawn from \(n\) items with replacement, and how many without?

Show answer

With replacement \(n^k\); without replacement \({n!/(n - k)!}\), which is \({n(n-1)\cdots(n-k+1)}\) for \({k \le n}\) and 0 for \({k > n}\).

2. How many ordered pairs of different balls can be drawn from three balls?

Show answer

\({3 \times 2 = 6}\): the 9 pairs with replacement minus the 3 that repeat a ball.

3. Write the chance that \(k\) people all have different birthdays in an \(n\)-day year as a ratio of two counts.

Show answer

\({p_k = \dfrac{n!/(n-k)!}{n^k}}\): lists with no repeat over all lists.

4. In a 5-day year, what is the chance that 3 people all have different birthdays?

Show answer

\({(5 \times 4 \times 3)/5^3}\), which is 60/125, or 12/25.

5. How many people does a 365-day year need before a shared birthday is more likely than not?

Show answer
  1. The chance of a shared birthday is about 0.476 at 22 people and about 0.507 at 23.

Exercises

1. ★ A 4-digit PIN is chosen at random from all 10,000. What is the probability that its four digits are all different?

Show solution

PINs with four different digits are ordered samples without replacement from 10 digits: \({10 \times 9 \times 8 \times 7 = 5{,}040}\). So the probability is \({5{,}040/10{,}000 = 0.504}\).

2. ★★ Five people each pick a random number from 1 to 10, all choices equally likely and independent. Find the probability that at least two pick the same number.

Show solution

All lists: \({10^5 = 100{,}000}\). Lists with no repeat: \({10 \times 9 \times 8 \times 7 \times 6 = 30{,}240}\). So all differ with probability 0.3024 and at least two match with probability \({1 - 0.3024 = 0.6976}\).

3. ★★★ A bootstrap sample draws \(n\) rows from a table of \(n\) rows with replacement, every ordered list of row numbers being equally likely. For \({n = 10}\), find the probability that row 1 is never drawn, and the probability that no row is drawn twice.

Show solution

All lists: \({10^{10}}\). Lists that avoid row 1 use only the other 9 rows at each of the 10 draws: \({9^{10}}\). So row 1 is missed with probability \({(9/10)^{10} \approx 0.349}\). Lists with no repeat are ordered samples without replacement of all 10 rows: \({10! = 3{,}628{,}800}\), so the probability is \({10!/10^{10} \approx 0.00036}\). A bootstrap sample of 10 rows almost always repeats a row, and leaves out any given row about a third of the time.

Summary card

Order kept: \(n^k\) with replacement, \(n!/(n-k)!\) without; their ratio is the birthday problem.

The anchor figure again: a 3 by 3 grid of ordered pairs from three balls with all nine cells counted, beside the same grid with the diagonal 11, 22, 33 struck out, leaving 6.
M06.2.2-F1

Back in: 9. Kept out: 6.

  • With replacement: \(n^k\) ordered samples.
  • Without replacement: \({n(n-1)\cdots(n-k+1)}\), which is \({n!/(n-k)!}\), in Python math.perm(n, k).
  • Birthdays: \({\Prob(\text{all differ}) = \dfrac{n!/(n-k)!}{n^k}}\); for 365 days it falls below one half at \({k = 23}\).
  • Why so few: \(k\) people make \({k(k-1)/2}\) pairs, and any pair can match.

Sources and next steps

Sources. Each was opened and checked against this lesson on 14 November 2026.

  • Charles M. Grinstead and J. Laurie Snell, Introduction to Probability, second edition. Theorem 3.2 counts the \(k\)-permutations of \(n\) elements as \({n(n-1)\cdots(n-k+1)}\); Example 3.3, the birthday problem, takes the \(365^r\) equally likely lists of birthdays, counts those with no repeat, and shows in Table 3.1 that the chance of all different birthdays is 0.4927 for 23 people.
  • Hossein Pishro-Nik, Introduction to Probability, Statistics, and Random Processes, Section 2.1.2, Ordered Sampling without Replacement: Permutations: the count \({n!/(n-k)!}\) and the birthday problem, with a shared birthday at about 0.5073 for 23 people. Section 2.1.1 covers ordered sampling with replacement.
  • Python Software Foundation, math.perm, Python 3.12 documentation: the number of ways to choose \(k\) items from \(n\) without repetition and with order, \({n!/(n-k)!}\), and zero when \({k > n}\).

Next. M06.2.3 Unordered samples and binomial coefficients lets order go: dividing by the \(k!\) orders of each sample gives \(n\) choose \(k\).

This lesson unlocks

M06.2.3 Unordered samples and binomial coefficients

Your progress is saved in this browser only. No account, no tracking.
Back to top