Cellular automata are a set of rules followed to form different patterns. (i.e. The Chaos Game) There is no one fixed set of rules to form all patterns, there can be infinitely many. The evolution of divisibility patterns in Pascal's triangle is closely related to a variety of cellular automata. Running a cellular automaton and testing divisibility properties of binomial coefficients both generates a geometric pattern. Some even says that Pascal's Triangle is the first cellular automaton. Today, cellular automata act as modeling and simulation tools in a wide range of fields such as science and technology, fluid dynamics in planes, biology, sociology, and much more. Cellular automata are also great feedback machines, they are mathematical finite state machines that changes a cell's state step by step.

When an automaton is one-dimensional, its cells are simply lined up like a chain. When it's two-dimensional, the cells are arranged in an array covering a plane. Sometimes we refer to the term layers instead of steps when we draw the succeeding steps of a one-dimensional automaton one below the other.

In order to run a cellular automaton, we need two pieces of information: an initial layer and a set of rules. The rules determine the next layer from the states of cells given in the first. There can be many, many different sets of rules, and so the rules should not depend on the preceding layer, a look-up table or formula should specify it. A look-up table is basically a picture of each rule instead of writing it in English.

The set of rules:

Cells will either be coloured black or white determined by the following (refer to the look-up table in figure 6):

1. If a cell is white, and the cell right of it is also white, the right cell remains white in the next layer.
2. If a cell is black, and the cell right of it is also black, change the right cell to white in the next layer.
3. If a cell is black, and the cell right of it is white, change the right cell to black in the next layer.
4. If a cell is white, and the cell right of it is black, the right cell remains black in the next layer.

Following this set of rules gives us the Sierpinski Triangle. This is a construction of a two-dimensional automaton with the behaviour of a one-dimensional automaton. Cells grow layer by layer just like in a one-dimensional, only difference in this case is that the layers are diagonals and the pattern grows from bottom left to top right. Figure 6 shows the first 16 layers of this Sierpinski automaton. As we know, Sierpinski is a self-similar fractal, and the figure generated by automaton is self-similarity as well. Just from the first 16 rows, we see 3 exact same triangles from rows 0 - 7 with columns 0 - 7.

Figure 6

The game of life is a famous two-dimensional cellular automata followed by a particular set of rules. Its set of rules clarifies the expectation of cellular automata. The rules are as follows:

Each cell can either be alive (symbolized as black) or dead (as white).

1. A layer consists of a 3x3 square with 9 cells. (Refer to figure 7)
2. We want to determine if a cell is dead or alive in each new layer by the other 8 cells which surrounds that cell, which we'll call its "neighbours".
3. A live cell will stay alive if two or three of its neighbours are alive.
4. If more than 3 neighbours are alive, the cell will die from overcrowdedness.
5. If fewer than two neighbours are alive, then the cell will die from loneliness.
6. A dead cell will come to life when surrounded by exactly three live neighbours.

Figure 7

The Sierpinski Triangle is a 2-state automaton since the pattern is formed involving the powers of the polynomial r(x) = 1+x divided by modulus 2. As for a mod 3 automaton, it involves the powers of the polynomial r(x) = 1+x+x². When the coefficients are divided by modulus 3, the remainders can either be 0, 1, or 2, which corresponds to a 3-state automaton.

As we mentioned at the beginning, we introduced two coordinate systems. Here is a comparison between the old and new coordinate systems, with the new one on the right side.

Figure 8

This new coordinate system is more convenient to work with in understanding the global pattern formation in Pascal's Triangle. The difference between the new and old system is that in the old system, we find at position (n,k) the coefficient . While in the new system, we have at position (n,k) the binomial coefficient

 In general, when we want to know what the remainder is after applying modulus p to the coefficients we use the mod-p condition by a prime number to test a binomial coefficient using Lucas' factorization: