Patterns in Pascal's Triangle - with a Twist

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

Mathematics is, at heart, a search for patterns and for a deep understanding of how and why they occur. It does not matter if the patterns are in naturally occurring phenomena -- e.g., weather or population growth -- or in geometrical structures that we mentally impose upon reality to make sense of it -- e.g., triangles, circles, ellipses, or tetrahedra. These patterns may also be found in structures that we create for any number of reasons.  We will introduce you to some structures we have been studying and some of the questions that arise from investigating the patterns we see in them.

Faculty Notes We are addressing primarily the non-specialist in mathematics, although we also include asides for mathematicians, particularly those who teach non-specialists. These asides can be found by clicking on the buttons with musical notes -- see the figure at the right, which in fact links to the first such aside. Pages intended for the more specialized audience will be clearly marked with these notes at the top of the page.   Elsewhere we assume minimal background in mathematics, so the main body of the article may be enjoyed by students, particularly those in Liberal Arts Mathematics or Mathematics Appreciation courses, or anyone who is interested in gaining a new appreciation for mathematics. However, pages 8-11 will be difficult for some students to understand and would be more appropriate for mathematics majors in foundational courses, particularly those courses that introduce groups. If you find pages 8-11 too difficult, skim through them, skip to the patterns, or skip them altogether.

We hope this article may give you an appreciation for the beauty of mathematics and an understanding of those who study it for its own sake. We also hope to point out some connections to disciplines and areas of study which, unlike most of the sciences, are frequently seen as being at some distance from mathematics.


Acknowledgements

Support for much of this work was provided by the National Science Foundation award # DUE-0087644 and by the Richard A. Henson endowment for the School of Science and Technology at Salisbury University.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

We thank undergraduate research student Andrew Nagel for providing the applets to accompany this article.


Published November, 2003
© 2003 by Kathleen M. Shannon and Michael J. Bardzell

Patterns in Pascal's Triangle - with a Twist - Introduction

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

Mathematics is, at heart, a search for patterns and for a deep understanding of how and why they occur. It does not matter if the patterns are in naturally occurring phenomena -- e.g., weather or population growth -- or in geometrical structures that we mentally impose upon reality to make sense of it -- e.g., triangles, circles, ellipses, or tetrahedra. These patterns may also be found in structures that we create for any number of reasons.  We will introduce you to some structures we have been studying and some of the questions that arise from investigating the patterns we see in them.

Faculty Notes We are addressing primarily the non-specialist in mathematics, although we also include asides for mathematicians, particularly those who teach non-specialists. These asides can be found by clicking on the buttons with musical notes -- see the figure at the right, which in fact links to the first such aside. Pages intended for the more specialized audience will be clearly marked with these notes at the top of the page.   Elsewhere we assume minimal background in mathematics, so the main body of the article may be enjoyed by students, particularly those in Liberal Arts Mathematics or Mathematics Appreciation courses, or anyone who is interested in gaining a new appreciation for mathematics. However, pages 8-11 will be difficult for some students to understand and would be more appropriate for mathematics majors in foundational courses, particularly those courses that introduce groups. If you find pages 8-11 too difficult, skim through them, skip to the patterns, or skip them altogether.

We hope this article may give you an appreciation for the beauty of mathematics and an understanding of those who study it for its own sake. We also hope to point out some connections to disciplines and areas of study which, unlike most of the sciences, are frequently seen as being at some distance from mathematics.


Acknowledgements

Support for much of this work was provided by the National Science Foundation award # DUE-0087644 and by the Richard A. Henson endowment for the School of Science and Technology at Salisbury University.

Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

We thank undergraduate research student Andrew Nagel for providing the applets to accompany this article.


Published November, 2003
© 2003 by Kathleen M. Shannon and Michael J. Bardzell

Patterns in Pascal's Triangle - with a Twist - What is Pascal's Triangle?

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

Faculty Notes In the twelfth century, both Persian and Chinese mathematicians were working on a so-called arithmetic triangle that is relatively easily constructed and that gives the coefficients of the expansion of the algebraic expression (a + b)n for different integer values of n (Boyer, 1991, pp. 204 and 242). Here's how it works:

  • Start with a row with just one entry, a 1.
  • Begin and end each subsequent row with a 1.
  • Each row should have one more entry than the row above it. Determine each interior entry by adding the number directly above the space for the new entry to the number diagonally above and to the left, so you get
1                              
1 1                            
1 2 1                          
1 3 3 1                        
1 4 6 4 1                      
1 5 10 10 5 1                    
1 6 15 20 15 6 1                  
1 7 21 35 35 21 7 1                
1 8 28 56 70 56 28 8 1              
1 9 36 84 126 126 84 36 9 1            
1 10 45 120 210 252 210 120 45 10 1          
1 11 55 165 330 462 462 330 165 55 11 1        
1 12 66 220 495 792 924 792 495 220 66 12 1      
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1    
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1  
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1

 

If you want to expand (a + b)10, for example, go to the row that begins 1, 10 -- it's the 11th row if you start counting at 1 or the 10th row if you start counting at 0. The terms of the expansion will all be of the form apbq, where p + q  = 10, and p and q are whole numbers between 0 and 10. Line the terms up, starting with a10b0, and decreasing the power of a and increasing the power of b. The coeficients in the row are then in the proper order. So,

(a + b)10 = 1a10b 10a9b 45a8b 120a7b 210a6b 252a5b      
+ 210a4b 120a3b 45a2b 10  a1b 1a0b10.

These numbers also give the number of different ways you can choose some from a collection of objects. If you have 11 objects and want to choose 3 of them, go to the 11th row (counting from 0) and the 3rd position in (again counting from 0), and you see that there are 165 different ways to choose 3 items from a collection of 11. This brings us to Pascal.

In the mid-1600s, while Blaise Pascal was working on one of his mathematical treatises, one of his friends, the Chavalier de Mere, began asking him questions about gambling odds, such as: "In eight throws of a die, a player is to attempt to throw a one, but after three unsuccessful trials, the game is interrupted. How should he be indemnified?" (Boyer and Merzbach, 1991, p. 363). Pascal's work in this area eventually led to the modern theory of probability, which has spawned the related area of statistics. Little did Pascal know where his work would lead. Nevertheless, since at the core of investigations of chance is the need to count the number of different possibilities, Pascal made use of the arithmetic triangle in his work. Because of the attention that work received, the triangle began to be known in the west as Pascal's Triangle.

The triangle is also frequently displayed in a symmetric manner where each row is centered, as in the following figure. Many people have studied the patterns to be found in the numbers in Pascal's triangle (see, for example, Brown and Hathaway, 1997; Granville, 1992, 1997; Long, 1981; and Wolfram, 1984). We will discuss one approach to looking for patterns in generalized versions of the triangle.

 

                  1                  
                1   1                
              1   2   1              
            1   3   3   1            
          1   4   6   4   1          
        1   5   10   10   5   1        
      1   6   15   20   15   6   1      
    1   7   21   35   35   21   7   1    
  1   8   28   56   70   56   28   8   1  
1   9   36   84   126   126   84   36   9   1

Patterns in Pascal's Triangle - with a Twist - First Twist: What is It?

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

Faculty Notes

Pascal's Triangle (symmetric version) is generated by starting with 1's down the sides and creating the inside entries so that each entry is the sum of the two entries above to the left and to the right. Suppose that, instead of using regular addition to generate the interior entries, you used modular arithmetic (also known as clock arithmetic). You may or may not remember seeing modular arithmetic in school, but you use it regularly when you deal with time. Three hours after 11:00 it is not 14:00 but rather 2:00. You add three to eleven, but when you get to twelve you start over again at 0. Modular arithmetic works the same way, except that we use 0 in place of the last number (which would be 12:00 in clock arithmetic).

[The military and some other organizations use a 24-hour clock and speak of "1100 hours" and "1400 hours". But this is still modular arithmetic with 24 replacing 12. For example, four hours after "2100 hours" is "100 hours" (i.e., 1:00 AM the next day). Furthermore, 0 replaces 24 in the military system -- you never hear a military person say "2400 hours".]

We also can do modular arithmetic with numbers other than 12 for the maximum. For example, we can use 5 as the maximum, in which case we call it mod 5 arithmetic. In mod 5 arithmetic, we use the numbers 0, 1, 2, 3, and 4, and 3 plus 3 is 1, while 2 plus 2 is still 4. If we do arithmetic mod 3, 2 plus 2 is 1, but 1 plus 1 is still 2, etc. You can see the addition tables for a number of different mod numbers by following this link.

One nice thing about modular arithmetic is that there are only a finite number of possible answers. If you assign to each of the possible answers a color, then the triangle can be presented as an array of colored dots or circles. Most of us find it more appealing to look for patterns in this kind of image than in the numbers themselves. The following figures show the first few rows of Pascal's Triangle using mod 3, mod 4, and mod 5 addition, expressed as arrays of colored circles. In these figures red is 0, black is 1, green is 2, blue is 3, and yellow is 4.

 

Pascal's Triangle Mod 3
27 rows
Pascal's Triangle Mod 4
32 rows
Pascal's Triangle Mod 5
50 rows

Sometimes we can see things differently if we use different colors. Here are the same patterns with different color assignments:

       Faculty Note

Andy's Applets: Would you like to try generating images for Pascal's Triangle mod n on your own?

Patterns in Pascal's Triangle - with a Twist - How about the Patterns?

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

 

Faculty Notes The figures above show six hexagons, each created by pasting together six identical copies of Pascal's Triangle mod some number. [There is no mathematical signficance in the pasting operation -- it is just a way to provide the appealing "kaleidoscopic" patterns, which may emphasize number patterns by repetition.] The mod numbers used fall into two different categories, three in one category, three in the other. Just by looking at the patterns, can you guess which sets of three hexagons go together? Want a hint?

Patterns in Pascal's Triangle - with a Twist - Two More Patterns

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

With which of the two groups would you place these two hexagons? Although 8 and 9 are both composite numbers, they are somewhat different in character from 6, 10, and 12 -- they each have only one prime factor. That is, 8 is a power of 2, and 9 is a power of 3, while 6 and 12 have both 2 and 3 as factors, and 10 has both 2 and 5 as factors.

What is really going on here? In the next section we look at these more closely.

Patterns in Pascal's Triangle - with a Twist - Patterns for [i]n[/i] = 2 through 12

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

 

Here are the triangles mod n for = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and 12.

 

Pascal's triangle mod 2 with 50 rows Pascal's triangle mod 3 with 50 rows Pascal's triangle mod 4 with 50 rows
Pascal's triangle mod 5 with 50 rows Pascal's triangle mod 2 with 50 rows Pascal's triangle mod 3 with 50 rows
Pascal's triangle mod 4 with 50 rows Pascal's triangle mod 5 with 50 rows Pascal's triangle mod 2 with 50 rows
Pascal's triangle mod 3 with 50 rows Pascal's triangle mod 4 with 50 rows colors assigned to 0 through 12

Look at the triangles for = 2 and n = 4. See how similar they are? If you were to recolor the yellow circles as royal blue and the light blue circles as black, the n = 4 triangle would be the same as the n = 2 triangle. Why do you think that might be?

Now look at the = 6 triangle. Can you see a color identification that would transform it to the = 2 triangle? How about to the = 3  triangle? Answers

Next look at the = 8 triangle. Can you make an identification that would transform it to the = 4 triangle? You could then make another identification to transform it to the n = 2 triangle. Answers

Can you see identifications between other triangles? What is the pattern here? Answers

Faculty Notes

Patterns in Pascal's Triangle - with a Twist - The Solid Downward-Pointing Triangles

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

 

Here are the triangles for n = 2 through 12 drawn to more rows:

 

Pascal's triangle mod 2 with 125 rows Pascal's triangle mod 3 with 125 rows Pascal's triangle mod 4 with 125 rows
Pascal's triangle mod 5 with 125 rows Pascal's triangle mod 2 with 125 rows Pascal's triangle mod 3 with 125 rows
Pascal's triangle mod 4 with 125 rows Pascal's triangle mod 5 with 125 rows Pascal's triangle mod 2 with 125 rows
Pascal's triangle mod 3 with 125 rows Pascal's triangle mod 4 with 125 rows colors assigned to 0 through 12

You probably noticed immediately the downward-pointing royal blue triangles in all of the patterns. Since royal blue corresponds to the number zero, you can see that, whenever you get a string of zeros on a row, this will generate a downward pointing blue triangle -- any entry below two zeros will be zero. But the non-zero entries on either end of the string will encroach one position on each side for each row.

For example, if you start with a row {1,0,0,0,0,0,1} and generate the following rows, you get:

 

1   0   0   0   0   0   1
  1   0   0   0   0   1  
    1   0   0   0   1    
      1   0   0   1      
        1   0   1        
          1   1          
            2            

The downward pointing triangles containing subsets of the colors for a triangle occur for similar reasons. For example, look at one of the blue triangles for the mod 2 triangle. Now look at the same area in the mod 4 and mod 8 triangles. What do you see? Look at the same region in the mod 6 triangle. What can you say about the colors in this region in the mod n triangles for any even n? (Answer)

Patterns in Pascal's Triangle - with a Twist - Second Twist: Finite Groups

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

Faculty Notes

The algorithm we used to generate Pascal's Triangle we can generalize still further. There is nothing special about addition -- all we need for our algorithm to work is an operation with two inputs and one output, both from the same collection of possible inputs and outputs. When we add 1 + 2 to get 3, 1 and 2 are the "inputs" and 3 is the "output". 1, 2 and 3 are all from the same set of allowable numbers. For the original version of Pascal's Triangle, that set is the set of counting numbers. And for the mod n triangle, the allowable set is {0, 1, ..., n}, with the operation of mod n addition.

For our coloring scheme to work, we need to have a finite set of allowable inputs and outputs, and all outputs need to be possible inputs. We need the set to be closed under our operation -- that is, whenever you perform the operation on members of the set, it returns another member of the set (as opposed to returning something not in the set). For example, if you add two counting numbers, you get another counting number, so the counting numbers are closed under addition. If you add two numbers from the set {0, 1, 2, 3, 4} modulo 5, you get another number from the set {0, 1, 2, 3, 4}, so the set {0, 1, 2, 3, 4} is closed under mod 5 addition.However, if you divide two counting numbers, you may get a result that is not another counting number. For example, 2 divided by 3 is 2/3, which is a fraction -- not a counting number. So the counting numbers are not closed under division.

Closure is absolutely required for our coloring scheme to work. When we combine two elements from our set, each of which is identified with a color, we must have another element of our set also identified with a color. An operation that takes two inputs from a given set and returns another element of the set is called a binary operation on the set. So we need a finite set and a binary operation on the set. There are some additional properties that are desirable:

  1. Associativity: Many familiar operations are associative. If you add 3 to 4 to get 7, then add 5, you get 12. On the other hand, if you add 4 to 5 to get 9, then add 3 to 9, you also get 12. In other words, (3 + 4) + 5 = 3 + (4 + 5); it doesn't matter which two you associate first. This does not work for every operation. For example, if you divide 20 by 10 to get 2 and then divide 2 by 2, you get 1. But if you divide 10 by 2 to get 5, then divide 20 by 5, you get 4, not 1. That is, (20/10)/2 does not equal 20/(10/2). It does matter which of the numbers you associate first.

    To generalize this idea, we say that an operation is associative if, whenever you perform the operation on two elements and then perform the operation again on the result of the first operation and a third element, you get the same result as you would if you performed the operation on the second element and the third element and then performed it again on the first element and the result of operating on the second and third.

    That's hard to follow, so let us try it this way: An operation * on a set A is associative if, for any elements a, b, and c of A,

    (a * b) * c = a * (b * c).

    Note . . .

     

  2. Identity: With addition on the integers, you have a zero element. Zero plus any other number gives you the other number. The same is true ofanynumberpluszero.Forexample,0 + 5 = 5 + 0 = 5. Thus 0 is the additive identity. The number 1 works similarly with multiplication -- that is, 1 is the multiplicative identity. If you multiply 1 by any number, then you just get the number back.

    If a set has an element which, whenever you operate on that element and any other element of the set or on any other element of the set and that element, the operation returns the other element; then the element with this property is called the identity element for the operation. In other words, given an operation * on a set A, if there is an element e of A such that, for all elements a of A,

    e * a = a * e = a,

    then e is the identity element for the operation *. An operation with an identity element is said to have the identity property. Again that note . . .

     

  3. Inverses: Once you have an identity element, you can talk about inverse elements. The additive inverse of a number is its negative -- that is, when you add a number and its negative you get 0, the additive identity. The multiplicative inverse of a number is its reciprocal, since a number times its reciprocal is 1, the multiplicative identity.

    If we restrict ourselves to the whole numbers, every number has an additive inverse, but numbers such as 2 and 3 do not have multiplicative inverses, because 1/2 and 1/3 are not whole numbers. On the other hand, in the set of all positive fractions (ratios of counting numbers, including such numbers as 7/1), every number has a multiplicative inverse, but no number has an additive inverse, because none of the negative fractions are in the set.

    Suppose a set has an operation with an identity and also the following property: Each element has an element with which it can be associated such that the result of applying the operation to two associated elements always returns the identity element. Then the operation has the inverse property. Two associated elements are called inverses of each other. In other words, given an operation * on a set A with an identity e, if for every element a in A, there exists an element a-1 in A such that

    a * a-1 = a-1 * a = e,
    then a-1 is called the inverse of a, and the operation * has the inverse property. One more time, that note . . .

We can perform our coloring scheme using sets with operations without these three properties. However, sets together with binary operations having these properties have led to an entire branch of mathematics called Group Theory, a subset of Abstract Algebra. Therefore, when we are interested in adding a new twist to our patterns, it is natural for us to start with sets and operations with these three properties.

A set together with a binary operation having properties 1 through 3 is called a group. A  finite set with such an operation is called a finite group. In the next section we will extend our coloring scheme to Pascal-like triangles whose entries are defined by operations in a finite group.

Patterns in Pascal's Triangle - with a Twist - More Patterns: PascGalois Triangles

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

We can construct a  PascGalois Triangle -- the next twist on Pascal's Triangle -- by the following steps:

  1. Associate with every element in a finite group a different color.
  2. Place one element of the group down one side of the triangle.
  3. Place another (possibly different) group element down the the other side of the triangle.
  4. Using the group operation (generally referred to as "group multiplication"), generate the interior.

Pascal's triangle mod n for any integer n is one example of PascGalois Triangles, since the integers {0, 1, 2, ...,  - 1} under addition mod n are a finite group. We generally give names to groups so that we can easily refer to them. The set {0, 1, 2, ..., n-1} using addition mod n is called ZnThis group is also called the cyclic group of order n. (Why cyclic?) Remember that we have seen the "multiplication" tables for some of these groups.

Here is another example: Consider the set of ordered pairs {(0,0), (1,0), (0,1), (1,1)} and the operation of combining two members of the set by adding the first components mod 2 to get the first component of the result and adding the second components mod 2 to get the second component of the result. Here is the multiplication table for this operation:

