A group of 10 friends goes to the movies and needs to pick 3 people to buy the popcorn. Only who goes matters, not the order in which they were chosen. This is a combination.
Why combinations? #
Selecting subsets without regard to order is one of the most frequent operations in computing and data science:
- Data analysis: the number of pairs of variables in a set of \(n\) columns is \(C(n, 2)\), the basis of correlation matrices and association tests in SQL (Structured Query Language) and pandas.
- Software testing: the all-pairs testing technique (testing every pair of parameters) must cover the interactions of each of the \(C(k, 2)\) pairs that can be formed from \(k\) parameters.
- Graph theory: the maximum number of edges in a simple graph with \(n\) vertices is \(C(n, 2)\), because each edge is a combination of two distinct vertices, with no direction.
- Cryptography: threshold schemes allow any subgroup of at least \(r\) out of \(n\) participants to reconstruct a secret key. The number of minimal subgroups that reconstruct it is \(C(n, r)\).
- Statistics and machine learning: the binomial coefficient \(C(n, r)\) appears in the binomial distribution and in feature subset selection. With \(n\) features, there are \(C(n, r)\) possible models that use exactly \(r\) of them.
From arrangement to combination #
In the article on arrangements, we saw that choosing \(r\) distinct elements out of \(n\) splits into two cases depending on whether order matters. The diagram below completes that decision tree by adding the combination branch:
flowchart TD
A["n distinct elements"] --> B{"Use all of them?"}
B -->|"Yes"| C["Permutation
P_n = n!"]
B -->|"No, choose r ≤ n"| D{"Does order matter?"}
D -->|"Yes"| E["Arrangement
A(n,r) = n!/(n-r)!"]
D -->|"No"| F["Combination
C(n,r) = n!/(r!(n-r)!)"]
Combinations #
The diagram above already anticipates the formal definition:
A combination of \(n\) distinct elements taken \(r\) at a time (an r-combination) is a selection of \(r\) elements without regard to order:
$$C(n, r) = \binom{n}{r} = \frac{n!}{r! (n-r)!}$$The formula comes straight from the arrangement: each combination generates \(r!\) arrangements, one for each reordering of the \(r\) chosen elements. Dividing the arrangement count by the number of internal reorderings gives the combination:
$$A(n,r) = C(n,r) \cdot r! \implies C(n,r) = \frac{A(n,r)}{r!} = \frac{n!}{r! (n-r)!}$$Properties #
Three fundamental identities simplify many practical calculations:
Choosing who joins the group is equivalent to choosing who stays out: the two subsets determine each other.
$$C(n, 1) = C(n, n-1) = n$$
When \(r > n/2\), use the symmetry \(C(n, r) = C(n, n-r)\): computing with \(n - r < r\) reduces the number of factors in the numerator and simplifies the calculation by hand.
Arrangement vs. Combination: How to Decide #
The key question is always: “Does order change the result?” The table below summarizes the most common cases:
| Situation | Does order matter? | Technique |
|---|---|---|
| Race podium (1st, 2nd, 3rd) | Yes | Arrangement |
| Committee of 3 members out of 10 | No | Combination |
| 4-digit password with distinct digits | Yes | Arrangement |
| 5-card hand from a deck | No | Combination |
Worked Examples #
Committee of 3 out of 10 people #
Problem: An association needs to choose 3 members out of 10 volunteers to form a committee. How many distinct committees can be formed?
Solution: Order does not matter, since a committee \(\{A, B, C\}\) is the same as \(\{B, A, C\}\). We apply the combination formula:
$$C(10, 3) = \frac{10!}{3! 7!} = \frac{10 \times 9 \times 8}{6} = \mathbf{120}$$Back to the opening example: the group of 10 friends can choose the 3 people for the popcorn in 120 distinct ways.
SQL: JOIN with an order filter to generate combinations
JOIN with an order filter to generate combinations
In SQL, the difference between an arrangement and a combination is just the
join condition. In the
article on arrangements
we used <> to avoid repetition while generating both directions; here we
use > to impose a canonical order and count each subset exactly once:
CREATE TABLE people (id INT, name TEXT);
INSERT INTO people VALUES
(1,'Ana'),(2,'Bruno'),(3,'Carlos'),(4,'Diana'),(5,'Eva'),
(6,'Felipe'),(7,'Gabi'),(8,'Hugo'),(9,'Iara'),(10,'João');
-- id_a < id_b < id_c guarantees that each trio appears exactly once,
-- regardless of the order of the names
SELECT a.name, b.name, c.name
FROM people a
JOIN people b ON b.id > a.id
JOIN people c ON c.id > b.id
ORDER BY a.name, b.name, c.name;
SELECT COUNT(*)
FROM people a
JOIN people b ON b.id > a.id
JOIN people c ON c.id > b.id;
-- 120 = C(10, 3)Replacing > with <> in the join conditions and adding
AND c.id <> a.id (so that the 1st and the 3rd are also distinct),
we would count the arrangements
\(A(10, 3) = 720\), six times as many, since each trio would appear in
all \(3! = 6\) possible orders.
5-card hand from a 52-card deck #
Problem: How many hands of 5 distinct cards can be dealt from a standard 52-card deck?
Solution: The order of the cards in the hand does not matter, since a hand \(\{A\spadesuit, K\heartsuit, Q\diamondsuit, J\clubsuit, 10\spadesuit\}\) is the same in any sequence in which the cards arrive:
$$C(52, 5) = \frac{52!}{5! 47!} = 2{,}598{,}960$$
Python: itertools.combinations and math.comb
itertools.combinations and math.comb
Python offers two ways to work with combinations: math.comb(n, r)
to compute the formula, and itertools.combinations(iterable, r) to
generate each subset individually.
from itertools import combinations
import math
# math.comb computes C(n, r) directly: fast, without generating all cases
print(math.comb(52, 5)) # 2598960
# itertools.combinations generates each hand: useful to filter by property
# (e.g., how many hands have at least one ace?)
deck = range(52) # 52 cards represented by 0-51
hands = combinations(deck, 5)
print(sum(1 for _ in hands)) # 2598960
# For large n and r, NEVER materialize the iterator into a list:
# use math.comb for the total and combinations() only when you need to inspectitertools.combinations guarantees that each element appears at most once
per subset and that subsets with the same elements in different orders are
treated as equal, exactly the definition of a combination.
Soccer team: 11 players out of 15 #
Problem: A coach needs to pick 11 starters out of 15 available players. How many distinct lineups (ignoring positions) are there?
Solution: Since \(r = 11 > 15/2\), the symmetry property simplifies the calculation, because choosing the 11 who play is equivalent to choosing the 4 who sit out:
$$C(15, 11) = C(15, 4) = \frac{15 \times 14 \times 13 \times 12}{4!} = \frac{32{,}760}{24} = \mathbf{1{,}365}$$Mixed group: 3 men and 2 women out of 6 men and 5 women #
Problem: A committee of 5 people must have exactly 3 men and 2 women. There are 6 men and 5 women available. How many distinct committees can be formed?
Solution: The choices of men and women are independent of each other; therefore, we apply the Product Rule to the two blocks:
$$C(6, 3) \times C(5, 2) = 20 \times 10 = \mathbf{200}$$Sample of 3 parts: at least 1 defective #
Problem: In a lot of 20 parts (5 defective, 15 good), a random sample of 3 parts is drawn. How many samples contain at least 1 defective part?
Solution: Counting the favorable cases directly would require summing three subcases (1 defective + 2 good; 2 defective + 1 good; 3 defective). The complement strategy is more efficient:
$$\text{At least 1 defective} = \text{Total} - \text{No defective}$$$$C(20, 3) - C(15, 3) = 1{,}140 - 455 = \mathbf{685}$$Splitting into equal groups #
Problem: In how many ways can 10 people be split into 2 groups of 5? Consider two cases: (a) unlabeled groups; (b) labeled groups (Group A and Group B).
Solution:
(a) Indistinguishable (unlabeled) groups: we choose who goes to the first group, and the second is automatically determined. Since the groups are equivalent to each other, each split would be counted \(2! = 2\) times if we did not correct for it. We divide by the number of permutations of the \(2\) groups:
$$\frac{C(10,5)}{2!} = \frac{252}{2} = \mathbf{126}$$(b) Labeled groups (Group A and Group B): the split “5 in Group A and 5 in Group B” is different from “5 in Group B and 5 in Group A”. It is enough to choose who goes to Group A, since Group B is the complement:
$$C(10,5) = \mathbf{252}$$Summary Table #
The tables below bring together the three fundamental groupings and the properties specific to combinations established in this article.
Comparison of the groupings:
| Concept | Uses all \(n\)? | Does order matter? | Formula |
|---|---|---|---|
| Permutation | Yes | Yes | \(P_n = n!\) |
| Arrangement | No (\(r \leq n\)) | Yes | \(A(n,r) = \dfrac{n!}{(n-r)!}\) |
| Combination | No (\(r \leq n\)) | No | \(C(n,r) = \dfrac{n!}{r!(n-r)!}\) |
Properties of combinations:
| Property | Formula |
|---|---|
| Relation to arrangement | \(A(n, r) = C(n, r) \cdot r!\) |
| Symmetry | \(C(n, r) = C(n, n-r)\) |
| Extreme cases | \(C(n, 0) = C(n, n) = 1\) |
| Unit cases | \(C(n, 1) = C(n, n-1) = n\) |
Exercises #
The exercises below cover the main techniques of the article: determining \(n\), symmetry, the complement, and the Product Rule. They are ordered from simplest to most complex.
Exercise 1: Determining \(n\)
If \(C(n, 2) = 10\), find \(n\).
Answer
Expanding the formula:
$$\frac{n(n-1)}{2} = 10 \implies n^2 - n - 20 = 0 \implies (n-5)(n+4) = 0$$Since \(n > 0\), we get \(n = 5\).
Exercise 2: Committee with a chair
From 12 people, 3 must be chosen for a committee. In how many ways can the committee be formed if one of the members must be the chair (a distinct role)?
Answer
The chair is a distinct position, and it matters who fills that role. We choose the chair in an ordered way (12 options) and the other 2 members without distinction from the 11 remaining:
$$12 \times C(11, 2) = 12 \times 55 = \mathbf{660}$$
Exercise 3: Grid paths
On a 4×4 grid of points, in how many ways can we go from the bottom-left corner to the top-right corner moving only up or right?
Answer
Every path uses exactly 3 moves up and 3 moves right, for a total of 6 moves. The path is completely determined by choosing which 3 positions (out of the 6) are the “up” move. The figure below shows one of these paths, with the moves numbered in the order they are made:
Each choice of the 3 “up” positions gives a different path, and every path comes from one such choice. Therefore:
$$C(6, 3) = \mathbf{20} \text{ paths}$$
Exercise 4: Points generating lines and triangles
With 10 points in the plane in general position (no 3 collinear), how many distinct lines and triangles can be formed?
Answer
- Lines: each pair of points determines exactly one line: \(C(10,2) = \mathbf{45}\)
- Triangles: each trio of points determines exactly one triangle: \(C(10,3) = \mathbf{120}\)
Exercise 5: Subsets of varying size
How many nonempty subsets of size ≤ 3 can be formed from 7 elements?
Answer
We add up the combinations for each size (Sum Rule):
$$C(7,1) + C(7,2) + C(7,3) = 7 + 21 + 35 = \mathbf{63}$$
Exercise 6: Teams with a restriction
In a class of 6 boys and 4 girls, how many teams of 4 have at least 1 girl?
Answer
By complement:
$$C(10,4) - C(6,4) = 210 - 15 = \mathbf{195}$$Next steps #
The combination \(C(n, r)\) completes the fundamental triad of classical combinatorics: together with the permutation and the arrangement, it covers the vast majority of counting problems with distinct elements.
The limitation of all three tools is exactly this requirement of distinctness: each element can appear at most once. But what happens when there are repetitions? How many anagrams does the word MISSISSIPPI have? How many 7-digit numbers can be formed with the digits \(\{1, 1, 2, 2, 2, 3, 3\}\)?
These problems lead us to permutations with repetition, the topic of the next article in the series.
