Sierpinski's Gasket and Dihedral Symmetry

The Sierpinski gasket could be obtained in a variety of ways. The applet below implements a finite automaton - a step by step procedure - on a square grid which initially contains a 1 in the upper left corner and zeros everywhere else. On every step, the content S(i, j) of a cell i, j is replaced with the sum

(1)	S(i, j) + S(i-1, j) + S(i, j-1).

The change occurs simultaneously on the whole grid. (1) is similar to the creation of the Pascal triangle that is produced by replacing S(i, j) with:

(2)	S(i-1, j) + S(i, j-1).

In the applet below, (1) and (2) correspond to the checkboxes "Add" and "Replace", respectively. Observe that, taken modulo 2 on a grid of size 2ⁿ, (1) and (2) lead to them result. However, on grids of size which is not a power of 2, the pictures are quite different.

The most curious property of (1), in my view, is that, at every step, the picture has the dihedral symmetry of a regular triangle. I.e., assuming that the trangle has been sheared into an equilateral one, the pattern has 6 different symmetries: identical, 2 rotations around its center, and the reflections in each of its three, say, medians.

In the applet, both (1) and (2) are identified is being 2-pronged. A 3-pronged analogy proceeds according to

(1')	S(i, j) := S(i, j) + S(i-1, j-1) + S(i-1, j) + S(i, j-1).

and, respectively,

(2')	S(i, j) := S(i-1, j-1) + S(i-1, j) + S(i, j-1),

where the symbol ":=" relates the values of the grid (the left hand side) to those on the previous step (the right hand side.) (1') results in a square pattern that also features the dihedral symmetry: identical, three rotations, 2 reflections in the midlines, and 2 reflections in the diagonals.

Given an apparent asymmetry of the definitions (1) and (1'), the presence of the dihedral symmetry on every step comes as a surprise. Does this phenomenon have a simple explanation?

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

What if applet does not run?

Let C(n, m) denotes the binomial coefficient - "n choose m." It's not hard to surmise the formulas for a generic term of the tables resulting form (1) and (1'). Let n and m be the row and column indices starting from 0 for the table obtained after N steps. Denote the table entries as D_{n, m} and D'_{n, m}, respectively. Then

D_{n, m} = 0, for n + m > N, and
D'_{n, m} = 0, if n > N or m > N.

For other values of n and m, we have

(3)	D_{n, m} = C(N-m, n)·C(N, m), and

(3')	D'_{n, m} = C(N, n)·C(N, m).

It is quite obvious that (3') has the dihedral symmetry, and just a little less so for (3).

About Fractals

71533005