1 - Introduction

Summary

This book is about counting. Of course this doesn't mean just counting a single finite set. Usually, we have a family of finite sets indexed by a natural number n, and we want to find F(n), the cardinality of the nth set in the family. For example, we might want to count the subsets or permutations of a set of size n, lattice paths of length n, words of length n in the alphabet {0, 1} with no two consecutive 1s, and so on.

What is counting?

There are several kinds of answer to this question:

1. • An explicit formula (which may be more or less complicated, and in particular may involve a number of summations). In general, we regard a simple formula as preferable; replacing a formula with two summations by one with only one is usually a good thing.

2. • A recurrence relation expressing F(n) in terms of n and the values of F(m) for m < n. This allows us to compute F(0),F(1), … in turn, up to any desired value.

3. • A closed form for a generating function for F. We will have much more to say about generating functions later on. Roughly speaking, a generating function represents a sequence of numbers by a power series, which in some cases converges to an analytic function in some domain in the complex plane. An explicit formula for the generating function for a sequence of numbers is regarded as almost as good as a formula for the numbers themselves.

If a generating function converges, it is possible to find the coefficients by analytic methods (differentiation or contour integration).

In the examples below, we use two forms of generating function for a sequence (a₀,a₁, a₂, …) of natural numbers: the ordinary generating function, given by

and the exponential generating function, given by

We will study these further in the next chapter, and meet them many times during later chapters. In Chapter 10, we will see a sort of explanation of why some problems need one kind of generating function and some need the other.