Glossary / Combinatorics
Take an ordinary 52-card deck and shuffle it well. Decks have been played with for centuries, by millions of people every day, so it feels as if every order must have come up long ago. In fact your order is almost certainly new: no one has ever held it before. Combinatorics is the art of counting how many ways there are to arrange or choose things, without listing the ways one by one.
“In plain words” is hidden on all puzzles.
Start with a small deck and add cards with the slider. Under the cards is how many different orders exist, and how long it would take to go through them all, laying out one order every second. How many cards does it take before the age of the universe is not enough?
How many cards it takes to keep going for longer than:
For a full deck there are about 8 · 1067 orders: an eight followed by 67 more digits. Imagine all 8 billion people shuffling a deck every second, starting at the Big Bang, 13.8 billion years ago. Together that makes about 3.5 · 1027 shuffles. That is a mere fraction 4 · 10−41 of all possible orders, which is to say nothing. For comparison, physicists estimate there are about 1050 atoms in the whole Earth, and there are hundreds of millions of billions of times more deck orders still.
The secret is multiplication. Each new card doesn't add orders, it multiplies them: it can be slotted into any position of the row you already have. The seventh card multiplies by 7, the twentieth by 20, the fifty-second by 52.
“Rigorous” is hidden on all puzzles.
A permutation is one way of lining up n different objects in a row. Any of the n can go first, any of the remaining n − 1 second, and so on to the last one. The number of ways is written n! and read "n factorial".
n! = n · (n − 1) · … · 2 · 1 · 3! = 3 · 2 · 1 = 6 · 4! = 24 · 10! = 3 628 800
Often the order doesn't matter: all that matters is which objects were chosen. The number of ways to choose k objects out of n is written C(n, k) and read "n choose k".
First count as if the order mattered: the first ball can be any of 49, the second any of 48, and so on to the sixth.
49 · 48 · 47 · 46 · 45 · 44 = 10,068,347,520 ordered draws
But a ticket is a set of six numbers, and the same six numbers can come out in 6! = 720 different orders. So we divide:
C(49, 6) = 10,068,347,520 / 720 = 13,983,816 different tickets
The chance of matching all six with one ticket is one in almost 14 million.
All the C(n, k) fit neatly into a triangle: row n holds C(n, 0), C(n, 1), … C(n, n). The edges are always ones, and each number inside is the sum of the two above it. Tap any number.
–
“Deeper” is hidden on all puzzles.
The number of ordered choices of k objects out of n is n · (n − 1) · … · (n − k + 1). This product is n! with the tail (n − k)! cut off. Each unordered set of k objects was counted exactly k! times, once for each of its orderings. So we also divide by k!:
n · (n − 1) · … · (n − k + 1) = n! / (n − k)! ⇒ C(n, k) = n! / (k! · (n − k)!)
This shows the symmetry C(n, k) = C(n, n − k) straight away: choosing 6 balls out of 49 is the same as choosing the 43 that are left out of the ticket. That is why Pascal's triangle is symmetric.
C(n, k) = C(n − 1, k − 1) + C(n − 1, k)
Mark one of the n objects, say the ace of spades. All sets of k objects split into two piles that don't overlap. Either the ace is in the set: then the other k − 1 come from the remaining n − 1, which is C(n − 1, k − 1) ways. Or the ace isn't: then all k come from the n − 1, which is C(n − 1, k). Together that is every set, each exactly once.
–
The same idea explains why row n adds up to 2n: each object is either taken or not, so the sets of every size together number 2 · 2 · … · 2.
n! ≈ √(2πn) · (n / e)n
Multiplying 52 numbers takes a while, but James Stirling found a shortcut back in 1730. For twenty it is off by less than half a percent, and the larger n, the more accurate: the relative error is about 1 / (12n). Compare it with the exact value.
Where do π and e come from? The logarithm of a factorial is the sum ln 1 + ln 2 + … + ln n, and that sum is almost the area under the curve ln x, roughly n ln n − n. That gives the factor (n / e)n. The root √(2πn) is a finer correction, and its π comes from the same integral that gives the area under the Gaussian curve of the normal distribution.
The middle value: line everyone up in order, and half are below it, half above.
A millionaire walks into a bar: the average income shoots up, the median barely moves.
The sum of all values divided by how many there are: what everyone would get if it were shared equally.
Almost everyone has more legs than average: the average is a little under two.
The average result you can expect if you repeat the same thing very many times.
A die's expected value is 3.5, yet no face shows 3.5.
A number from −1 to +1 showing how closely two quantities move together.
In summer both ice cream sales and drownings go up. Ice cream isn't to blame: the heat drives both.
A measure of spread: how far values typically stray from the mean. The standard deviation is its square root, in the same units.
Two towns with the same average temperature: one stays near +15 all year, the other swings from −20 to +50.
A bell-shaped distribution: most values sit near the mean, and the further away, the rarer.
Every ball on a Galton board falls at random, yet thousands of balls always build the same bell.
The more repetitions, the closer the share of an outcome gets to its true probability.
The share of heads creeps towards 50%, while the gap between heads and tails in coins usually grows.
The chance of an event given that something else is already known.
Almost all NBA players are tall, but almost all tall people are not NBA players.
Events are independent if knowing about one doesn't change the chances of the other.
After five heads in a row tails is no more likely: the coin remembers nothing.
How many times you multiply the base by itself to get a number: log₂ 8 = 3, because 2 · 2 · 2 = 8.
A sheet of paper folded in half 42 times would be thicker than the distance to the Moon.
A sample some people get into more easily than others, so it describes everyone badly.
In 1936 a magazine polled millions of Americans and still picked the wrong election winner.
How often chance alone would produce a gap at least as big as yours if there were really no difference.
When there is no effect at all, p below 0.05 turns up as often as p between 0.50 and 0.55.
A range around a measured number, built by a method that covers the true value in a chosen share of samples, such as 95%.
Of twenty honest 95% intervals, on average one misses the truth, and none of them knows whether it is the one.
The probability that a test notices a real effect of a given size. A power of 80% means the test misses one working effect in five.
A weak A/B test that does find an effect almost always exaggerates it: a real +10% shows up on the dashboard as +24%.
How far an average or a rate computed from a sample usually misses the truth: σ divided by the square root of the sample size.
Halving the error takes four times as much data.
The sum 1 + ½ + ⅓ + ¼ + …: it grows without limit, but incredibly slowly.
Identical books can be stacked so the top one overhangs the table edge as far as you like.
The rule for updating confidence when new evidence arrives: prior odds × strength of the evidence.
Two weak pieces of evidence together can be strong, while one striking piece means little if the claim was unlikely.
Growth where a quantity is multiplied by the same factor each time, so it doubles at equal intervals.
One grain on the first square of a chessboard, doubling on each next one: the last square holds as much rice as the world grows in over 300 years.
A path where each next step is taken at random: forward or back, left or right.
A drunk man will always find his way home, but a drunk bird may never return.
A stream of independent random events at a constant average rate: calls, Geiger clicks, raindrops.
In 1944 Londoners thought German flying bombs were aimed at certain districts; it was ordinary random clumping.