Before this lesson
M01.8.2 Permutations: arrangements in order M01.7.3 Arithmetic and geometric sums
After this lesson you can
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.
A data set has five examples, a to e. You want to hold out two of them as a test set and train on the other three. How many different test sets could you choose? Five choices for the first and four for the second make 20, but is that really the answer?
From the last lesson
1. What is \(5!\), and what does it count?
\({5! = 120}\). It is the number of orders in which 5 different items can stand in a row.
2. In how many ways can gold, silver and bronze go to 3 of 5 runners?
60: 5 choices for gold, then 4 for silver, then 3 for bronze.
Lesson M01.8.2 counted 60 ordered picks of three items from a, b, c, d and e. Now sort those 60 picks into groups, putting two picks in the same group when they use the same three letters. The group of \(\{a, b, c\}\) holds abc, acb, bac, bca, cab and cba: the 6 orders of those three letters.
The 60 ordered picks of three from five, sorted by the letters they use. Every column is one selection, and every selection appears in exactly \({3! = 6}\) orders.
Every group has exactly 6 picks, because any three different letters can be put in order in \({3! = 6}\) ways (lesson M01.8.2). So the 60 picks fill some number of groups of 6, and that number is the number of ways to choose three letters when their order does not matter:
\[ \frac{60}{6} = 10 \text{ selections.} \]
A choice in which order does not matter is called a combination. It is simply a subset: the selection \(\{a, b, c\}\) and the selection \(\{c, a, b\}\) are the same set.
Step 1. Count with order. The ordered picks of \(k\) from \(n\) different items number \({n!/(n-k)!}\), from lesson M01.8.2.
Step 2. Count the orders of one choice. A choice of \(k\) different items can be put in a row in \(k!\) ways, so it turns up \(k!\) times among the ordered picks.
Step 3. Make an ordered pick in two stages. First choose which \(k\) items to use, then put them in order. Whatever was chosen at the first stage, the second stage has \(k!\) options, so the multiplication principle gives
\[ \begin{aligned} \frac{n!}{(n-k)!} &= (\text{number of choices}) \\ &\quad \times k!. \end{aligned} \]
Step 4. Divide. Dividing both sides by \(k!\) leaves the number of choices on its own. That number gets a name and a symbol of its own:
\[ \binom{n}{k} = \frac{n!}{k!\,(n-k)!}. \]
It is read “\(n\) choose \(k\)”. For five items and three places, \(\binom{5}{3}\) is 120 divided by \({3! \times 2!}\), that is by 12, which gives 10: the ten columns of the picture.
Why. Steps 3 and 4 above, for any \(n\) and \(k\). The second form comes from the first by cancelling \({(n - k)!}\) against the tail of \(n!\), as in lesson M01.8.2. It is the one to use by hand: \(\binom{100}{2}\) is \({100 \times 99}\) over 2, which is 4950, with no need to write out \(100!\).
Three small cases are worth knowing. \({\binom{n}{0} = 1}\), because the empty set is the only subset with no elements, and the formula agrees, since \({0! = 1}\). \({\binom{n}{n} = 1}\), the whole set. \({\binom{n}{1} = n}\), one subset for each single element. If \(k\) is larger than \(n\) there is no subset that big, and the count is 0.
Why the first. Pair each choice of \(k\) items with the \({n - k}\) items it leaves out. Two different choices leave out different items, and every set of \({n - k}\) items is left out by exactly one choice of \(k\), the rest. So the choices of \(k\) and the choices of \({n - k}\) match up one to one, and there are as many of each. The formula agrees: swapping \(k\) and \({n - k}\) only swaps the two factorials underneath. Choosing a test set of 2 from 5 examples is choosing a training set of 3, so \({\binom{5}{2} = \binom{5}{3}}\), and both are 10.
Why the second. Put \({k = 2}\) in the cancelled form: \({n(n-1)}\) over \(2!\), which is 2. For the sum, draw every ordered pair of different items as a grid.
All ordered pairs of different items from five. Each unordered pair appears twice, once on each side of the diagonal, so one triangle holds every pair exactly once.
Keep only the triangle where the first item comes earlier than the second. Its first row pairs the first item with each of the \({n - 1}\) items after it, the second row has \({n - 2}\) pairs, and so on down to 1. Counting the same pairs row by row and by the formula must give the same number:
\[ 1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2}. \]
That is the formula of lesson M01.7.3 for the sum of the whole numbers from 1 to \(m\), with \(m\) equal to \({n - 1}\).
Suppose an item may be chosen more than once and order still does not matter, like scoops of ice cream from 3 flavours a, b and c. With 2 scoops there are 6 choices: aa, ab, ac, bb, bc and cc. Write each choice as stars and bars: one star per scoop, with a bar between the flavours, so ab is \(\star\,|\,\star\,|\) and cc is \(|\,|\,\star\,\star\). Every choice is then a row of \(k\) stars and \({n - 1}\) bars, \({n + k - 1}\) places in all, and it is fixed by which places in the row hold the stars. Choosing \(k\) places for the stars out of the \({n + k - 1}\) gives
\[ \binom{n+k-1}{k} \text{ choices,} \]
and here \({\binom{4}{2} = 6}\).
For 5 items and 3 places it is \({\binom{7}{3} = 35}\). Dividing the \({5^3 = 125}\) ordered strings by \({3! = 6}\) does not work in this case, because the groups now differ in size: three different letters have 6 orders, but aab has only 3 and aaa only 1.
How many test sets of two can five examples give? List them so that none is missed and none is counted twice: write each pair with its earlier letter first, and go through the first letters in turn.
Every test set of two from five examples, each with the training set it leaves behind. The rows hold 4, 3, 2 and 1 test sets.
So there are 10 test sets. The formula agrees, in full and in its cancelled form:
\[ \begin{aligned} \binom{5}{2} &= \frac{5!}{2!\,3!} = \frac{120}{12} = 10, \\ \binom{5}{2} &= \frac{5 \times 4}{2} = 10. \end{aligned} \]
The question’s 20 counted every test set twice, as \(ab\) and as \(ba\). Each test set leaves a training set of three, and different test sets leave different training sets, so there are also \({\binom{5}{3} = 10}\) training sets.
With more data the numbers grow fast. From 100 examples there are \({\binom{100}{2} = 4950}\) test sets of two and \({\binom{100}{5} = 75{,}287{,}520}\) test sets of five. Testing on every possible test set of a given size \(p\) is called leave-\(p\)-out cross-validation. Because of this growth it soon becomes very costly, and the scikit-learn documentation advises other ways of splitting for large data sets.
First from scratch. Two loops with the second index always larger than the first list each pair once, with its earlier item first, exactly as in the worked example.
examples = ["a", "b", "c", "d", "e"]
test_sets = []
for i in range(5):
# Only j after i, so each pair comes once.
for j in range(i + 1, 5):
test_sets.append(examples[i] + examples[j])
print(len(test_sets), test_sets)10 ['ab', 'ac', 'ad', 'ae', 'bc', 'bd', 'be', 'cd', 'ce', 'de']Next the grouping of the picture: sort the letters of each ordered pick to get a key that is the same for every order of the same three letters, and collect the picks in a dictionary under their keys. Then a count of choices by the cancelled formula.
import itertools
groups = {}
# All 60 ordered picks, each a tuple of letters.
picks = list(itertools.permutations(
examples, 3))
for pick in picks:
# Sorting gives one key for every order:
# ('c', 'a', 'b') becomes ('a', 'b', 'c').
key = tuple(sorted(pick))
if key not in groups:
groups[key] = []
groups[key].append(pick[0] + pick[1] + pick[2])
print(len(groups), "groups")
print(groups[("a", "b", "c")])
def choose(n, k):
# No subset is bigger than the set.
if k > n:
return 0
# n(n - 1)...: the ordered picks.
top = 1
for i in range(k):
top = top * (n - i)
# k!: the orders of one choice.
bottom = 1
for i in range(1, k + 1):
bottom = bottom * i
return top // bottom
print(choose(5, 2), choose(5, 3))
print(choose(100, 2), choose(5, 6))10 groups
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
10 10
4950 0The library has both halves. itertools.combinations(items, k) lists the choices, each with its items in their original order, and math.comb(n, k) counts them.
import math
pairs = list(itertools.combinations(
examples, 2))
print(len(pairs), pairs[:3])
print(math.comb(5, 2), math.comb(5, 3))
print(math.comb(100, 2), math.comb(100, 5))
print(math.comb(5, 6))10 [('a', 'b'), ('a', 'c'), ('a', 'd')]
10 10
4950 75287520
0Choose-and-arrange explorer
Choose how many items and how many places, then switch “order matters” and “repeats allowed” on or off. Every outcome is listed, the orders of one selection share a box, and the count is shown beside the formula that gives it.
Things to try:
Wrong beside right. The orders of three letters come in groups of six, not two, so ignoring order divides by \({3! = 6}\).
“Order does not matter, so halve the count.”
Halving is right only for pairs, where each choice has \({2! = 2}\) orders. A choice of three items has \({3! = 6}\) orders, and a choice of \(k\) items has \(k!\). Halving the 60 ordered picks of three gives 30, which still counts every selection three times. Divide by \(k!\).
“I am choosing, so it is a combination.”
Only if the chosen items play the same part. Choose one of five examples for testing and another for validation, and the two jobs are different: \(a\) for testing with \(b\) for validation is not the same split as the other way round. That is an ordered pick, \({5 \times 4}\), which is 20, not \(\binom{5}{2}\). Ask whether swapping two chosen items gives a different outcome. If it does, order matters.
“To work out \(n\) choose \(k\), compute the three factorials.”
That works, but the numbers get huge for no reason: \(\binom{100}{2}\) would need \(100!\), a number with 158 digits. Cancel first. Only \(k\) factors remain on top and \(k!\) underneath: \({100 \times 99}\) over 2 is 4950. In code, math.comb(100, 2) gives 4950 at once.
1. Why does every selection of 3 of the 5 items appear 6 times among the 60 ordered picks?
Because its three different items can be put in order in \({3! = 6}\) ways, and each of those orders is one of the ordered picks.
2. Write the formula for \(\binom{n}{k}\).
\({\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}}\), which after cancelling is \({n(n-1)\cdots(n-k+1)}\) over \(k!\).
3. Why is \(\binom{n}{k}\) equal to \(\binom{n}{n-k}\)?
Each choice of \(k\) items to keep is the same as a choice of the \({n - k}\) items to leave out, and this pairing matches the two kinds of choice one to one.
4. How many pairs can be made from 6 items?
\(\binom{6}{2}\) is \({6 \times 5}\) over 2, which is 15. It is also the sum of 1, 2, 3, 4 and 5.
5. What does math.comb(5, 2) return, and what does itertools.combinations("abcde", 2) give?
math.comb(5, 2) is 10. itertools.combinations hands out the 10 pairs themselves, (‘a’, ‘b’), (‘a’, ‘c’) and so on, each with its letters in their original order.
1. ★ A committee of 3 is chosen from 8 people. How many committees are possible? How many ways are there to choose a chair, a secretary and a treasurer from the same 8 people, and how are the two answers related?
The committee is a choice without order:
\[ \begin{aligned} \binom{8}{3} &= \frac{8 \times 7 \times 6}{3!} \\ &= \frac{336}{6} = 56. \end{aligned} \]
The three posts make it an ordered pick: 8, then 7, then 6 options, 336 ways. Each committee can share out the three posts in \({3! = 6}\) ways, and 56 times 6 is 336.
2. ★★ A data set has 10 examples. How many test sets of 2 examples are possible, and how many training sets of 8? How many test sets of 4?
Test sets of 2: \(\binom{10}{2}\) is \({10 \times 9}\) over 2, which is 45. Each leaves a training set of 8, so there are also \({\binom{10}{8} = 45}\) of those. Test sets of 4:
\[ \begin{aligned} \binom{10}{4} &= \frac{10 \times 9 \times 8 \times 7}{4!} \\ &= \frac{5040}{24} = 210. \end{aligned} \]
3. ★★★ From \(n\) people, a team of \(k\) is chosen and one team member is made captain. Count the ways to do this in two different orders of choosing, and so show that
\[ k\binom{n}{k} = n\binom{n-1}{k-1}. \]
Check it with \({n = 5}\) and \({k = 3}\).
Team first. Choose the team in \(\binom{n}{k}\) ways, then its captain from its \(k\) members: \(k\) ways. In all, \(k\binom{n}{k}\).
Captain first. Choose the captain from all \(n\) people, then the other \({k - 1}\) team members from the remaining \({n - 1}\) people: \(\binom{n-1}{k-1}\) ways. In all, \(n\binom{n-1}{k-1}\).
Both count the same thing, a team with a captain, so they are equal. With \({n = 5}\) and \({k = 3}\): \({3 \times \binom{5}{3}}\) is 3 times 10, and \({5 \times \binom{4}{2}}\) is 5 times 6. Both are 30.
Ignoring order divides out the \(k!\) orders of each choice.
Ten selections, six orders each.
\[ \binom{n}{k} = \frac{n!}{k!\,(n-k)!} \]
Sources. Each was opened and checked against this lesson on 12 November 2026.
Next. M01.8.4 Pascal’s triangle and the binomial theorem lays the numbers \(\binom{n}{k}\) out in a triangle and finds them again in \({(a + b)^n}\).
This lesson unlocks
M01.8.4 Pascal's triangle and the binomial theorem