Skip to main content

Unordered samples and binomial coefficients

Choose k of n things when order does not matter: divide the ordered count by the k! orders of each choice to get n choose k. Prove Pascal’s rule on a Galton board, and find that exactly 2 heads in 4 fair flips has probability 6/16.
M06.2.3L1 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.2 Ordered samples and the birthday problem

What you will be able to do
  • Derive n choose k = n!/(k!(n - k)!) by dividing the ordered count n!/(n - k)! by the k! orders of each sample.
  • Count the sequences of n coin flips with exactly k heads, and the paths to bin k of a Galton board, as n choose k.
  • Prove Pascal’s rule by asking where a Galton board ball was one row earlier, and build Pascal’s triangle from it.
  • Compute the probability of exactly k heads in n fair flips, by hand, with a recursive function and with math.comb.

The question

Flip a fair coin 4 times. What is the chance of exactly 2 heads? The number of heads can be 0, 1, 2, 3 or 4, so is the answer 1/5? A model’s accuracy on 4 test examples, each right or wrong, poses the same question.

From the last lesson

1. How many ordered samples of size 3 can be drawn from 5 balls without replacement?

Show answer

\({5 \times 4 \times 3 = 60}\), which is \({5!/2!}\).

2. Why does a shared birthday become likely with so few people?

Show answer

Because any pair can match, and \(k\) people make \({k(k-1)/2}\) pairs: 253 pairs among 23 people.

Intuition

Write out every sequence of 4 flips. There are \({2^4 = 16}\), all equally likely. Now sort them by how many heads they hold.

Sixteen boxes, each holding a sequence of four letters H and T, arranged in five columns headed 0 heads, 1 head, 2 heads, 3 heads and 4 heads. The columns hold 1, 4, 6, 4 and 1 sequences; the six sequences with 2 heads, HHTT, HTHT, HTTH, THHT, THTH and TTHH, are yellow. Under the columns the counts 1, 4, 6, 4, 1 are written large, with 1/16, 4/16, 6/16, 4/16 and 1/16 beneath. A line at the bottom reads: 16 equally likely sequences, so P of exactly 2 heads equals 6/16.
M06.2.3-F1

The 16 sequences of 4 flips, sorted by their number of heads. Six of them have exactly 2 heads, so that event has probability 6/16.

The columns are not the same height. There is one way to get no heads and six ways to get two. So the five head counts are not equally likely, and the answer to the hook is \({6/16 = 3/8}\), not 1/5.

The 6 is a count of a new kind. A sequence with 2 heads is fixed by which two of the four places hold the heads, and a set of places has no order: places {1, 3} and places {3, 1} are the same choice. This lesson counts such unordered choices.

Build it up

Step 1. Group the ordered samples. Draw 2 balls from 5 without replacement, keeping order: \({5 \times 4 = 20}\) ordered pairs (lesson M06.2.2). Now ignore order. The pairs 12 and 21 are the same unordered sample {1, 2}.

Ten rounded boxes in two rows, labelled with the sets {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5} and {4, 5}. Each box holds two small blue chips, the two orders of that set, such as 12 and 21. A note above says ordered pairs, blue, grouped into unordered samples, boxes. The line underneath reads 20 ordered pairs divided by 2 factorial orders each equals 10 equals 5 choose 2 samples.
M06.2.3-F2

Every unordered sample of 2 holds exactly \({2! = 2}\) ordered pairs. So the 20 ordered pairs make \({20/2 = 10}\) unordered samples.

Step 2. Every group has the same size. A set of \(k\) different balls can be put in order in \({k!}\) ways (lesson M01.8.2). So every unordered sample is counted \({k!}\) times among the ordered ones, and dividing by \({k!}\) counts each exactly once.

Step 3. Heads are places chosen. A sequence of \(n\) flips with \(k\) heads is fixed by the set of \(k\) places that show H. So the number of such sequences is the number of unordered samples of \(k\) places from \(n\).

Step 4. The Galton board. A ball falls through rows of pegs and bounces left (L) or right (R) at each. Its path is a sequence of L and R, exactly like a sequence of T and H, and its bin is its number of right bounces. So the number of paths into bin \(k\) after \(n\) rows is the number of flip sequences with \(k\) heads.