* (0,0) (0,1) (1,0) (1,1)
(0,0) (0,0) (0,1) (1,0) (1,1)
(0,1) (0,1) (0,0) (1,1) (1,0)
(1,0) (1,0) (1,1) (0,0) (0,1)
(1,1) (1,1) (1,0) (0,1) (0,0)

Notice that this set is really like two copies of Z2 pasted next to each other. When two sets are put together to form a new set of ordered pairs in this manner, we call it a cross product. So this example is just the cross product of Z2 with itself, denoted Z2  x Z2. Notice that the operation involved is just the same operation from Z2, performed on each of the elements in the pair separately. In the next section we will see the PascGalois Triangle for this set.

Patterns in Pascal's Triangle - with a Twist - Cross Products of Cyclic Groups

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

Let us see what happens when we make a PascGalois triangle using the group Z2  x Z2. Remember that the multiplication table for this group is

Now we have to choose which elements to place down the sides of our triangle. Notice that if we chose to place (0,1) down both sides, combining (0,1) with itself gives (0,0) and combining again with (0,1) gives (0,1) again so the element (0,1) cannot generate the whole group. Unlike the case of modular addition, where repeated addition of 1's will generate all of the possible results, in this set there is no single element that generates the whole set. Thus we decide to put the element (1,0) down one side of the triangle and the element (0,1) down the other side. In this triangle, pink is (0,1), yellow is (1,0), purple is (1,1), and teal is (0,0).

Here is the same triangle with a few more rows:

Does this triangle remind you of any of the modular arithmetic triangles? In particular does it remind you of the mod 2 triangle, also known as the Z2 PascGalois triangle? Let's take another look at the Z2  x Z2 triangles with 50 rows. In the following sequence of figures, we begin to change slowly the color corresponding to (1,1) to the color corresponding to (0,0). Then we change the color corresponding to (1,0) until it matches the color corresponding to (0,1). The final triangle is the Z2 triangle redrawn using teal for zero and pink for one. The colors corresponding to the different elements are displayed in order {(0,0),(0,1),(1,0),(1,1)} to the left of each triangle.

 

Z2xZ2 PascGalois triangle with teal identity Z2xZ2 PascGalois triangle with teal identity and (1,1) moving to teal Z2xZ2 PascGalois triangle with teal identity and (1,1)moving to teal
Z2xZ2 PascGalois triangle with teal (1,1) and identity Z2xZ2 PascGalois triangle with teal (1,1) and identity and (1,0) moving to pink Z2xZ2 PascGalois triangle with teal (1,1) and identity and (1,0) moving to pink
Z2xZ2 PascGalois triangle with teal (1,1) and identity and (1,0) moving to pink Z2 PascGalois triangle with teal identity and 1 in pink

The following animation shows the same identification occurring in the 128-row triangles.

Patterns in Pascal's Triangle - with a Twist - Dihedral Groups

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

All of the groups that we have looked at so far have an additional property that we did not list on page 8:

  1. Commutativity: An operation is commutative if the order of the two elements being operated on doesn't matter. In other words, an operation * on a set A is commutative if, for any a and b in the set A,

    a * b = b * a.

Groups whose operations have this additional property are called commutative groups or, more frequently, abelian groups. (Why abelian?) Groups whose operations do not have this property are called non-commutative or non-abelian.

Among the important non-abelian groups are the dihedral groups, Dn. To illustrate these, let us begin by looking at D3. The elements of D3 are movements of an equilateral triangle that result in the triangle's still looking the same as it did before you moved it. Such a movement is called a symmetry. For example, if you flip an equilateral triangle around any one of its altitudes, the triangle still looks the same -- see the first figure below. The pink lines and the labels on the vertices are to help you to see what is going on but are not part of the triangle itself. Therefore, we do not say that the triangle looks different if the only change in its appearance is in the positioning of the labels or the pink lines. There are six different symmetric movements of the triangle; three of these involve flipping the triangle across an altitude as in the following pictures:

 

  Let's call this movement a.
  Let's call this movement b.
  Let's call this movement c.

The other three symmetric movements are rotations though 0 (or 360) degrees, 120 degrees and 240 degrees as in the following figures:

  Let's call this movement e.
  Let's call this movement p.
  Let's call this movement q.

 

The operation we will associate with this set of movements is just to perform the movements one after the other.

For example if you perform movement a:
followed by movement p:
you get the same result you would have
gotten from performing movement c:

So a * p = c.

We can try this with all combinations to get the multiplication table for this operation:

 

Notice that properties 1 though 3 hold for this operation on this set of movements, but property 4 does not hold. For example, a * p = c, but p * a = b. They are not the same. Therefore, D3 is a non-abelian group. Take a look at the PascGalois triangles for this group.

