How many 8-character passwords are there? In how many ways can 10 people sit around a table? How many subsets does a set with 20 elements have?
These questions look simple until trying to list the cases one by one reveals the astronomical scale of the possibilities. This is where combinatorics comes in: the mathematics of counting efficiently.
Why does counting matter? #
In computing and mathematics, counting discrete objects shows up everywhere:
- Security: the strength of a password depends on the number of possible combinations
- Algorithms: complexity analysis often involves counting paths or subsets
- Probability: computing probabilities requires knowing the number of favorable cases and the total
- Optimization: many problems involve picking the best among many possible configurations
Combinatorics provides the tools to answer these questions exactly and efficiently, without listing everything.
The roadmap of this series #
This series covers the foundations of combinatorics in increasing order of complexity. Each article brings precise definitions, worked examples and exercises with commented solutions.
The Sum Rule and the Product Rule #
The starting point. The sum rule counts mutually exclusive situations (“or”) by adding. The product rule counts independent steps (“and”) by multiplying. All of combinatorics rests on these two rules.
→ The Sum Rule and the Product Rule
Simple and Circular Permutations #
When we want to order all the elements of a set. In a row: \(P_n = n!\). In a circle: \(PC_n = (n-1)!\). Includes examples with restrictions (blocks, alternations, separations).
→ Simple and Circular Permutations
Simple Arrangements #
Ordered selections of only \(r < n\) elements, also called r-permutations. The formula \(A(n,r) = \dfrac{n!}{(n-r)!}\) shows up in podiums, routes and license plates.
Simple Combinations #
Unordered selections of \(r\) elements out of \(n\). The formula \(C(n,r) = \binom{n}{r}\) solves problems about committees, card hands and samples. Order does not matter, only who was chosen.
Permutations with Repetition #
What if the elements are not all distinct? The formula \(\dfrac{n!}{n_1! n_2! \cdots n_r!}\) adjusts the count by dividing out the overcounting. Applied to anagrams, binary sequences and lattice paths.
→ Permutations with Repetition
Arrangements with Repetition #
Ordered selections with repetition allowed: \(AR(n,r) = n^r\). Here \(r\) can be larger than \(n\). Shows up in passwords, number representation in computers and any sequence where symbols repeat.
→ Arrangements with Repetition
Combinations with Repetition #
Unordered selections with repetition: \(CR(n,r) = \binom{n+r-1}{r}\). The stars and bars method reveals the equivalence with non-negative integer solutions of equations.
→ Combinations with Repetition
Binomial Coefficients and Pascal’s Triangle #
The identities of the coefficients \(\binom{n}{r}\): symmetry, Pascal’s rule, the row theorem (\(\sum \binom{n}{k} = 2^n\)) and the column theorem. Pascal’s Triangle as the visual structure of these relations.
→ Binomial Coefficients and Pascal's Triangle
The Binomial Theorem #
The theorem that joins algebra and combinatorics: \((a+b)^n = \sum_{r=0}^{n}\binom{n}{r}a^{n-r}b^r\). Includes the general term formula, examples of extracting specific coefficients and proofs of identities by substitution.
What comes before and after #
This series is part of a larger sequence on Discrete Mathematics:
- Before: The Language of Sets and From Base Case to Infinity, on set theory and mathematical induction
- After: The Mathematics of Connections, on graph theory
Each series can be read on its own, but the progression was planned to build intuition gradually.
Quick Reference Table #
The topics covered throughout the series, with their main formulas, for quick reference:
| Technique | Order matters? | Repetition? | Formula |
|---|---|---|---|
| Sum rule | n/a | n/a | \(|A| + |B|\) (disjoint) |
| Product rule | n/a | n/a | \(|A| \cdot |B|\) |
| Simple permutation | Yes | No | \(n!\) |
| Circular permutation | Yes | No | \((n-1)!\) |
| Permutation w/ repetition | Yes | Yes (identical) | \(\dfrac{n!}{n_1!\cdots n_k!}\) |
| Simple arrangement | Yes | No | \(\dfrac{n!}{(n-r)!}\) |
| Arrangement w/ repetition | Yes | Yes | \(n^r\) |
| Simple combination | No | No | \(\dbinom{n}{r}\) |
| Combination w/ repetition | No | Yes | \(\dbinom{n+r-1}{r}\) |
When the problem is choosing \(r\) elements out of \(n\), two questions decide the formula: does order matter? Is repetition allowed? The figure below arranges the four answers in a grid and shows each case choosing 2 letters from \(\{a, b, c\}\):
Enjoy the reading!