A Galton board with 4 rows of pegs, 1, 2, 3 and 4 pegs per row, drawn as circles. Each peg holds the number of paths that reach it: row 1 holds 1; row 2 holds 1, 1; row 3 holds 1, 2, 1; row 4 holds 1, 3, 3, 1. Below are five bins labelled bin 0 to bin 4 holding 1, 4, 6, 4 and 1; bin 2 is yellow. A blue path runs from the top peg right, left, right, left into bin 2. Notes beside it read: a path is 4 bounces, L or R, 16 paths; bin k is k right bounces; the blue path R L R L ends in bin 2; each count is the sum of the two above it, 6 equals 3 plus 3.
M06.2.3-F3

The number at each peg counts the paths that reach it. Each count is the sum of the two above it, which is Pascal’s rule; the bins read 1, 4, 6, 4, 1.

The formal statement

NoteUnordered samples: \(n\) choose \(k\)

The number of unordered samples of size \(k\) drawn without replacement from \(n\) distinct items (the number of \(k\)-element subsets of an \(n\)-element set) is, for \({0 \le k \le n}\),

\[ \binom{n}{k} = \frac{n!}{k!\,(n-k)!}. \]

Proof. Count the ordered samples of size \(k\) in two ways. Directly, there are \({n!/(n-k)!}\) of them (lesson M06.2.2). In two stages instead: first choose the unordered sample, in \(\binom{n}{k}\) ways, then put its \(k\) items in order, in \(k!\) ways. By the multiplication rule

\[ \binom{n}{k}\, k! = \frac{n!}{(n-k)!}. \]

Divide both sides by \(k!\).

NotePascal’s rule

For \({1 \le k \le n - 1}\),

\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}. \]

Proof on the Galton board. A path into bin \(k\) after \(n\) rows ends with one last bounce. If that bounce was to the right, the ball was in bin \({k - 1}\) after \({n - 1}\) rows; there are \(\binom{n-1}{k-1}\) such paths. If it was to the left, the ball was already in bin \(k\); there are \(\binom{n-1}{k}\) such paths. Every path ends with exactly one of the two bounces, so the two groups share no path, and their sizes add. (Lesson M01.8.4 proved the same rule by asking whether a choice contains the first item; here the question is about the last bounce.)

Pascal’s triangle is the table of these numbers, built row by row from \({\binom{n}{0} = \binom{n}{n} = 1}\) with each inside entry the sum of the two above it.

NoteExactly \(k\) heads in \(n\) fair flips

All \(2^n\) sequences are equally likely, and \(\binom{n}{k}\) of them have \(k\) heads, so

\[ \Prob(\text{exactly } k \text{ heads}) = \frac{\binom{n}{k}}{2^n}. \]

Worked example

Exactly 2 heads in 4 flips. The two places of the heads form an unordered sample of 2 from the 4 places, so

\[ \begin{aligned} \binom{4}{2} &= \frac{4!}{2!\,2!} = \frac{24}{4} = 6, \\ \Prob(2 \text{ heads}) &= \frac{6}{2^4} = \frac{6}{16} = \frac{3}{8}. \end{aligned} \]

Left, under the heading choose the places of the 2 heads: six rows pairing a choice of places with a yellow sequence: places 1, 2 with HHTT; 1, 3 with HTHT; 1, 4 with HTTH; 2, 3 with THHT; 2, 4 with THTH; 3, 4 with TTHH; then 4 choose 2 equals 6 sequences. Right, under the heading divide by all 16 sequences, P of 2 heads equals 6/16 equals 3/8: bars for 0 to 4 heads labelled 1/16, 4/16, 6/16, 4/16 and 1/16, with the bar for 2 heads yellow.
M06.2.3-F4

The trace. Each choice of 2 places gives one sequence, so there are \(\binom{4}{2} = 6\); dividing by all 16 sequences gives the probability.

Pascal’s rule gives the same 6 without factorials: \({\binom{4}{2} = \binom{3}{1} + \binom{3}{2} = 3 + 3}\). On the board, 3 paths reach bin 1 after three rows and then bounce right, and 3 reach bin 2 and bounce left.

At least 3 heads. Add the bars for 3 and 4 heads: \({(4 + 1)/16 = 5/16}\). They are disjoint events, so their probabilities add.

Code