Of course, the equilateral triangle is not the only shape with symmetries. Although many shapes have symmetries, the easiest family of shapes to study in this manner are the regular polygons. Remember that a polygon is a many sided figure (where the sides are straight edges), and a regular polygon is one whose sides are all the same length. Thus an equilateral triangle is a regular polygon, a.k.a. a regular 3-gon, a square is a regular 4-gon, and the U.S. Pentagon is built in the shape of a regular 5-gon. A square has eight symmetries. You can flip it about either of its two diagonals or about either of its two altitudes or you can rotate it through 0, 90, 180, or 270 degrees. (Remember that a rotation through 360 degrees is the same as a rotation through 0 degrees.) So there are 4 flips and 4 rotations that are symmetries for the regular 4-gon. Thus D4 has 8 elements. Similarly, there are n flips and n rotations that are symmetries for a regular n-gon. The rotations are through multiples of 360/n degrees and the flips are across axes formed in the following ways:

If n is even, join the midpoints of sides that are across from each other or join corners that are across from each other.

If n is odd, join each corner to the midpoint of the opposite side.

 

Thus the symmetries of a regular n-gon will form a group with 2n elements, and we call the group Dn. We define the multiplication in the same way we did in the D3 case. Again, performing a flip followed by another flip results in a rotation, performing a rotation followed by another rotation results in a rotation, and performing either a flip then a rotation or a rotation then a flip, results in a flip. (You can verify this by cutting out a regular hexagon and a regular pentagon, labeling the corners, and flipping and rotating.) It is possible to generate multiplication tables and thus PascGalois triangles for these groups. Then it is interesting to see what the triangles look like.

Patterns in Pascal's Triangle - with a Twist - Some Questions about Recognizing Patterns

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

Faculty Notes

Recognizing patterns depends on our ability to perceive them. One interesting sidebar that arose in our study of these patterns has to do with human visual perception. The patterns we can find in the D3 triangles are much more apparent with some color assignments than with others. This of course leads us to questions about how humans perceive colors. We also wonder how perception might differ from individual to individual. There are a wealth of interesting questions that could be researched in this area. Some of the questions could probably be answered with a review of the literature in psychology of perception or in biology. Others could lead to further experimentation in these areas.

We have not pursued these issues, but we wish to bring these questions to your attention, and we have constructed an animation to illustrate the phenomena to which we refer. You can also see the differences among the six triangles in the hexagon below. All six were generated the same way but using different color assignments. If you read pages 8-11, you may recognize at least some of these as PascGalois triangles for D3.

Hexagon made from six D3 PascGalois Triangles with different color associations

 

There are also questions about which kinds of patterns people would find aesthetically appealing. It might be interesting to study whether people prefer hexagons made with Pascal's Triangles mod n for n prime vs. n composite or for values of n with different prime factors vs. values with the same prime factors. For example, see this page.

Another question of interest: How many different colors can the human eye distinguish in patterns such as these? And a related question: How do we generate the maximum number of distinguishable colors on a computer screen? Interestingly enough, having once generated colors for the computer screen, it is a non-trivial problem to generate equivalent colors for print. We have a pretty good algorithm for generating 16 colors and can expand to a reasonable set of 64 colors but are not certain that they are all truly distinguishable.

There is definitely work to be done in this area. Those who study art and graphical design struggle with similar issues. These issues suggest some interesting projects that students from a number of disciplines might wish to tackle.

Patterns in Pascal's Triangle - with a Twist - Zooming In: Self-Similarity

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

Faculty Notes

One thing you can notice when you study our triangles is that sometimes when you "zoom out" or increase the number of rows you get triangles that look very similar. The following animations show what happens when you increase or decrease the number of rows in certain PascGalois Triangles. In each case, notice how the general structure or appearance of the triangle is preserved as you "zoom out".

Pascal's Triangles mod 3: Each triangle has either three
times as many or a third as many rows as the previous one.
PascGalois Triangles for Z3 tripling number of rows
Pascal's Triangles mod 5: Each triangle has either five
times as many or a fifth as many rows as the previous one.
PascGalois Triangles for Z5 quintupling number of rows
PascGalois Trianglesfor D4:
Each triangle has either twice as many or half as many
rows as the previous one. PascGalois Triangles for D4 doubling number of rows
PascGalois Trianglesfor D3:
Each triangle has either twice as many or half as many
rows as the previous one. PascGalois Triangles for D3 doubling number of rows

If something looks the same when viewed at all different scales, it is said to be self-similar. For example, imagine looking at a satellite image of a jagged coastline. Now consider looking at an image taken from an airplane of a smaller section of the same coastline. Finally, think of an image of the coastline taken from a tower nearby of a yet smaller section of the coast. Assuming the coast is natural and undeveloped, all three images would likely look pretty much the same. By changing the scale, you do not change the essential nature of the "curve" that would outline the coast.

You can perform a similar exercise by looking at snapshots taken at different distances for some other image. For example, think of the patterns in the growth of a fern or a tree. A single branch of a tree looks pretty much like a tree itself.

