|
Geometry of Binomial Coefficients (1984) |
|
This note describes the geometrical pattern of zeroes and ones obtained by reducing modulo two each element of Pascal's triangle formed from binomial coefficients. When an infinite number of rows of Pascal's triangle are included, the limiting pattern is found to be ``self-similar,'' and is characterized by a ``fractal dimension'' 
. Analysis of the pattern provides a simple derivation of the result that the number of even binomial coefficients in the 
th row of Pascal's triangle is 
, where 
is a function which gives the number of occurrences of the digit 1 in the binary representation of the integer .
Pascal's triangle modulo two appears in the analysis of the structures generated by the evolution of a class of systems known as ``cellular automata.'' (See [1], [2], [3] for further details and references.) These systems have been investigated as simple mathematical models for natural processes (such as snowflake growth) which exhibit the phenomenon of ``self-organization.'' The self-similarity of the patterns discussed below leads to self-similarity in the natural structures generated.
Figure 1 shows the first few rows of Pascal's triangle, together with the figure obtained by reducing each element modulo two, and indicating ones by black squares and zeroes by white (blank) squares. Figure 2 gives sixty-four rows of Pascal's triangle reduced modulo two. A regular pattern of inverted triangles with various sizes differing by powers of two is clear. Large inverted triangles spanning the whole of Pascal's triangle begin at rows 
. Consider the pattern down to the beginning of one such large inverted triangle (say down to the sixty-third row). A striking feature of the pattern is that the largest upright triangle contains three smaller triangles whose contents are similar (except at the scale of very small triangles) to those of the largest triangle, but reduced in size by a factor of two. Inspection of each of these three smaller triangles reveals that each is built from three still smaller similar triangles. This ``self-similarity'' continues down to the smallest triangles. At each stage, one upright triangle from the pattern could be magnified by one or more factors of two to obtain essentially the complete pattern. The pattern obtained differs from the original complete pattern at the scale of very small triangles. If, however, Pascal's triangle were extended to an infinite number of rows, then for all finite triangles this effect would disappear, and the original and magnified patterns would be identical. In fact, triangles of any size could be reproduced by taking smaller triangles and then magnifying them. The limiting pattern obtained from Pascal's triangle modulo two is thus ``self-similar'' or ``scale invariant,'' and may be considered to exhibit the same structure at all length scales. Many examples of other ``self-similar'' figures are given in [4], [5].
If the number of inverted triangles with base length 
is denoted 
, then Fig. 2 indicates that 
. For large , therefore
The exponent 
appearing here gives the ``fractal dimensionality'' [4], [5] of the self-similar pattern.
Consider a (``filled in'') square. Reduce the square by a factor of two in each of its linear dimensions. Four copies of the resulting reduced square are then required to cover the original square. Alternatively, one may write that the number of squares 
with side length contained in the original square satisfies 
, so that 
. The exponent two here gives the usual dimensionality of the square. One may then by analogy identify the exponent 
in Equation (1) as the generalized or ``fractal'' dimension of the figure formed from Pascal's triangle modulo two.
Figure 2 suggests that the number 
of ones in the th row of Pascal's triangle modulo two (or, equivalently, the number of odd binomial coefficients of the form 
is a highly irregular function of . However, when is of the form 
, the simple result 
is obtained. This can be considered a consequence of the algebraic relation 
for 
and all primes 
, which may be proved by considering the base representations of factorials. Algebraic methods [6]--[12] have been used to obtained the general result
The function gives the number of occurrences of the digit 1 in the binary representation of the integer . Hence, for example, 
, 
, 
, 
, and so on. A graph of for up to 128 is given in Fig. 3. Note that although the function is defined only for integer , values at successive integers have been joined by straight lines on the graph. For 
, 
. The lower bound is reached when is of the form 
; the upper one when 
. Clearly 
(since multiplication by simply appends zeroes, not affecting the number of 1 digits), and for 
, 
(since the addition of in this case prepends a single 1, without affecting the remaining digits).
.The result (2) for may be obtained by consideration of the geometrical pattern of Fig. 2, continued for 
rows, so as to include the complete upright triangle containing the th row. By construction, the th row corresponds to a line which crosses the lower half of the largest upright triangle. Each successive digit in the binary decomposition of determines whether the line crosses the upper (0) or lower (1) halves of successively smaller upright triangles. The upper halves always contain one upright triangle smaller by a factor two; the lower halves contain two such smaller triangles. The total number of triangles crossed by the line corresponding to the th row is thus multiplied by a factor of two each time the lower half is chosen. The total number of ones in the th row is therefore a product of the factors of two associated with each 1 digit in the binary representation of , as given by Equation (2).
There are several possible extensions and generalizations of the results discussed above.
One may consider Pascal's triangle reduced modulo some arbitrary integer 
. Figure 4 shows the resulting patterns for a few values of . In all cases, a self-similar pattern is obtained when sufficiently many rows are included. For prime, a very regular pattern is found, with fractal dimension
so that 
. 
, and so on. In general, for large , one finds that 
; when 
, the elements of Pascal's triangle modulo become ordinary integers, which are all nonzero by virtue of the nonzero values of binomial coefficients. By a simple generalization of Equation (2), the number of entries with value 
in the th row of Pascal's triangle modulo is found to be 
, where now 
gives the number of occurrences of the digit in the base- representation of the integer .
One may also consider the generalization of Pascal's triangle to a three-dimensional pyramid of trinomial coefficients. Successive rows in the triangle are generalized to planes in the pyramid, with each plane carrying a square grid of integers. The apex of the pyramid is formed from a single 1. In each successive plane, the integer at each grid point is the sum of the integers at the four neighbouring grid points in the preceding plane. When the integers in the resulting three-dimensional array are reduced modulo , a self-similar pattern is again obtained. With 
, the fractal dimension of the pattern is 
. In general, the pattern obtained from the 
-dimensional generalization of Pascal's triangle, reduced modulo two, has fractal dimension 
.
for several values of .
White squares indicate zeroes; progressively blacker squares indicate increasing values, up to 
.
