Essential Combinatorics

The first task is to decide what counts as one outcome.

Textbook Media Press presents ESSENTIAL COMBINATORICS, a compact, self-contained working course in the principal methods of counting. It begins with the sum and product rules, permutations and combinations, stars and bars, and probability by counting, then develops combinatorial proof, the pigeonhole principle, Catalan and Stirling numbers, multinomial methods, inclusion–exclusion, elementary number theory, generating functions, and recurrence relations.

The emphasis throughout is on representation: decide what the objects are, determine when two descriptions are the same, and choose the method that exposes the structure. Continuing examples carry fixed points, pairings, occupancy, symmetry, and compositions through the book, while graded exercises move from direct applications to proof, synthesis, and longer explorations. Answers, hints, or solutions are provided in the back matter.

A formula becomes much more useful when we understand the objects it counts and the decisions that produced it. For that reason, many identities are approached in more than one way. An algebraic derivation may establish the result efficiently, while a combinatorial proof explains why the two sides must agree by identifying a common family of objects. The aim is to make these changes of viewpoint a natural habit.

The manuscript is meant to be read with pencil in hand. A displayed formula usually appears at the end of a counting argument rather than at its beginning: first identify the outcomes, decide when two descriptions represent the same object, determine whether order or repetition matters, and only then choose a formula. Early examples make this modeling step explicit, and later chapters return to the same habit when the objects become paths, set partitions, arithmetic functions, probability distributions, or coefficients of a power series. The exercises are part of the exposition, because many of them ask the reader to discover a second representation or to push an idea beyond the formal development in the chapter.

Five recurring threads run the length of the book. Fixed points of permutations progress from elementary counting to derangements, bivariate exponential generating functions, factorial moments, and a Poisson limit. Pairings move from the double factorial to noncrossing Catalan structures and then to involutions. Occupancy problems connect balls and boxes with the pigeonhole principle, Stirling numbers, onto functions, and birthday asymptotics. Circular arrangements develop into questions about periodic words, Möbius inversion, stabilizers, and Burnside’s lemma. Compositions evolve from separator arguments to generating functions, tilings, and Fibonacci-like recurrences. Two longer case studies, on dice relabeling and on set partitions, carry the same philosophy across a still wider range of mathematics.

The text grew from a ten-lecture course given at Western Kentucky University, in which the author presented the counting methods and combinatorial theory he had found useful while studying and working in other areas of mathematics and its applications.

Scope. Graph theory, Ramsey theory, and the deeper theory of integer partitions are important areas, but a serious treatment of them would require a different and substantially longer book. Here the emphasis remains on methods a mathematically literate reader is likely to need elsewhere: constructing a sample space, changing representations, exploiting symmetry, extracting coefficients, recognizing a recurrence, and deciding which of several familiar tools is appropriate to a new problem.