1
Divide by r! to forget the order
Each r-subset arises from exactly r! ordered selections, so C(n,r) = P(n,r)/r!.
Lesson · Combinatorics and Counting · Arrangements
Combinations
C(n, r) = n!/(r!(n−r)!) counts subsets of size r. It is P(n, r) divided by r!, because each subset was counted once for every order of its elements.
C(n, r) = P(n, r)/r! = n!/(r!(n−r)!)
C(n, r) = C(n, n−r) symmetry: choosing r is leaving n−r
C(n, 0) = C(n, n) = 1
Σ_r C(n, r) = 2ⁿ all subsets
Unordered, no repetition
Core ideas
What this lesson establishes
One formula, derived from permutations by dividing out the orderings that do not matter.
2
Symmetry is obvious once seen
Choosing which r to include is the same as choosing which n−r to leave out, so C(n,r) = C(n,n−r).
3
The subsets sum to 2ⁿ
Every subset has exactly one size, so summing C(n,r) over all r counts every subset once — and “Subsets and Power Sets” in Sets, Relations, and Functions already knew the total.
The material
Choosing without order
The derivation, the identities, and the standard applications.
Definition · Combination
An r-combination of a set is a subset of size r. The number of them is written C(n, r) or binom(n, r) and read "n choose r".
Theorem · Counting combinations
C(n, r) = P(n, r)/r! = n!/(r!(n−r)!) for 0 ≤ r ≤ n.
Count ordered selections of r distinct objects in two ways. Directly there are P(n, r) of them.
Alternatively, choose which r objects to use (C(n, r) ways) and then arrange them (r! ways), giving C(n, r) · r!.
The two counts are of the same set, so P(n, r) = C(n, r) · r!, and dividing gives the formula.
□
That proof is a double count: one set counted two ways, and the two expressions therefore equal. “Combinatorial Proof” makes the technique explicit; it appears here because it is the cleanest derivation of the formula.
Theorem · Symmetry
C(n, r) = C(n, n−r).
The map sending a subset to its complement is a bijection between the r-subsets and the (n−r)-subsets: it is injective because a set is determined by its complement, and surjective because every (n−r)-subset is the complement of its own complement.
□
The bijective proof is better than the algebraic one, which merely observes that the formula is symmetric in r and n−r. A bijection says why: the two collections are the same objects, described from opposite sides.
Theorem · Sum over all sizes
Σ_{r=0}^{n} C(n, r) = 2ⁿ.
Count the subsets of an n-set two ways. By size: C(n, r) of each size r, and every subset has exactly one size, so the total is the sum. Directly: each element is independently in or out, giving 2ⁿ.
□
Example · Poker hands
A 5-card hand from 52 is C(52,5) = 2 598 960, since the order cards arrive in does not matter. Hands containing all four aces: choose the four aces (1 way) and one more card from 48, giving 48. So the probability is 48/2598960 ≈ 0.0000185 — Discrete Probability makes that division legitimate.
Example · Lattice paths
Paths from (0,0) to (m,n) using unit steps right and up: each path is a sequence of m + n steps of which m are right, so there are C(m+n, m) of them. Choosing which steps are right determines the path completely.
Interactive
The four counting rules
Enumerated while enumeration is possible
Method
Recognising a combination
Order and repetition, in that order.
1
Ask whether order matters
Committees, hands and subsets: no. Podiums, passwords and sequences: yes. This one question separates “Permutations” and “Combinations”.
2
Ask whether repetition is allowed
If objects may be chosen more than once, “Combinations with Repetition” applies instead.
3
Use symmetry to simplify
C(20,18) = C(20,2) = 190. Computing the smaller side is faster and less error-prone.
4
Check with a small case
C(4,2) = 6 should match the six pairs you can list. The lab does this automatically up to 400 selections.
Combinations
Score 0 / 0Choose the answer you can justify.
Committees with structure
From 8 mathematicians and 6 physicists, choose 5 with at least 3 mathematicians.
Cases by the number of mathematicians — disjoint and exhaustive:
3 maths, 2 physicists: C(8,3)·C(6,2) = 56 · 15 = 840
4 maths, 1 physicist: C(8,4)·C(6,1) = 70 · 6 = 420
5 maths, 0 physicists: C(8,5)·C(6,0) = 56 · 1 = 56
total = 840 + 420 + 56 = 1316
Sanity check: total committees of 5 from 14 is C(14,5) = 2002,
and 1316 < 2002. ✓
Within each case the product rule applies because the two choices are independent: which mathematicians are chosen does not change how many ways the physicists can be. The sum rule then combines the cases, which are disjoint because a committee has one definite composition.
Common mistakes
1
Using C where order mattersA three-digit code is not a three-element subset. Ask what makes two outcomes different before choosing a formula.
2
Adding when the choices are simultaneous"3 mathematicians AND 2 physicists" is a product within a case. The sum rule combines the cases, not the parts of one case.
3
Computing the large side of a symmetric coefficientC(30,28) is C(30,2) = 435, which is two multiplications rather than twenty-eight.
Check your understanding
✓
Finish when you can combine C with cases and with the complement.
Count the 5-card hands that contain at least two aces, by cases (exactly two, three or four aces) and by complement (all hands minus those with no ace minus those with exactly one). Each case is a product C(4, k) · C(48, 5 − k); say why the two choices in it are independent, and why the cases are disjoint. The two totals must agree, and the poker example above fixes the magnitude.
Note: C(n, r) is also written binom(n, r) and called a binomial coefficient, because “The Binomial Theorem” shows it is the coefficient of x^r y^{n−r} in (x + y)ⁿ. The two facts — counting subsets and expanding a power — are the same fact.