Another Twist
The algorithm we used to generate Pascal's Triangle 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. 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. A set is closed under a given operation if 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. 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 which 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 which are desirable:

Associativity: Many operations with which you are familiar are associative.
If you add three to four to get seven, then add five, you get twelve. On
the other hand if you add four to five to get nine, then add three to nine,
you also get twelve. 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 twenty by ten to get two and then divide two
by two, you get one. On the other hand if you divide ten by two to get
five, then divide twenty by five, you get four, not one.
(20/10)/2 does not equal 20/(10/2). It does matter which ones 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, 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 . .
.

Identity: With addition on the integers, you have a zero element. Zero plus any
other number just gives you the other number. The same is true of any number
plus zero. 0+5=5+0=5. Thus zero is the additive identity. The number
one works similarly with multiplication; one 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 exists an element e
of A such that for all other elements a of A:
e*a = a*e = a
then e is the identity element. An operation
with an identity is said to have the identity property.
Again note
. . .

Inverses: Once you have an identity, you can talk about inverses.
Remember the additive inverse of a number is its negative, since when you
add a number and its negative you get zero, the additive identity. The
multiplicative inverse of a number is its reciprocal, since a number times
its reciprocal is one, the multiplicative identity. If we restrict ourselves
to the whole numbers, every number has an additive inverse but numbers
like 2 and 3 do not have multiplicative inverses since 1/2 and 1/3 are
not whole numbers. If an operation has an identity and the set also has
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
note . . .
It is possible to 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, which is 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. You can construct a
PascGalois
Triangle (the next twist on Pascal's Triangle) by first associating with every
element in a finite group a different color, then placing one element down
one side of the triangle and a, possibly different, element down the the
other side of the triangle, and finally using the group operation, generally referred
to as group multiplication, to generate the interior. Pascal's triangle
mod n for any integer n is one kind of example of PascGalois
Triangles since the integers, {0, 1, 2, . . . n1} 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, ..., n1} using addition mod n is called Z_{n}. Z_{n}
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 where you combine 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 Z_{2}
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 Z_{2} with itself,
denoted Z_{2}x Z_{2}. Notice that the operation
involved is just the same operation from Z_{2}, performed
on each of the elements in the pair separately.
Would you like to see the PascGalois Triangle for this set?
Andy's Applets:
Would you like to see what happens if you make PascGalois Triangles using groups formed
by putting together a copy of Z_{n} and Z_{m}?
All of the groups that we have looked at so far
have an additional property that we did not list above. That property is

4. 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. Groups whose operations
do not have this property are called noncommutative or nonabelian.
One wellknown class of nonabelian groups are the dihedral groups, D_{n}.
To illustrate these, let us begin by looking at D_{3}. The
elements of D_{3} are movements of an equilateral triangle
which 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 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 follows:
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 follows:
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:
* 
e 
p 
q 
a 
b 
c 
e 
e 
p 
q 
a 
b 
c 
p 
p 
q 
e 
b 
c 
a 
q 
q 
e 
q 
c 
a 
b 
a 
a 
c 
b 
e 
q 
p 
b 
b 
a 
c 
p 
e 
q 
c 
c 
b 
a 
q 
p 
e 
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, D_{3} is
a nonabelian group. Let's see how the PascGalois triangles
look 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
3gon, a square is a regular 4gon, and the U.S. Pentagon is built in the
shape of a regular 5gon. 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
4gon. Thus D_{4} has 8 elements. Similarly, there are n
flips and n rotations that are symmetries for a regular ngon.
The rotations are through multiples of 360/n degrees and the flips
are across axes formed as follows:

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 ngon will form a group
with 2n elements and we call the group D_{n}. We
define the multiplication in the same way we did in the D_{3}
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.
Andy's Applets:
Would you like to generate your own?