You are here

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.

Kathleen M. Shannon and Michael J. Bardzell, "Patterns in Pascal's Triangle - with a Twist - Second Twist: Finite Groups," Convergence (December 2004)