Counting, visually
Counting you can see: Pascal's triangle to row 64 coloured mod 2, 3 or 5 with parents and hockey sticks, the binomial theorem as "pick x or y", draggable stars and bars, lattice paths and MISSISSIPPI, an enumerator that shows when a construction counts something twice, derangements and 1/e, next permutation step by step, a backtracking tree with pruning, product-rule stages with password keyspaces, and birthday and hash collisions.
Added
How to use it
Pick a tab. Every count is exact (whole numbers of any size), and most tabs enumerate the objects as well as counting them, so you can check the formula against the list.
-
Pascal’s triangle — up to row 64, coloured by the remainder of each entry mod 2, 3 or 5 (Sierpiński’s triangle appears mod 2). Click an entry: its two parents (Pascal’s rule), the hockey-stick diagonal that sums to it, and its value as n!/(r!(n − r)!).
-
Binomial theorem — (a + b)ⁿ as “from each bracket pick a or b”: every pick listed (up to n = 6), grouped by how many b’s, so the coefficient C(n, k) is the size of each group. Terms can carry coefficients and signs (
2x,-1,3/4); click a group to see that one term worked out. -
Stars and bars — drag a bar (or click a star to move the nearest bar) and watch the distribution (x₁, …, x_k) change; optionally at least one or two of each. Every distribution is listed and counted against C(n + k − 1, k − 1).
-
Paths & anagrams — shortest grid routes as words of E’s and N’s, and distinct arrangements of any word (MISSISSIPPI), stepped through in dictionary order, counted as n!/(n₁!·n₂!···) and as a stage-by-stage product of binomial coefficients.
-
Counted k times — runs a construction, groups the results, and shows how many objects were built once, twice, … : ordered lists for a committee (each 3! times), the “guaranteed woman” mistake (336 builds of 195 committees), two pair with 13 × 12 (each hand twice), seats round a table, and a construction that is right. The two-pair case also deals random poker hands against the exact table.
-
Derangements — Dₙ by inclusion–exclusion, Dₙ/n! racing to 1/e, and a simulation of hats handed back at random and of Secret Santa redraws (about e of them).
-
Next permutation — the book’s four steps (pivot, successor, swap, reverse the suffix) on any list, one at a time, or every permutation in order; repeated items give each arrangement once.
-
Backtracking — the choose / explore / un-choose recursion tree for 2–6 items, step by step or played, with optional pruning (n queens, no consecutive neighbours, 1 before 2) and the nodes it saves.
-
Product rule & passwords — stage boxes for “26 × 26 × 26 × 10 × 10 × 10 × 10” style counts, with or without repeats, and a keyspace calculator: alphabet, length and guess rate give the number of keys, bits of entropy and time to search (all of it, and half on average), with the “digit + lower + upper” policy by inclusion–exclusion.
-
Birthdays & hashes — the exact chance of a repeat among n draws from N values, the stopping points of thousands of simulated rooms, and the three numbers that are easy to mix up: √N, the 50% point ≈ 1.18√N, and the mean first collision ≈ 1.25√N. For a 32-bit hash they are 65,536, 77,164 and 82,138.
The tool counts by enumerating and by formula; for single values (nCr, nPr, multisets, poker and lottery odds, the birthday problem for any group) use Probability. To watch probability happen — Monty Hall, the central limit theorem, A/B tests — see Sampling and simulation.
Companion to chapter 24 of Mathematics, Reconnected, Combinatorics: the art of counting.
Limits
-
Pascal’s triangle stops at row 64 and shows numbers only when the cells are big enough; hover a cell for its value. Binomial picks are listed up to n = 6 (64 picks), expansions up to n = 12.
-
Lists stop at a few thousand items (distributions, arrangements, permutations); the counts do not.
-
The backtracking tree is drawn when it has at most 160 ends (n ≤ 5 without pruning).
-
Simulations use a seeded generator (mulberry32), so the same seed gives the same result; they are not the book’s Python runs, so simulated numbers differ slightly from the printed ones. Birthday rooms for N above 2²² are drawn from the exact stopping-time distribution by inverse transform rather than by hashing every item; above 2⁴⁰ only the approximations are shown.
Linking to an example
Links name the tab in the hash (#pascal, #binomial, #stars, #paths, #overcount,
#derange, #nextperm, #backtrack, #stages, #birthday) and its settings as short
parameters, for example ?n=6&r=3&rows=9#pascal.
Parameters apply to the tab in the hash; anything left out takes its default. ?example=<name>
loads a book example (and its tab, if the hash names none), and other parameters override it.
Terms such as -1 and 3/4 need no escaping; a plus sign must be written %2B (a bare + in a
URL means a space, and is ignored here). Lists use commas. Opening a link replaces this browser’s
saved settings for the tool; Restore my settings undoes it.
| Tab | Parameter | Meaning | Example |
|---|---|---|---|
|
|
rows shown, 1–64 |
|
|
|
colour by remainder mod |
|
|
|
the selected entry C(n, r) |
|
|
|
the two terms: a number, a letter, or both ( |
|
|
|
the power (0–12); the term with q^k to work out ( |
|
|
|
identical objects, boxes |
|
|
|
at least this many in each box (0, 1 or 2) |
|
|
|
bar positions among the n + k − 1 places, commas |
|
|
|
|
|
|
|
east and north steps |
|
|
|
letters to arrange (up to 20) |
|
|
|
which arrangement, counting from 0 in dictionary order |
|
|
|
|
|
|
|
poker hands to deal (two-pair case), seed |
|
|
|
people; simulated shuffles; seed |
|
|
|
the starting list, commas (numbers or words) |
|
|
|
|
|
|
|
items 1 … n, 2–6 |
|
|
|
|
|
|
|
stages as pool size × count, commas |
|
|
|
|
|
|
|
password alphabet size, length, guesses per second |
|
|
|
|
|
|
|
number of equally likely values N |
|
|
|
N = 2^bits (overrides |
|
|
|
the n to highlight; simulated rooms; seed |
|
Book examples (?example=):
| Example | Shows | Book |
|---|---|---|
rows 0–8: 10 + 10 = 20, Pascal’s rule |
ch. 24 |
|
the hockey stick 1 + 3 + 6 + 10 = 20 = C(6, 3) |
ch. 24 |
|
odd entries of 64 rows: Sierpiński’s triangle |
ch. 24 |
|
Pascal’s triangle coloured mod 3 |
ch. 24 |
|
Pascal’s triangle coloured mod 5 |
ch. 24 |
|
(x + y)³: xxx xxy … yyy, so 1, 3, 3, 1 |
ch. 24 |
|
(x + 2)⁴ = x⁴ + 8x³ + 24x² + 32x + 16 |
ch. 24 |
|
coefficient of x³ in (2x − 1)⁵ is 80 |
ch. 24 |
|
exactly one affected child of four: 4 · ¼ · (¾)³ = 27/64 |
ch. 24 |
|
MISSISSIPPI: 11!/(1! 4! 4! 2!) = 34 650 |
ch. 24 |
|
5 east, 3 north: C(8, 3) = 56 shortest routes |
ch. 24 |
|
7 scoops, 3 flavours: ||* and C(9, 2) = 36 tubs |
ch. 24 |
|
at least one scoop of each: C(6, 2) = 15 |
ch. 24 |
|
a dozen doughnuts of 5 kinds: C(16, 4) = 1820 |
ch. 24 |
|
ordered lists count each committee 3! = 6 times |
ch. 24 |
|
4 × C(9, 3) = 336 counts committees 1–4 times; the answer is 195 |
ch. 24 |
|
chair first or committee first: 360 both ways, each counted once |
ch. 24 |
|
5 people round a table: 120 rows, each seating 5 times, 24 seatings |
ch. 24 |
|
13 × 12 builds every two-pair hand twice: 247 104 = 2 × 123 552 |
ch. 24 |
|
D₄ = 9; D_n/n! → 1/e |
ch. 24 |
|
10 hats: P(no one gets their own) ≈ 1/e; Secret Santa ≈ e draws |
ch. 24 |
|
(1, 3, 5, 4, 2) → (1, 4, 2, 3, 5): pivot, successor, swap, reverse |
ch. 24 |
|
all six orderings of 1, 2, 3 in lexicographic order |
ch. 24 |
|
repeated items: only 3!/2! = 3 arrangements |
ch. 24 |
|
choose / explore / un-choose: 3! = 6 leaves |
ch. 24 |
|
pruning: 4 queens |
ch. 24 |
|
3 letters, 4 digits: 175 760 000 plates |
ch. 24 |
|
no repeats: 78 624 000 plates |
ch. 24 |
|
PINs with no repeated digit: 5040, so 4960 repeat |
ch. 24 |
|
26⁸ ≈ 2.09 × 10¹¹: 20.88 seconds at 10¹⁰ guesses/s |
ch. 24 |
|
62¹² ≈ 3.23 × 10²¹: about 10 000 years |
ch. 24 |
|
digit + lower + upper required: 159 655 911 367 680 |
ch. 24 |
|
23 people: P(shared birthday) = 0.5073 |
ch. 24 |
|
32-bit hash: √N = 65 536, but 50% only at 77 164; mean first collision 82 138 |
ch. 24 |
|
32-bit hash: the first collision comes after about √N = 65 536 (50% at 77 164, mean 82 138) |
ch. 29 |
|
2¹⁶ buckets: the √N rule |
ch. 24 |
Feedback is a gift. Something to improve, a feature to add, or a bug? Tell me.
Runs entirely in your browser; nothing you type leaves this page.