Preface
This is a continuation of our combinatorics problem book. It deals mainly with pattern counting problems. These are more advanced problems, in that the mathematics behind them is probably a bit more abstract and not as intuitively easy to grasp, at least not with an initial encounter. This does not mean that they are technically more difficult, but they do require that ill-defined and somewhat nebulous concept of mathematical sophistication. This really just means being comfortable with applying mathematical machinery purely in the abstract, i.e. having trust in the machinery.
We give only a brief introduction to the mathematics behind these problems. The emphasis is on using the mathematics and not on its theoretical foundation. In our experience, when you discover the power of some new mathematical technique, and become adept at using it, then the motivation for understanding its foundation arises naturally. It is more difficult to find this motivation if you don't really understand what the math can do for you. At least that is the case with us, and it may be the result of a natural bias as physicists, who use mathematics from a more utilitarian point of view. There is a list of references for readers who want to dig deeper into the theoretical foundations of these techniques.
Here is a simple example of the kind of pattern counting we are
interested in. We have black and white square tiles and we want to
create a linear arrangement of n of them. With no restrictions,
elementary combinatorics tells us there are 2
The patterns we talk about are usually represented as a string of symbols. A class of patterns is represented by a set of strings. The set of strings is sometimes called a language. Many pattern classes fall into the category of regular languages. These are languages that can be generated by a finite automaton. A regular expression is a shorthand way of describing a regular language. Regular expressions and finite automata are very powerful ways to describe, generate, and count patterns. This book describes these tools and shows how to use them.
Another type of pattern counting problem involves equivalence under symmetry. Suppose we want to create a necklace using beads of three colors. An elementary analysis says there 3n ways to make an n bead necklace. But many of these necklaces will be related by a simple circular shift of the beads. If such necklaces are considered equivalent and counted as one, then how many unique necklaces are there? What if we also equate necklaces where one is just another that is picked up and turned over? These problems are surprisingly easy to answer using a method called Polya's theory of counting. We cover this method and its more general form, called Burnside's theorem. There are many worked out problems that show how to use the method. Included are problems that find the number of unique ways to color the Platonic solids.
In short, this book describes, and shows how to use, very powerful methods for counting patterns. These are methods that should be in the toolbox of every combinatorialist. It not only shows how to count them but also provides the means to generate them with programs that can be downloaded from the book's web page on the Abrazol website at abrazol.com.
May you have many happy hours counting and generating patterns.
Stefan Hollos and Richard Hollos Longmont, Colorado