×

Zaphod Beeblebrox’s brain and the fifty-ninth row of Pascal’s triangle. (English) Zbl 0757.05003

The author gives a new proof that the number of odd integers in the \(n\)th row of Pascal’s triangle is \(2^{\#_ 2(n)}\), where \(\#_ 2(n)\) is the number of one’s in the binary expansion of \(n\). Marking the odd elements of Pascal’s triangle, a self-similar pattern evolves. So, the author tries to give an explanation for the patterns of entries \(\equiv 1\pmod 4\) and \(\equiv-1\pmod4\). At first, no method works, but superimposing an idea of Zaphot Beeblebrox’s brain [from D. Adams, The hitchhiker’s guide to the galaxy, London 1979], he can deduce these patterns to arrive at the theorem: The number of entries \(\equiv 1\pmod 4\) equals the number of entries \(\equiv-1\pmod 4\) in row \(n\) if and only if there are two consecutive 1’s in the binary expansion of \(n\); otherwise there are no entries \(\equiv-1\pmod 4\) in row \(n\).
It becomes more complicated to get the next theorem: In each row of Pascal’s triangle, the number of integers in each of the arithmetic progressions 1, 3, 5, and \(7\pmod 8\) is either 0 or a power of 2. The author is also able to give the correct exponents of 2 in this theorem. How to proceed with 16? All methods fail: In Row 59 there are exactly six entries in each of the congruence classes 1, 11, 13, and \(15\pmod{16}\) – - six is no power of two (but \(2+6=8)\).
At last the author can show a kind of self-similarity of Pascal’s triangle \(\bmod p\) \((p\) an odd prime). The ideas for the proof come from patterns generated by cellular automata.
Reviewer: B.Richter (Berlin)

MSC:

05A10 Factorials, binomial coefficients, combinatorial functions
11B65 Binomial coefficients; factorials; \(q\)-identities
PDFBibTeX XMLCite
Full Text: DOI