Pascal's triangle, in two colours

Pascal’s triangle is the most elementary object in combinatorics — an object of the same kind as the gnomon, where an arrangement does the work a formula would otherwise have to. Start with a 1. Every entry below is the sum of the two above it. That is the whole rule.

Its entries count things — row $n$ holds the number of ways to choose $k$ items from $n$, for each $k$ — and it has been known in one form or another in China, Persia, India and Europe for around a thousand years, considerably longer than Pascal has been dead. Halayudha describes it in tenth-century India, al-Karaji in eleventh-century Persia, Yang Hui in thirteenth-century China. Pascal’s contribution, in 1654, was to organise what was known and connect it to the new theory of games of chance; the name is a piece of European bookkeeping rather than a claim of discovery.

What every one of those traditions found first was the additive rule, and it is worth pausing on why that rule produces counts at all. To choose $k$ items from $n$, either the last item is taken — leaving $k-1$ to choose from $n-1$ — or it is not, leaving $k$ to choose from $n-1$. Those two cases are exhaustive and do not overlap, so the counts add. The triangle is that single sentence, iterated.

Now do something arbitrary to it. Not wrong, not clever — arbitrary, in the sense that nothing about the triangle’s purpose suggests it, and the question could as easily have been asked of the integers laid out in a spiral. Ignore the values entirely and ask only one question of each entry: is it odd or even? Shade the odd ones.

That shape has a name #

It is the Sierpiński triangle, described by Wacław Sierpiński in 1915 by a construction that has nothing whatever to do with binomial coefficients: take a triangle, remove the middle quarter, and repeat on each of the three triangles that remain, forever.

One construction is about counting subsets. The other is about cutting holes in paper. They produce the same object, and the coincidence demands an explanation.

Why the holes are where they are #

The explanation is a result of Édouard Lucas, from 1878. It says that the binomial coefficient $\binom{n}{k}$ is odd exactly when the binary digits of $k$ are a subset of the binary digits of $n$ — that is, whenever $k$ has a 1 bit, $n$ must have a 1 bit in the same place.

Take row 12, which is $1100$ in binary. Then $\binom{12}{4}$ is odd, because $4 = 0100$ and its single 1 bit sits under one of $n$’s. But $\binom{12}{2}$ is even, because $2 = 0010$ has a bit where 12 has none.

Written as a single condition: $\binom{n}{k}$ is odd exactly when k AND NOT n is zero. It is a two-instruction test, and it is why generating the picture requires no factorials and no big-number arithmetic at all.

Now the self-similarity. Rows $0$ through $2^m - 1$ are exactly the rows where $n$ has no bits above position $m$. Rows $2^m$ through $2^{m+1}-1$ have one extra high bit set, and that bit is either matched by $k$ or not — which splits the next block of rows into two independent copies of the block above, separated by a region where the bit is unmatched and everything is even.

That is the recursion. Doubling the number of rows produces two copies of the existing picture side by side, with a solid triangular gap between them. Doubling again does it to the result. The Sierpiński triangle is what that process converges to, and it converges to it because binary place value is itself a doubling structure.

So the shape is not a coincidence at all. Both constructions are the same recursion, one expressed in the base-2 representation of integers and the other in the geometry of subdividing a triangle. The surprise is in the disguise, not in the fact.

Counting the odd entries exactly #

Lucas’ theorem does more than explain the shape. It makes the picture countable, and the count is the thing that turns a striking image into a measured claim.

Row $n$ is odd at position $k$ exactly when $k$’s bits sit under $n$’s. So the number of odd entries in row $n$ is the number of subsets of $n$’s 1 bits — which is $2^{s(n)}$, where $s(n)$ counts the 1 bits in the binary form of $n$.

The formula is easy to check against the picture and it explains the two most conspicuous features at once. A row numbered $2^m$ has a single 1 bit, so it has exactly two odd entries — the two ends — and that is why the picture has those startlingly empty rows running across it at every power of two. A row numbered $2^m - 1$ is all 1 bits, so every one of its $2^m$ entries is odd, and those are the solid rows immediately above the empty ones.

