How odd

The new Matt Parker puzzle asks, How odd is Pascal’s triangle? Or more specifically, what percentage of the entries in the first 128 rows are odd?

Since we don’t care about the numbers themselves, just how odd they are, we can consider a modified triangle where the rule is: Each entry is the XOR (exclusive or) of the two above it. Using ones and zeroes, this triangle looks like:

Row 11
211
3101
41111
510001
6110011
71010101
811111111

An entry in this triangle is 1 if and only if the corresponding entry in Pascal’s triangle is odd. If you examine this and carry it forward, you realize this is starting to look like another famous mathematical triangle, the Sierpiński triangle. As you go to more and more rows, it gets closer to the Sierpiński triangle’s fractal nature.

In fact, what you notice is that at every row that’s a power of 2 (row 1, 2, 4, 8, 16, 32…) every entry in the row is 1. And at that point the uppermost half of the triangle is replicated twice in the lowermost half, with an “empty” triangle (all zeros) in between. For instance:

11
211
3101
41111
510001
6110011
71010101
811111111

Rows 1–2 have a triangle of size 2, composed of three 1s; rows 3-4 are two such triangles, with a “triangle” of size 1, composed of a single 0, in between. And then:

11
211
3101
41111
510001
6110011
71010101
811111111

Rows 1–4 have a triangle of size 4, composed of nine 1s and a 0; rows 3-4 are two such triangles, with a triangle of size 3, composed of six 0s, in between. And so on.

More generally, when you reach row 2^n, the first 2^{n-1} rows contain a triangle of size 2^{n-1} and the last 2^{n-1} rows contain two such triangles with an “empty” triangle of size 2^{n-1}-1 in between.

But that just means the number of 1s in the first 2^n rows is 3 times the number in the first 2^{n-1} rows. There’s one 1 in the first 1 rows, 3 in the first 2 rows, 9 in the first 4 rows, and so on: 3^n in the first 2^n rows. The total number of entries in m rows is T(m) = m(m+1)/2, and the percentage of odd entries is just the ratio of these two: P(n) = 2\times 3^n/(2^n(2^n+1)):

2^n3^nT(2^n)P(n)
233100%
491090%
8273675%
168113659.56%
3224352846.02%
64729208035.05%
1282187825626.49%

As you go to more and more rows, the percentage of odd entries gets smaller. For large n, the first 2^n rows contain a triangle of zeros filling up the middle one quarter (slightly less) of the triangle, and each of the other three quarters is a triangle containing a triangle of zeros filling up the middle one quarter, with the other three quarters being a triangle containing a triangle of zeros… well, turtles all the way down. As n approaches infinity, P(2^n) approaches equality with P(2^{n-1}). But the big triangle is a quarter empty and three quarters nonempty, so P(2^n) = 3P(2^n)/4, so in the limit, P(2^n) = 0.

Or, using the formula, \lim_{n \to \infty} P(2^n) = \lim_{n \to \infty} 2\times 3^n/(2^n(2^n+1)) = \lim_{n \to \infty} 2\times (3/4)^n = 0.

If the above triangle reminds you of a 1-dimensional cellular automaton, by the way, that’s because it is one. Specifically, you can think of it as a skewed version of Rule 60 or Rule 102 (with successive rows shifted half a cell left or right, respectively), or, if you regard adjacent numbers as actually having zeros between them, it’s Rule 90. These are the three rules in which the next state of a cell is the XOR of two of the three cells in its neighborhood.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s