First a recursive function built on Pascal’s rule alone, with the two ends of each row as the stopping cases. lru_cache remembers answers already found, so each entry is computed once.

from fractions import Fraction
from functools import lru_cache
from itertools import product
import math

@lru_cache(maxsize=None)
def choose(n, k):
    """n choose k from Pascal's rule: the last bounce came from bin k - 1 or from bin k."""
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    return choose(n - 1, k - 1) + choose(n - 1, k)

triangle = [[choose(n, k) for k in range(n + 1)] for n in range(5)]
print(triangle)

flips = list(product("HT", repeat=4))
two_heads = sum(1 for seq in flips if seq.count("H") == 2)
print(len(flips), two_heads, Fraction(two_heads, len(flips)), Fraction(choose(4, 2), 2 ** 4))
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
16 6 3/8 3/8

The library call is math.comb(n, k), which also returns 0 when \({k > n}\). Last, a simulation: 100,000 runs of 4 fair flips.

import numpy as np

print(math.comb(4, 2), math.comb(5, 2), math.comb(52, 5))

rng = np.random.default_rng(11)
heads = rng.integers(0, 2, size=(100_000, 4)).sum(axis=1)
share = np.mean(heads == 2)
print(round(float(share), 4))
6 10 2598960
0.3752

The simulated share sits close to \({3/8 = 0.375}\).

Explore

M06.2-X1

Counting explorer

Choose how many balls are in the bag and how many you draw, then switch “order matters” and “put back” on and off. Every ordered draw is a tile; the tiles that make the same sample share a box. Watch the box sizes: when they are all equal, the samples are equally likely, and when balls go back they are not.

Ten rounded boxes, each an unordered sample of two balls from five such as {1, 2}, each holding its two ordered pairs such as 12 and 21, with the line 20 ordered pairs divided by 2 factorial orders each equals 10 equals 5 choose 2.

Pitfalls

Two bar charts over the number of heads in 4 flips, 0 to 4. Left, marked with a cross and titled each count 1/5: five equal bars labelled 1/5, with the note 5 possible counts. Right, marked with a tick and titled count sequences, 4 choose k over 16: bars labelled 1/16, 4/16, 6/16, 4/16 and 1/16, with the bar for 2 heads yellow.
M06.2.3-F5

Wrong beside right. The five head counts are not equally likely; counting the 16 equally likely sequences gives 1, 4, 6, 4, 1 out of 16.

“There are 5 possible numbers of heads, so each has probability 1/5.”

The head counts are groups of outcomes, and the groups have different sizes. Count in the space of equally likely sequences and divide by \(2^n\), as in lesson M06.2.1.

Left, marked with a cross and titled divide by 2 factorial anyway: nine blue chips 11, 12, 13, 21, 22, 23, 31, 32, 33, the ordered draws of two from three balls with replacement, and the line 9 divided by 2 factorial equals 4.5 samples, with a question mark. Right, marked with a tick and titled groups differ in size: six boxes, three holding a single chip 11, 22 or 33 and marked 1/9, and three holding two chips such as 12 and 21 and marked 2/9, with the line 6 samples, but not equally likely.
M06.2.3-F6

With replacement, dividing by \(k!\) fails: a sample that repeats a ball has only one order.

“To ignore order, always divide by \(k!\).”

Only when every sample has exactly \(k!\) orders, which is true when the \(k\) items are all different. Drawing 2 from 3 balls with replacement gives 9 ordered draws, and \({9/2!}\) is not even a whole number. The 6 unordered samples are real, but {1, 1} has one order and {1, 2} has two, so they are not equally likely: 1/9 against 2/9. Count probabilities on the ordered draws.

“Choosing 2 of 5 and choosing 3 of 5 are different counts.”

They are equal: \({\binom{5}{2} = \binom{5}{3} = 10}\), because choosing which 2 to keep is the same as choosing which 3 to leave. In general \({\binom{n}{k} = \binom{n}{n-k}}\), which is why each row of Pascal’s triangle reads the same backwards.

Check yourself

Recall

1. How is \(\binom{n}{k}\) obtained from the number of ordered samples?

Show answer

Each unordered sample of \(k\) different items has \(k!\) orders, so \({\binom{n}{k} = \dfrac{n!/(n-k)!}{k!}}\), which is \({\dfrac{n!}{k!\,(n-k)!}}\).

