Probability starts with counting: the chance of something is often the number of ways it can happen divided by the number of ways anything can happen. Listing every possibility works for three or four, and fails long before a hundred. A handful of counting rules give the number at once: multiply the choices, use a factorial for orderings, divide out repeats for groups. They also explain some hard facts about AI: why a language model can never consider every possible sentence, and why attention, which compares every word with every other, gets expensive as text gets longer. This lesson builds the rules from slots, checks them in Python, and applies them to those two questions.
What you'll be able to do
Count possibilities by filling slots left to right and multiplying the choices
Count orderings with factorials, ordered picks with n!/(n − r)!, and groups with n!/(r!(n − r)!)
Count with math.factorial, math.perm and math.comb, and confirm small cases with a loop
See why a model can't try everything: sentences grow like vⁿ, and attention's table of scores like n², in Python and PyTorch
Quick check
Have a guess before you start. A camp menu has 3 breakfasts and 4 dinners. How many different breakfast-and-dinner days are there?
34
12
7
3
Show the answer
12
Each of the 3 breakfasts can go with each of the 4 dinners: 3 × 4 = 12.
The math: fill the slots, multiply
Purpose. Know how many possibilities there are without listing them.
The counting principle. When a choice is made in steps, the number of outcomes is the product of the number of choices at each step. Fill the slots left to right:
ways=n1×n2×⋯×nk
In plain words: for each way of filling the first slot, there are n₂ ways to fill the second, and so on.
A 4-digit PIN has 10 choices per slot: 10 × 10 × 10 × 10 = 10⁴ = 10,000. A code of 3 letters then 2 digits has 26 × 26 × 26 × 10 × 10 = 1,757,600.
Quick check
From lesson 10: what is 2¹⁰?
20
1,024
100
512
Show the answer
1,024
2 × 2 × … ten times = 1,024. It's also the number of yes-or-no answer sheets for 10 questions: two choices per slot.
When choices shrink. Choosing a gold, silver and bronze winner from 5 hikers, A to E: 5 choices for gold, then 4 left for silver, then 3 for bronze.
The picture. Step through the slots two ways at once: as boxes of numbers, and as a tree of choices that grows left to right, one column per slot. A ? is a slot still to fill. At each step the top branch splits once for every hiker who could take the next place. The whole tree would have 60 ends, too many to draw, so a box such as +3 stands for 3 more choices that branch the same way.
Try it now
Then set the choices for each place to 5, 4, 3, 2, 1 and press Use these numbers: every hiker in a line, 5! = 120 orders, and the tree grows two more columns.
Symbols and formula. Three counts come up again and again:
n!=n×(n−1)×⋯×1P(n,r)=(n−r)!n!C(n,r)=r!(n−r)!n!
In plain words: n! ("n factorial") orders all n things; P(n, r) picks r of them in order; C(n, r) ("n choose r") picks r of them as a group, ignoring order.
5 hikers in a line: 5! = 120. Gold, silver, bronze: P(5, 3) = 60. A team of 3: C(5, 3) = 10. Each group of 3 can be ordered in 3! = 6 ways, so the ordered count, 60, counts every group 6 times: 60 ÷ 6 = 10. Dividing out the repeats is where the r! comes from: one pair in two orders is still one pair.
Quick check
How many ways can 4 tent spots be assigned to 4 groups, one each?
4
24
16
256
Show the answer
24
4 choices for the first spot, 3 for the next, then 2, then 1: 4! = 24.
Quick check
A committee of 2 is picked from 6 people. How many committees are possible?
12
30
36
15
Show the answer
15
Ordered picks: 6 × 5 = 30. Each committee was counted twice (A then B, B then A): 30 ÷ 2 = 15.
In your own words
In your own words: why is a group of r counted r! times among the ordered picks?
Write a sentence or two, then compare it with a good answer in the lesson.
In Python: count, then confirm by listing
Purpose. Compute counts with one call, and check small ones by listing every case.
It runs right here in your browser, with nothing to install.
math.factorial(n) is n!, math.perm(n, r) is ordered picks, and math.comb(n, r) is groups. For small cases, a loop that lists every possibility is the best check that the right formula was chosen.
Code flow. Here is that check for 3 items, numbered 0, 1 and 2, taken two at a time. First the formulas count, then two loops list. Step through and watch the two lists fill: a pair goes into ordered whenever its two items differ (i ≠ j), but into groups only in one order (i < j).
The loops list 6 ordered pairs and 3 groups, the same two counts the formulas printed first. Each group shows up twice in ordered, once in each order. The same check for 4 items, counting instead of listing:
items = ["tent", "tarp", "stove", "map"]
ordered = 0
groups = 0for i inrange(len(items)):
for j inrange(len(items)):
if i != j:
ordered = ordered + 1if i < j:
groups = groups + 1print(ordered, groups)
12 ordered pairs and 6 groups: math.perm(4, 2) and math.comb(4, 2) agree.
A named mistake: perm for comb. "How many teams" means order doesn't matter: math.comb. "How many ways to pick a captain and a vice-captain" means it does: math.perm. Asking "would swapping two picks give a different answer?" decides which. Using perm for a team overcounts by r!.
Worked example
Worked example: count and verify four cases
Compute four counts with the formulas, and confirm the smallest by listing.
import math
pins = 10 ** 4
lineups = math.factorial(6)
podiums = math.perm(8, 3)
teams = math.comb(8, 3)
print(pins, lineups, podiums, teams, podiums // teams)
count = 0for a inrange(5):
for b inrange(a + 1, 5):
for c inrange(b + 1, 5):
count = count + 1print(count, math.comb(5, 3))
In the lesson you can change this and run it.
10,000 PINs, 720 line-ups of 6, 336 podiums from 8 and 56 teams of 3 from 8. podiums ÷ teams = 6 = 3!: each team is counted 6 times among the podiums. The three nested loops list every group of 3 from 5 in increasing order, a < b < c, so each group appears exactly once: 10, matching math.comb(5, 3).
Quick check
What does this print?
import math
print(math.perm(6, 2), math.comb(6, 2), math.factorial(4))
36 15 24
15 30 24
30 15 10
30 15 24
Show the answer
30 15 24
Ordered pairs from 6: 6 × 5 = 30. Groups of 2: 30 ÷ 2 = 15. 4! = 24.
Drill
Pairs, two ways
Fix the loop so pairs counts each unordered pair of the 6 items exactly once. Then set formula to the same count from math.comb, and ordered to the ordered count from math.perm.
import math
pairs = 0for i inrange(6):
for j inrange(6):
pairs = pairs + 1
formula = 0
ordered = 0print(pairs, formula, ordered)
In the lesson, your code is checked as you write it.
In your own words
How do you decide between math.perm and math.comb for a counting question?
Write a sentence or two, then compare it with a good answer in the lesson.
In AI and ML: why a model can't try everything
Purpose. Counting shows where brute force runs out.
Sentences. A language model with a vocabulary of v words could write vⁿ different sentences of n words: n slots, v choices for each. Here is one entry from the trail club's camp log. .split() cuts it into words, and set(log) keeps one copy of each word (lesson 28): the log's vocabulary.
log = "the fire was warm and the tent was dry so we all slept well".split()
v = len(set(log))
print(len(log), v)
for n in [1, 2, 3, 4, 5]:
print(n, v ** n)
The entry has 14 words but only 12 different ones. From those 12 words you could write 12 one-word sentences, 144 of two words, 1,728 of three and 248,832 of five.
The picture. The same counts as bars, first for 1 to 3 words, then for 1 to 5 on one scale. Keep your eye on the 3-word bar when you press Next.
Ten-word sentences from the same 12 words number about 62 billion (12¹⁰). Real vocabularies have 50,000 or more words, so a model can never check every sentence; it builds one word at a time instead (lesson 91).
sentences=vnpairs of words=2n(n−1)
In plain words: sentences grow exponentially with length; pairs grow with the square of the length.
Attention's cost. A transformer's attention compares every word with every other word in its input. For n words that's n(n − 1)/2 pairs: 45 for 10 words, 4,950 for 100, and 499,500 for 1,000. Ten times the text means about a hundred times the comparisons.
Quick check
What does this print?
pairs = []
for n in [10, 100, 1000]:
pairs.append(n * (n - 1) // 2)
print(pairs)
[45, 4950, 499500]
[90, 9900, 999000]
[45, 450, 4500]
[100, 10000, 1000000]
Show the answer
[45, 4950, 499500]
n(n − 1)/2 pairs: each word paired with every other, counted once. Ten times the words gives about a hundred times the pairs.
In PyTorch. A real attention layer keeps its comparisons in a table of scores, a row for each word and a column for each word it looks at: T × T numbers for a text of T words. torch.ones(T, T) makes a table that size (every entry 1, standing in for a score), and .numel() counts its entries. Here it is for the camp-log entry:
import torch
log = "the fire was warm and the tent was dry so we all slept well".split()
T = len(log)
pairs = T * (T - 1) // 2
scores = torch.ones(T, T)
print(T, pairs, scores.shape, scores.numel())
print(2 * pairs + T)
The table holds 196 numbers for 14 words, and the plain-Python line under it gives the same 196: every pair in both orders plus each word with itself, 2 × 91 + 14. So the table grows like the pairs, with the square of the length. The math part's flow has a PyTorch tab built the same way: torch.ones([5, 4, 3]) (a list of sizes works as well as separate numbers) has one axis per slot and one entry per way, and .numel() multiplies 5 × 4 × 3 = 60.
Why this matters in practice. Doubling a model's context length roughly quadruples the work attention does, which is why long-context models need special tricks to stay affordable. And since sentences can't be listed, generating text is always a matter of choosing well, step by step, among the next word's options. With a vocabulary of 50,000 words, a sentence of 10 words has 50,000¹⁰ possible versions, about 10⁴⁷: a 1 followed by 47 zeros. Even a computer scoring a billion sentences a second would need far longer than the age of the universe to score them all. So no model tries. Search methods such as beam search keep a few of the best partial sentences, say 4, so each step scores 4 × 50,000 = 200,000 options rather than every complete sentence. Counting gives the size of a search before you write any code, and tells you whether "try them all" is a plan or a fantasy.
Drill
Sentences and pairs
For a vocabulary of 12 words, set sentences to the number of sentences of lengths 3, 5 and 10, as a list. Then set pairs to the number of word pairs in texts of 10, 100 and 1,000 words, as a list, and ratio to pairs for 1,000 words divided by pairs for 100, rounded to 1 place.
31Formulas with fractions: clear them firstFreeClearing denominators, cross-multiplying, a letter in the bottom, and reciprocal formulas like 1/R = 1/R₁ + 1/R₂.35 min
37Inverse functions, lines and scalingFreeUndoing a function by making x the subject, domains that allow it, line forms, and unscaling predictions.40 min
38Sequences and sums: find n, a, d and rFreeEvery letter of the arithmetic and geometric formulas as the subject, and an average's window from its decay.40 min
40Review: rearrange anything (algebra)FreeBroken rearrangements to fix, mixed practice from the whole algebra block, a strategy chart, and its formula sheet.35 min
41Coordinates and distanceFreePoints as (x, y), Pythagoras, distance in any number of coordinates, and nearest neighbors.42 min
42Angles, degrees and radiansFreeMeasuring a turn, converting units, arcs, and the angle between two arrows.36 min
43Sine and cosineFreeAcross and up: right triangles, the unit circle, and directions and rotations.42 min
44Waves: height, speed and shiftFreeAmplitude, period and phase, sampling a wave, and position codes in transformers.37 min
68Vector equations: rearranging with arrowsFreeSolving for a vector or a scale, recovering a gradient from two weight snapshots, and an angle from a dot product.40 min
87Counting: choices, orders and groupsFreeThe counting principle, factorials, ordered picks and groups, and why attention's cost grows with the square of the length.43 min
88Probability: from counts to chancesFreeEqually likely outcomes, the complement, distributions, seeded simulation, and a next-word model.43 min
89Combining events: and, or, independentFreeThe or rule, independence, probability trees, drawing with and without replacement, and chains of steps.42 min
100Maximum likelihoodFreeLikelihoods as products, log-likelihoods as sums, grid search, underflow, and the negative log-likelihood loss.45 min
101Linear regression: the best lineFreeResiduals, least squares by formula, three roads to one line, the matrix form, and train versus test error.45 min
109One neuron, start to finishFreeWeighted sum, activation, loss, slopes and update, by hand and in code, and what one straight line can and can't split.45 min
111Training a small networkFreeThe backward pass in matrix form, gradient checks, a full training loop, and reading loss curves.45 min
112The same network in PyTorchFreenn.Sequential with the NumPy weights loaded, the same loss and slopes, then SGD and mini-batches.45 min
113Attention as matrix mathFreeScaled dot-product scores, the causal mask, a row-by-row softmax, and blending value vectors.45 min
114Residual connections and layer normFreeAdding the input back and why its slope keeps learning alive, layer norm by hand, and add and norm.40 min
115A transformer block, start to finishFreeA sentence through embeddings, attention, add and norm, a small network and next-word scores, every shape named.45 min
117Final test: transpose any formulaFreeSlips to fix from every topic, mixed practice of every kind of rearranging, the strategy chart and the full sheet.45 min
Learn the math behind AI from arithmetic up: numbers, algebra, vectors and matrices, calculus, probability and statistics, each shown as numbers moving and checked in Python, ending with a network you build and train from the formulas.
See the course →
Never trained an AI? Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account. Teach it to write