Three objects in combinatorics confuse almost everyone at first: permutations, arrangements (k-permutations) and combinations. The distinction really comes down to two questions: does order matter? and are all the elements chosen, or only some? Once these are answered, the formula follows from the product rule and the division rule, with nothing to memorise.
The factorial
The factorial of n, written n!, is the product of the numbers from 1 to n: 5! = 5 · 4 · 3 · 2 · 1 = 120. By convention 0! = 1, which keeps all the following formulas consistent.
The factorial grows faster than any power with a fixed base: 10! = 3,628,800, and 20! already exceeds 2 · 10¹⁸.
Permutations: ordering all the elements
A permutation of n distinct objects is an ordering of them. There are n choices for the first place, n − 1 for the second, and so on down to 1. By the product rule:
P(n) = n!
Example: the 6 permutations of {A, B, C} are ABC, ACB, BAC, BCA, CAB, CBA.
In computing: a comparison-based sorting algorithm must distinguish between n! possible orderings of its input. Since each comparison has two outcomes, at least log₂(n!) comparisons are needed in the worst case, a quantity of order n log n. That is why no comparison sort can do better than n log n.
Arrangements: choosing k elements in order
An arrangement (or k-permutation) of n objects taken k at a time is an ordered sequence of k distinct objects chosen from n. The product rule stops after k factors:
P(n, k) = n · (n − 1) · … · (n − k + 1) = n! / (n − k)!
Example: in a race with 8 competitors, the possible podiums (gold, silver, bronze) number 8 · 7 · 6 = 336.
Combinations: choosing k elements without order
A combination of n objects taken k at a time is a k-element subset, without order. Each combination corresponds to k! different arrangements (the ways of ordering the k chosen elements). By the division rule:
C(n, k) = P(n, k) / k! = n! / (k! (n − k)!)
This number is called the binomial coefficient and is read "n choose k".
Example: the groups of 3 people that can be formed from 8 number 336 / 6 = 56. The podium has 336 cases because order matters; a 3-person committee has 56 because it doesn't.
A scheme for choosing
| Question | Order matters | Order doesn't matter |
|---|---|---|
| All n elements | permutations, n! | a single choice |
| k of n elements, no repetition | arrangements, n!/(n−k)! | combinations, C(n, k) |
| k of n elements, with repetition | nᵏ | C(n + k − 1, k) |
The last row concerns choices where the same element may appear several times: nᵏ is the number of strings of length k over an n-symbol alphabet, while C(n + k − 1, k) counts combinations with repetition, which deserve a discussion of their own.
Properties of the binomial coefficient
- Symmetry: C(n, k) = C(n, n − k). Choosing who is in is the same as choosing who stays out.
- Pascal's rule: C(n, k) = C(n − 1, k − 1) + C(n − 1, k). Fix one element: either it is chosen (leaving k − 1 choices among n − 1) or not (leaving k choices among n − 1).
- Row sum: C(n, 0) + C(n, 1) + … + C(n, n) = 2ⁿ, the number of all subsets of an n-element set.
Pascal's rule generates Pascal's triangle (known in Italy as Tartaglia's triangle), in which each number is the sum of the two above it:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Row n contains the coefficients of the expansion of (a + b)ⁿ: for example (a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴. This is the binomial theorem, which gives these coefficients their name.
Computing them without overflow
Computing C(n, k) as n! / (k!(n − k)!) produces huge intermediate numbers. It is better to multiply and divide one step at a time, using the fact that every partial result is an integer:
def binomial(n, k):
k = min(k, n - k)
r = 1
for i in range(1, k + 1):
r = r * (n - k + i) // i
return r
Python also provides math.comb(n, k), which does the same job.
A realistic example
A lottery draws 6 numbers out of 90, without order. The possible combinations number C(90, 6) = 622,614,630. Someone playing a single combination therefore has a chance of matching all six of one in more than 622 million. If the order of the draw mattered, there would be 6! = 720 times as many cases.
In short
- First question: does order matter? Second: are all elements chosen, or only k?
- Permutations: n!; arrangements: n!/(n − k)!; combinations: n!/(k!(n − k)!).
- Combinations come from arrangements by dividing by k!, the ways of ordering the k chosen.
- Pascal's triangle arises from Pascal's rule and gives the coefficients of (a + b)ⁿ.
- To compute C(n, k), alternate multiplications and divisions rather than using full factorials.
