This Month's Feature Column

Gray Codes

Introduction

How many ways are there to take three letters a, b, c and arrange them in different ordered strings?


abc
acb
bac
bca
cab
cba

The list above shows all of the six possible different strings. The strings are listed the way they would be in a dictionary, where words that start with a come before those that start with b, and these in turn come before those that start with c. Which word, able or alert, comes first in the dictionary? Since both words start with a we have a tie, so we look at the letter in the second position. Since b comes before l, we list able before alert. This approach to ordering strings is known as lexicographical ordering. It begins with a system for an ordering of alphabetical strings of length 1 and extends to order strings of any length. Note that to carry such a process one has to know the "ordering" for the letters in the alphabet. Thus, if one has the four-symbol "alphabet" a, A, b, B, one might want to consider the lexicographical order for these 4 symbols to be a, b, A, B or a, A, b, B. Using the ordering a, A, b, B, the legicographical ordering of strings of symbols of length two without repeats would be:

aA
ab
aB
Aa
Ab
AB
ba
bA
bB
Ba
BA
Bb

while with the ordering a, b, A, B we would have:

ab
aA
aB
ba
bA
bB
Aa
Ab
AB
Ba
Bb
BA

Mathematics often involves giving precise definitions of terminology and looking at the consequences of those definitions subject to various rules. Often this offers novel approaches to objects that one thought were familiar territory.

Part of the interest in enumerating the starting collection of strings, which can be thought of as the permutations of three symbols--all the different ways to arrange three symbols where order matters--is because there are so many different situations where they arise. For example, there are 6 different ballots that a voter can produce when three candidates are ranked without ties. Alternatively, these strings are the different "passwords" or "pins" that can be created with exactly 3 fixed letters, where no letter can be repeated.

Joseph Malkevitch
York College (CUNY)
malkevitch at york.cuny.edu