These are all examples of the self-similarity property found in geometric objects known as fractals. See Burger and Starbird (2000, pp. 398-511), Field and Golubitsky (1992), or Gleick (1987) for more information about fractals and fractal geometry. Fractals arise in an area of mathematics called Dynamical Systems or Chaos Theory that became very popular in 1980's. It continues to be a rich area of mathematics because these fractal patterns frequently correspond better to many things we see in nature than do the shapes (circles, triangles, rectangles, general polyhedra, etc.) that had previously been used to describe them.

PascGalois Triangles exhibit their own kind of self-similarity, and the tools that have been developed to study the self-similar structure of fractals, such as the notion of fractal dimension, can be modified to study them as well. This is one avenue of further study related to these images. See Bardzell and Shannon (preprint) and Wolfram (1984) for more information.

Patterns in Pascal's Triangle - with a Twist - One-Dimensional Cellular Automata

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

 

There has been considerable interest recently in structures called cellular automata. The most famous example of a cellular automaton is probably John Conway's Game of Life. Cellular automata have been used to model a number of natural phenomena, including the spread of fires and disease. PascGalois Triangles are examples one-dimensional cellular automata. We can also look at two-dimensional cellular automata with similar constructions and at one-dimensional cellular automata with slightly different constructions.

A one-dimensional cellular automaton is a row of cells, each of which has some value from a finite alphabet, together with a local rule for changing the values of the cells in discrete time steps. A configuration in which each cell has a specific value from the alphabet is called a state. The local rule, called the update rule, assigns a new value to a cell based on its current value and the values of its neighbor cells.

For example, Pascal's Triangles mod n or the PascGalois Triangles discussed in section 3 can be viewed as one-dimensional cellular automata with an infinite number of cells. First, consider each row of the triangle as extending indefinitely in either direction, with the "hidden" cells outside the triangle assigned values of zero or the group identity. Each entry of the triangle corresponds to a cell and its value. We update the automaton by combining the current value of a cell with the current value of the cell directly to the right of it and then place the row of cells with new values directly below the old row. This gives the PascGalois triangle skewed to the right. For example, here are two versions of the first 125 rows of Pascal's Triangle mod 5 (or the PascGalois triangle for Z5):

 

PascGalois Triangle for Z5
One-Dimensional Cellular Automata using Z5 multiplication Rule

This is an example of an infinite cellular automaton. Remember that each row of these pictures represents a different state of the automaton, so that as you move down the rows, you are moving through the temporal evolution of the automaton. Of course, for this to generalize to PascGalois triangles with two different values down the two sides, we have to begin with a row with two non-identity entries. With Pascal's Triangle mod n, we can begin with the top row with a single entry of one.

One-Dimensional Cellular Automaton using Z5 multiplication RuleWe can also define related finite cellular automata either by fixing the values of the cells on the ends or by wrapping the cellular automata around so that the cell on the right of the last cell is defined to be the first cell, and the cell on the left of the first cell is defined to be the last cell. Essentially, you define your automaton as if the row of cells is in fact a circle of cells. You can then apply the same update rule. Suppose we do the mod 5 example again with 25 cells wrapped into a circle -- see the figure at the right.

Notice that the values begin to repeat, i.e. the last 25 rows look just like the first 25. In fact, this particular cellular automaton repeats every 100 rows. Since we have only finitely many cells and only finitely many values they can take on, the cellular automaton has finitely many possible states, so eventually it has to repeat a state it has already taken on. Once it does that, the subsequent states will also repeat. With finite cellular automata, no matter what state you begin with, you always evolve to a repeating cycle eventually. This repeating cycle is called a periodic cycle. The states taken on before reaching the periodic cycle are called transient states. For our example, since the entire set of states repeats, there are no transient states.

If we try this with 18 cells instead of 25, the periodic cycle contains 2232 states, and the initial state, the one with only one nonzero value, does not repeat -- it is transient.

  • What makes this case different?
  • Can we predict in advance what the length of the periodic cycle will be?
  • Does the length of the periodic cycle change if we begin with a different initial state, or does it depend only on the number of cells we're using?
  • If we use some group multiplication other than Z5, how will that change things?

It is relatively easy to play around with examples and to make conjectures about them, but proving the conjectures is another matter.

In addition to looking at other groups, we can look at other update rules. For example, you might define the new value of a cell to be the sum (or the product, using group multiplication) of the value of the cell to the left and the value of the cell to the right. Our undergraduate research students have been able to answer some of the questions that arise in these investigations -- see Gymnich (2002) and Miller (2001) for some examples -- but there are still many questions left to explore

Patterns in Pascal's Triangle - with a Twist - Two-Dimensional Cellular Automata

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

A two-dimensional cellular automaton consists of a grid of cells rather than a row of cells. As in the one-dimensional case, the cells have values from a finite alphabet and a local rule to update those values. In the one-dimensional case, the local neighborhood that determines the cell's next value consists of the cell itself and its neighbors to the left and to the right. Two-dimensional automata have neighbors in more directions.

