Classical probability is favorable outcomes divided by total outcomes (see Probability Fundamentals). The catch is that both counts can be enormous, and listing them by hand is hopeless. Combinatorics is the art of counting outcomes without writing them all down.
When you select items, ask: does the order matter? If reordering the same items counts as a new outcome (a podium, a password), it is a permutation. If it does not (a committee, a lottery ticket), it is a combination. That single question routes you to the right formula every time.
The Multiplication Principle
The most fundamental rule: if a task is a sequence of independent choices with n₁, n₂, n₃, ... options at each step, the total number of outcomes is their product.
Two starters, then three mains for each: 2 × 3 = 6 meals. The principle scales without effort, a 4-digit PIN is 10⁴ = 10,000 possibilities, and a plate of 3 letters then 3 digits is 26³ × 10³ = 17,576,000. Each independent slot simply multiplies in its own count.
Permutations: When Order Matters
A permutation is an ordered arrangement. Arranging all n distinct items gives n! orderings; selecting and ordering r of them gives:
P(n, r) = n! / (n - r)!
Awarding gold, silver, and bronze among 8 runners is P(8, 3) = 8 × 7 × 6 = 336: the first medal has 8 candidates, then 7 remain, then 6. Arranging all of something is the special case P(n, n) = n!. By convention 0! = 1, which keeps every formula consistent.
Combinations: When Order Does Not
A combination is an unordered selection. Because order is ignored, each group is counted once. The clean way to see it: a combination is a permutation with its r! reorderings divided out.
Choosing 2 of {A, B, C} gives 6 ordered pairs but only 3 actual pairs, because AB and BA are the same selection. That is the whole story of C(n, r) = n! / (r! (n - r)!), read "n choose r": take the permutations and divide away the r! ways to reorder each group.
Counting for Probability
Now the payoff. Classical probability is just favorable outcomes over total outcomes, and the tools above count both. First, the decision guide that picks your tool:
The lottery is a pure combination: choosing 6 numbers from 49 ignores order, so there are C(49, 6) = 13,983,816 possible tickets, and one ticket wins the jackpot with probability about 1 in 14 million. A poker flush is favorable-over-total counting: pick a suit and then 5 of its 13 cards, 4 × C(13, 5) = 5,148 hands, out of C(52, 5) = 2,598,960, so P(flush) ≈ 0.00198, about 1 in 505.
Where the combinations live: Pascal's triangle
Every combination C(n, r) is an entry of Pascal's triangle, and row n holds the coefficients of (a + b)ⁿ. That link is exactly why C(n, r), the number of ways to get r successes in n trials, drives the binomial distribution in the chapters ahead.
Pascal documented this triangle in 1653, but it was known centuries earlier to Pingala in India, and later to al-Karaji, Omar Khayyam, and Yang Hui, a reminder that mathematics is rarely the work of one name. For data science, counting underpins the binomial and hypergeometric distributions, the combinatorics of sampling, and the feature-interaction counts that explode model complexity. Counting cleanly is a quiet superpower.
Counting in Machine Learning & AI
Counting is not just for cards and lotteries. The same three tools quietly govern how machine-learning systems are built, why some are expensive, and where brute force has to give way to clever search.
The clearest example is the combinatorial explosion. Deciding which of n features to feed a model is a combinations problem: there are 2ⁿ possible subsets in total. With just 20 features that is already over a million, so you can never simply "try them all":
That single picture is the famous curse of dimensionality, and it is why feature selection, neural architecture search, and hyperparameter tuning all rely on smart shortcuts rather than enumeration. Here is where the chapter's three tools show up across machine learning:
| Counting tool | In ML / AI it appears as | A concrete number |
|---|---|---|
| Multiplication principle | The size of a hyperparameter grid; counting a network's parameters | 3 rates × 4 depths × 5 trees = 60 models to train |
| Combinations, 2ⁿ | Feature subsets, cross-validation folds, ensemble samples | 20 features → 2²⁰ ≈ 1,048,576 subsets |
| Binomial coefficient C(n, k) | The binomial behind naive Bayes and logistic likelihoods, and significance tests | ways to get k of n predictions right by chance |
| Pairs, C(n, 2) | Self-attention comparing every pair of tokens; similarity matrices | 512 tokens → C(512, 2) ≈ 130,816 pairs |
| Permutations, n! | Permutation feature importance, permutation tests, sequence orderings | shuffling a column among its n! possible orders |
Two ideas above are worth pausing on. Attention is pairwise: a Transformer compares all C(n, 2) ≈ n²/2 pairs of tokens, so doubling the context length roughly quadruples the work, which is exactly why long-context models are costly and "efficient attention" is a hot research area. And combinatorial explosion (2ⁿ feature subsets, branching game trees, Go's roughly 10¹⁷⁰ positions) is the reason modern AI learns to search instead of enumerating: when you cannot count your way through the space, you must approximate it. Counting tells you when brute force is doomed, which is half of knowing what to do instead.
Count it in Python
The companion notebook uses math.factorial, math.perm, and math.comb
alongside itertools to verify every count by enumeration: the multiplication principle,
permutations and factorials, combinations (and the C = P / r! relationship), the lottery and poker
probabilities, and Pascal's triangle drawn out to row 8.
View opens the rendered notebook instantly (no setup). Open in Colab runs &
edits it live in your browser. To run locally, install numpy and matplotlib and launch
jupyter notebook.
🎓 Key Takeaways
- ✓Multiplication principle: a sequence of independent choices multiplies, n₁ × n₂ × n₃ ...
- ✓Permutation (order matters): P(n, r) = n! / (n - r)!; arrange all n in n! ways.
- ✓Combination (order ignored): C(n, r) = n! / (r! (n - r)!) = P(n, r) / r!.
- ✓Ask "does order matter?" to pick permutation vs combination, every time.
- ✓Counting feeds probability: favorable / total, both counted; Pascal's triangle holds every C(n, r) and powers the binomial.
- ✓Counting shapes ML/AI: hyperparameter grids multiply, feature subsets explode as 2ⁿ, attention compares C(n, 2) token pairs, the reason AI learns to search rather than enumerate.
Practice Challenges
Five short challenges, beginner to intermediate. Try them on paper or in Python before checking the solutions.
Count the menus
A cafe offers 4 mains, 3 sides, and 5 drinks. How many distinct meals (one of each)? And if you add a choice of 2 desserts?
Officers (order matters)
From a club of 10 members, how many ways to choose a President, Vice-President, and Treasurer (distinct roles)?
Committee & handshakes
From the same 10 members, how many 3-person committees (equal roles)? And how many handshakes if all 10 shake hands once?
Which one?
Decide order-matters-or-not and compute: (a) a 4-letter password from 26 letters, no repeats; (b) choosing 4 pizza toppings from 12.
Counting for probability
From a 52-card deck, what is the probability a 5-card hand is exactly four-of-a-kind (four of one rank plus any fifth card)?
A fully-worked solutions notebook walks through all five challenges, with each count verified in code. Try them yourself first, then compare.
Quiz: Test Yourself
Eight quick questions on counting and combinatorics. Answer them, hit Check Answers, and keep refining until you score 100%. Your progress is saved, so you can hop back to the chapter and return anytime.