Combinatorics
Counting without listing every case. How many podiums, passwords, card hands, handshakes? Four formulas are enough, and two questions decide between them: does order matter, is repetition allowed? The whole chapter lives in that one reflex.
0The symbols
Few signs, but each one encodes a precise counting situation. Here is the dictionary.
| Symbol | Meaning |
|---|---|
| n! | "n factorial": the product 1 · 2 · 3 ⋯ n. The number of ways to order n distinct objects. |
| 0! = 1 | An indispensable convention: there is exactly one way to order zero objects, namely doing nothing. |
| Pₙ | The permutations of n objects: Pₙ = n!. All the objects, each one once, order matters. |
| Aₙᵏ | The arrangements (k-permutations of n): k objects drawn from n, without replacement, taking order into account. |
| Cₙᵏ | The combinations: k objects chosen from n, without replacement, without order. Also read as "n choose k". |
| (ⁿₖ) | The binomial coefficient: the same thing as Cₙᵏ, in matrix dress. It is what populates Pascal's triangle. |
| nᵏ | Draws with replacement and with order: k successive choices out of n possibilities each time. |
| · | The multiplicative principle: successive steps multiply. The chapter's great, silent engine. |
| + | The additive principle: mutually exclusive cases add up. Valid only without overlap. |
| (a + b)ⁿ | The binomial theorem: its expansion is written out in advance by the binomial coefficients. |
1The two principles
Every formula in this chapter is built from two elementary moves: multiplying steps, adding cases.
1.1 · Multiplying steps
When an experiment unfolds in successive steps whose number of choices does not depend on earlier steps, the total is the product of the choices at each step.
Because every outcome of the first step opens the same range of options at the second: the tree has m branches, and each one splits into n. Counting the leaves means multiplying.
The number of choices must be the same at every branch; the choices themselves may differ.
1.2 · Adding cases
When outcomes fall into families that do not overlap, count each family and add them up.
2Factorial and permutations
2.1 · n! and permutations
Ordering n distinct objects means filling n places: n choices for the first, n − 1 for the second, and so on down to 1.
The multiplicative principle does the rest: n · (n − 1) ⋯ 1 = n!.
Why is 0! = 1 and not 0? Because an empty product equals 1, just as an empty sum equals 0. And because the formulas demand it: Cₙⁿ = n!/(n! · 0!) must equal 1, since there is only one way to take everything.
Factorials explode fast: 10! already comes to 3,628,800, and 20! exceeds what an ordinary calculator can hold. That is the sign that listing everything by hand is hopeless, and that formulas earn their keep.
2.2 · Anagrams: permutations with repetition
When objects are indistinguishable from one another (think of the three A's in ANANAS, French for pineapple), swapping these twins around changes nothing.
So we count n! as though everything were distinct, then divide by the k! of each group of twins.
The lab counts the anagrams of any word: it groups the letters, writes out the division and, when the list stays short, lists the anagrams for real.
3Arrangements
An arrangement is an ordered draw: k places to fill with objects taken from n.
Without replacement, the range of choices shrinks at every place: n, then n − 1, down to n − k + 1. With replacement, it stays at n for every place: nᵏ.
In practice, the form n!/(n − k)! is almost never used directly: you write the descending product straight away, k factors starting from n.
A₁₀³: three factors starting from 10, namely 10 · 9 · 8. Done before you have even reached for a calculator.
4Combinations
A combination is an unordered draw: you choose a bundle of k objects out of n, and the bundle has no first place.
Start from the arrangement Aₙᵏ, then divide by k!: each bundle was counted there once for every order it could appear in.
Choosing the k objects you take is exactly the same as choosing the n − k you leave behind. Two descriptions of the same move, hence the same number.
This is the chapter's signature argument: count the same thing two ways. No calculation needed, and the formula falls out on its own.
Pick out one star object among the n. Every choice of k objects either contains it (leaving k − 1 to take from n − 1) or leaves it out (leaving k to take from n − 1).
Two disjoint cases, additive principle: Pascal's rule. It is what generates the triangle in the next lab.
5The draw factory
The four formulas side by side, applied to real objects. Choose n, k and the drawing mode: the machine writes out the formula, gives the total, and lists the draws themselves for as long as they fit on screen.
Compare the four modes at fixed n and k: same letters, four different worlds. Watch ABC and BCA merge into one the moment order stops mattering.
6Pascal's triangle and the binomial theorem
Arrange the Cₙᵏ into a pyramid: each cell is the sum of the two cells above it, Pascal's rule turned into a picture. Click a cell: its two parents light up, along with its symmetric twin.
Expanding (a + b)ⁿ means distributing across n parentheses: every term of the result picks a or b from each one. A term aⁿ⁻ᵏbᵏ appears exactly as many times as there are ways to choose the k parentheses that contribute b.
That number is Cₙᵏ. The binomial theorem is not an algebra formula with a dash of combinatorics thrown in: it is combinatorics, pure and simple. And row n of the triangle gives 2ⁿ once you set a = b = 1: the number of subsets of an n-element set.
7The method
The central reflex fits into a square with two questions. It picks the formula for you.
8The six mistakes
9Test yourself
Eight questions, exactly one correct answer each time. The explanation appears right after your choice.
10The vocabulary in French and German
This formulary comes from Swiss upper-secondary schools (Gymnasium), where it is taught in both French and German. Here are its terms in their original languages, side by side.
| Français | Deutsch |
|---|---|
| l'analyse combinatoire / le dénombrement | die Kombinatorik / das Abzählen |
| la factorielle | die Fakultät |
| la permutation | die Permutation |
| l'arrangement | die Variation |
| la combinaison | die Kombination |
| le coefficient binomial | der Binomialkoeffizient |
| « n choisir k » | «n über k» |
| avec / sans répétition | mit / ohne Wiederholung |
| avec / sans remise | mit / ohne Zurücklegen |
| l'ordre compte | die Reihenfolge zählt |
| le principe multiplicatif | das Produktprinzip |
| le principe additif | das Summenprinzip |
| des cas disjoints | disjunkte Fälle |
| le complémentaire | das Komplement |
| l'anagramme | das Anagramm |
| indiscernable | ununterscheidbar |
| le triangle de Pascal | das Pascalsche Dreieck |
| la formule de Pascal | die Pascalsche Formel |
| le binôme de Newton | der binomische Lehrsatz |
| le développement | die Entwicklung |
| le sous-ensemble | die Teilmenge |
| l'arbre de dénombrement | das Zählbaumdiagramm |
| énumérer | aufzählen |
| le tirage | die Ziehung |