2. State Pascal’s rule.

Show answer

\({\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}}\) for \({1 \le k \le n - 1}\).

3. What is the probability of exactly 2 heads in 4 fair flips?

Show answer

\({\binom{4}{2}/2^4 = 6/16 = 3/8}\).

4. On a Galton board with \(n\) rows, how many paths lead to bin \(k\), and why?

Show answer

\(\binom{n}{k}\). A path is a sequence of \(n\) left or right bounces, and it ends in bin \(k\) exactly when \(k\) of them are right, so it is fixed by choosing which \(k\) rows bounce right.

5. Why can you not divide the 9 ordered draws of 2 from 3 balls with replacement by \(2!\)?

Show answer

Because the samples that repeat a ball, such as {1, 1}, have only one order, while the others have two. The groups differ in size, so dividing by \(2!\) does not count them.

Exercises

1. ★ A fair coin is flipped 6 times. Find the probability of exactly 3 heads.

Show solution

\({\binom{6}{3} = \dfrac{6!}{3!\,3!} = \dfrac{720}{36} = 20}\) sequences out of \({2^6 = 64}\), so the probability is \({20/64 = 5/16}\).

2. ★★ Build row 5 of Pascal’s triangle from row 4 with Pascal’s rule, and use it to find the probability of at least 4 heads in 5 fair flips.

Show solution

Row 4 is 1, 4, 6, 4, 1. Adding neighbours gives row 5: 1, \({1 + 4 = 5}\), \({4 + 6 = 10}\), \({6 + 4 = 10}\), \({4 + 1 = 5}\), 1. At least 4 heads means 4 or 5 heads: \({(5 + 1)/2^5 = 6/32 = 3/16}\).

3. ★★★ A classifier answers 10 test questions, each right or wrong. Suppose all \({2^{10}}\) patterns of rights and wrongs are equally likely (a model that guesses). Find the probability of at least 8 right, and explain why a 50% model scoring 8 out of 10 is not very surprising.

Show solution

At least 8 right means 8, 9 or 10 right: \({\binom{10}{8} + \binom{10}{9} + \binom{10}{10}}\), which is \({45 + 10 + 1 = 56}\) patterns out of 1,024, so the probability is \({56/1024 = 7/128 \approx 0.055}\). About one guessing model in 18 scores 8 or more, so on only 10 questions a high score is weak evidence of skill; that is why test sets need many examples (ML01.2).

Summary card

Ignore order by dividing by the \(k!\) orders of each sample: that is \(n\) choose \(k\).

The anchor figure again: the 16 sequences of 4 flips in five columns of 1, 4, 6, 4 and 1 by number of heads, with the six sequences with 2 heads in yellow.
M06.2.3-F1

1, 4, 6, 4, 1 out of 16.

  • Unordered samples: \({\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}}\), in Python math.comb(n, k).
  • Pascal’s rule: \({\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}}\), the last bounce on a Galton board.
  • Fair flips: \({\Prob(k \text{ heads in } n) = \binom{n}{k}/2^n}\); 2 heads in 4 is 6/16.
  • Careful: dividing by \(k!\) works only when the \(k\) items are all different.

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.4 is Pascal’s rule, proved by asking whether a chosen element is in the subset; Theorem 3.5 gives the binomial coefficient as the falling product over \(j!\); Example 3.10 describes the Galton board and notes that a path, written as 0 for left and 1 for right, is a sequence just like \(n\) coin tosses.
  • Hossein Pishro-Nik, Introduction to Probability, Statistics, and Random Processes, Section 2.1.3, Unordered Sampling without Replacement: Combinations: each \(k\)-element subset can be ordered in \(k!\) ways, so the ordered count equals \(\binom{n}{k}\,k!\) and \({\binom{n}{k} = n!/(k!(n-k)!)}\).
  • Python Software Foundation, math.comb, Python 3.12 documentation: the number of ways to choose \(k\) items from \(n\) without repetition and without order, \({n!/(k!(n-k)!)}\), and zero when \({k > n}\).

Next. M06.2.4 Drawing without replacement uses \(n\) choose \(k\) twice in one fraction to find the chance that a random mini-batch holds a given number of positive examples.

This lesson unlocks

M06.2.4 Drawing without replacement M06.5 Discrete random variables

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