Total the count over the first $2^m$ rows and the sum is $3^m$: each new bit position either is set or is not, and setting it doubles that row’s count while adding a row. Three, nine, twenty-seven, eighty-one — the number of shaded cells triples every time the number of rows doubles.

That is the fractal dimension, stated as arithmetic rather than as a property of a limit. Doubling the linear size multiplies the shaded area by 3 instead of by 4, so the exponent relating them is $\log 3 / \log 2 \approx 1.585$. And the density follows immediately: of the $\tfrac12 \cdot 2^m(2^m+1)$ entries in the first $2^m$ rows, only $3^m$ are odd, so the proportion of odd entries is roughly $(3/4)^m$ — which goes to zero. Almost every entry of Pascal’s triangle is even, and the triangle looks about half shaded only because the drawn part of it is a very small $m$.

The shape is older than both of them #

The usual telling has Sierpiński describing the shape in 1915 and the parity picture arriving later, once anyone thought to shade a triangle. Both dates are much too recent.

The shape appears in the floors of a number of Italian churches, laid in the Cosmatesque style by marble workers in the twelfth and thirteenth centuries. The pavement of the cathedral at Anagni carries it in several places, built up through three or four levels of subdivision in coloured stone, some two hundred years before Pascal and seven hundred before Sierpiński.

Whether the craftsmen had anything in mind that would now be called self-similarity is not knowable from a floor. What is clear is that the construction — take a triangle, mark the midpoints, leave the middle one out, do it again to the others — is a natural thing to do with a chisel and a stock of coloured marble, and that the resulting pattern is pleasing at a glance and rewarding on inspection, which is the whole brief of a church floor.

That is a useful corrective to the way these coincidences are usually narrated. Two constructions did not converge on one shape because of a deep unity revealing itself to mathematics; a doubling recursion is one of the few things that can be done with a triangle, and anyone who does it gets this. The interesting fact is not that the shape recurs. It is that the parity of a combinatorial count performs the same recursion, and that took Lucas to notice.

Change the modulus, change the picture #

If parity is what produces this, other divisors should produce their own patterns — and they do. Colouring by remainder modulo 3 gives a self-similar pattern built on triples rather than pairs; modulo 5 gives one built on fives. Kummer’s theorem, a generalisation of Lucas’, says exactly how many times a prime $p$ divides $\binom{n}{k}$: it is the number of carries that occur when $k$ and $n-k$ are added in base $p$.

That is a startling sentence on first reading. A fact about divisibility turns out to be a fact about carrying — about the mechanics of column addition in a particular base. The fractals in Pascal’s triangle are pictures of where the carries happen.

The counting argument above generalises with it, and puts a number on what those two figures show. For a prime $p$, the entries in the first $p^m$ rows that survive — that are not divisible by $p$ — number exactly

$$\left(\frac{p(p+1)}{2}\right)^m,$$

the count in the first $p$ rows raised to the $m$-th power, for the same reason $3^m$ worked at $p = 2$: each new base-$p$ digit replicates the whole block. Counting them by brute force confirms it — $6$, $36$ and $216$ across the first $3$, $9$ and $27$ rows modulo $3$; $15$, $225$ and $3375$ modulo $5$.

So every modulus has its own dimension, $\log\!\big(p(p+1)/2\big)/\log p$, and no two are the same: $1.585$ at $p = 2$, $1.631$ at $3$, $1.683$ at $5$, $1.712$ at $7$. They climb with $p$ and approach $2$ without ever arriving — at $p = 1009$ the dimension is $1.900$. The modulo-5 picture is measurably denser than the modulo-3 one, and the trend says why: a larger prime divides fewer entries, so more survive, and the holes thin out until the triangle is very nearly solid without ever quite becoming so.

That the dimension differs for every prime is the part worth registering. The Sierpiński triangle is not the shape hiding in Pascal’s triangle. It is the shape that appears when the question asked is about $2$. There is a different fractal for every prime, all self-similar for the same reason, and the famous one is famous because parity is the first question anybody thinks to ask.

The additive rule also explains why the triangle is symmetric, which is otherwise a curiosity. Choosing $k$ items from $n$ is the same act as choosing which $n-k$ to leave behind, so $\binom{n}{k} = \binom{n}{n-k}$ and each row reads the same backwards. That symmetry is visible in the parity picture too — the shaded pattern is a mirror image about the vertical axis — and it survives every modulus, because a symmetry of the numbers is inherited by any question asked of them.

There is a small lesson in that. Properties of an object tend to survive being looked at in new ways, which is why asking an old object a new question is so often productive: whatever structure was there is still there, and the new question may be the one that makes it visible. The triangle was built to count committees. It answers questions about binary representation, about fractal dimension, about the shape of a pile of falling balls, and about carrying in base $p$ — none of which anyone had in mind, all of which were already present in the additive rule from the beginning, waiting for somebody to ask a question the rule had not been built to answer.

The same triangle, elsewhere #

Pascal’s triangle has an unreasonable number of things hidden in it, and most of them are visible once the right question is asked of the entries.

Sum each row and the totals are the powers of two, because choosing any subset of $n$ items means making $n$ independent yes-or-no decisions. Read the shallow diagonals and the Fibonacci numbers appear. Read the third diagonal and the triangular numbers do — the same ones that show up as two interlocking staircases.

And plot a row as a bar chart rather than a list, and the shape is a bell curve. Row 40 of Pascal’s triangle, drawn to scale, is very nearly a normal distribution — which is not a coincidence either, and is the subject of balls falling through a peg board. Each entry counts the number of paths from the top to that position, and a ball bouncing down a Galton board is choosing a path at random.

What the picture cannot show #

The parity picture is finite and the Sierpiński triangle is not. Thirty-two rows, or sixty-four, or a thousand — each is a stage of a construction whose actual subject is the limit, and the limit is not any of them.

That matters for the one property everybody quotes. The Sierpiński triangle has dimension $\log 3 / \log 2 \approx 1.585$: more than a line, less than a region. No finite stage has that dimension. Every drawn stage is a finite union of solid triangles with dimension exactly 2 and total area that is still positive. The area goes to zero and the dimension drops below 2 only in the limit, and the limit cannot be drawn — a picture of it would be a picture of something with no area at all.

The exact count sharpens the point rather than resolving it. That the first $2^m$ rows hold precisely $3^m$ odd entries is a statement about every finite stage, provable and checkable, and the number $1.585$ is extracted from how that count grows rather than from any drawing it describes. A dimension is a property of a trend, and a trend is the one thing a single figure is structurally incapable of containing — which is why the count had to be done in prose, on a picture that shows sixteen rows.

The pictures are also silent on why the two constructions coincide. They show that they do, convincingly, and Lucas’ theorem is what explains it. Coincidence-spotting is what a figure is good for; the reason is always somewhere else.

The ladder from here #

Rungs above: the hockey-stick identity, and the other sums the triangle’s shells encode. Binomial coefficients as counts of lattice paths — which is the Galton board in another costume. The binomial theorem, drawn. Lucas’ theorem proved rather than quoted. Kummer’s carry-counting theorem in full. Fractal dimension made precise, with box-counting. Iterated function systems, and the chaos game that draws the same triangle from random points. Pascal’s triangle modulo composite numbers, where the pattern is messier and more interesting. And the connection to the figurate numbers living in its diagonals.

What the exercise is really about #

The move here is worth naming: take a well-understood object and ask it a question it was not built to answer.

Pascal’s triangle was constructed to count combinations. Asking about parity is a question from a different subject entirely, with no obvious reason to produce anything interesting. The reason it does is that the object had more structure in it than the original question needed, in the way a cone had more in it than any single conic section required — and structure that a construction did not consciously put in is exactly the structure that turns out to be worth finding.

Ulam’s spiral, in primes on a spiral, comes from the same instinct applied to the integers, and produces something considerably less well understood. Sometimes the unexpected pattern has a two-line explanation, as here. Sometimes it is an open problem.

The two cases are worth holding side by side, because from inside the picture they are indistinguishable. Colouring Pascal’s triangle by parity and colouring the integers by primality are the same gesture applied to two different objects. One produced a fractal with a complete explanation inside twenty years; the other produced a pattern that has resisted a hundred. Nothing about how the pictures look predicts which is which, and any instinct that says otherwise is worth distrusting.