The best known example of a two-dimensional cellular automaton is John Conway's Game of Life. (A web search on "Game of Life" will turn up numerous references, including programs you can download to experiment with the automaton. We list one such site in our References.)

We show two popular ways to specify a cell's neighborhood in the following figures. On the left, the neighborhood consists of nine cells, and on the right the neighborhood consists of only five. In a nine-point rule, all the cells in this three-by-three grid would be considered neighbors of the center cell. In a five-point rule, only those that share an edge with the center cell would be included. Thus the four corners, although diagonally adjacent to the center cell, are not available to the rule.

The same kinds of questions arise for two-dimensional cellular automata as for one-dimensional automata. As in the one-dimensional case, if we use a finite grid, there are only finitely many possible states, one of which is the state in which all cells have the value of zero (or the identity). If this state is reached, the cellular automaton continues in this state forever. Since there is really no action at this point, we generally refer to this state as "death" -- we say a cellular automaton initial state that eventually reaches this state "dies" or "dies out."

The red line is where the top and bottom join; the blue is where left and right join.As we did in our example in the one-dimensional case, we define the cells at the right hand edge of the grid and the cells at the left hand edge to be next-door neighbors. We also define the downstairs neighbors of the bottom row to be the first row and the upstairs neighbors of the first row to be the last row. In this manner we are really wrapping our rectangle into the surface of a donut shape or a torus.

Click here for some examples of group multiplication rule cellular automata. These were created by using a five-point rule of clockwise group multiplication, not including the center. The file contains some large animations and may take a while to load. If you are having trouble loading or running these animations, you might want to try our supercompressed versions instead.

We also include some examples of nine-point rule automata. This file also has large animations and may take a while to load. If you are having trouble loading or running these animations, you might want to try our supercompressed versions instead.

Andy's Applet's: Would you like to run your own two-dimensional automata? [[This link is no longer functional. Ed: 2013.]

There are a myriad of other questions one could ask, either spawned by the investigations outlined above or by going in other directions entirely. We have had students with interests in computer science, statistics, pure mathematics, and applied mathematics work with us on various questions that have spun off of these investigations. A full listing of even the extensions we have begun investigating is beyond the scope of this paper, but we refer you to the References for more information. We also invite you to think of your own questions. It seems that every investigation in mathematics leads to more new questions. Thus mathematics is an ever-growing rich field of knowledge. We hope you have enjoyed this small journey into just one of the many accessible niches in mathematics.

Patterns in Pascal's Triangle - with a Twist - References

Author(s): 
Kathleen M. Shannon and Michael J. Bardzell

Bardzell, M., and K. Shannon (preprint), Fractal Dimensions of Group Generated 1-Dimensional Cellular Automata, Salisbury University.

Bardzell, M., and K. Shannon (2002), "The PascGalois Triangle: A Tool for Visualizing Absract Algebra," pp. 115-123 in Innovations in Teaching Abstract Algebra (A. C. Hibbard and E. J. Maycock, eds.), MAA Notes #60, Washington, D.C.: Mathematical Association of America.

Boyer, C. B., and U. C. Merzbach (1991), A History of Mathematics, 2nd ed. New York: Wiley

Brown, S., and D. Hathaway (1997), "Fibonacci Powers and a Facinating Triangle," The College Mathematics Journal, 28, 124-128.

Burger, E. B., and M. Starbird (2000), The Heart of Mathematics: An Inviation to Effective Thinking, Emeryville, CA.: Key College Publishing.

Field, M., and M. Golubitsky (1992), Symmetry in Chaos: A Search for Pattern in Mathematics Art and Nature, Oxford: Oxford University Press.

Gleick, J. (1987), Chaos: Making a New Science, New York: Viking Penguin Inc.

Granville, A. (1992), "Zaphod Beeblebrox's Brain and the Fifty-ninth row of Pascal's Triangle," The American Mathematical Monthly, 99, 318-331.

Granville, A. (1997), "Correction to: Zaphod Beeblebrox's Brain and the Fifty-ninth row of Pascal's Triangle, " The American Mathematical Monthly, 104, 848-851.

Gymnich, S. (2002), "A Classification of Simple 1-Dimensional Automata Generated over Cyclic Groups," Proceedings of the National Conference on Undergraduate Research (NCUR), University of Wisconsin-Whitewater.

Long, C. (1981), "Pascal's Triangle Modulo p," Fibonacci Quarterly 19, 458-463.

Miller, N. (2001), "Periodicity and Long-Term Evolution of 2-D Cellular Automata," Proceedings of the National Conference on Undergraduate Research (NCUR), University of Kentucky, Lexington, KY.

Phillips, H. (1961), My Best Puzzles in Logic and Reasoning, New York: Dover Publications.

Wolfram, S. (1984), "Geometry of Binomial Coefficients," The American Mathematical Monthly, 91, 566-571.

Additional Web resources (available as of 11/6/03):