# Combinatorics: A Guided Tour

Share this page
*David R. Mazur*

MAA Press: An Imprint of the American Mathematical Society

Reprinted edition available: TEXT/55

Combinatorics is mathematics of enumeration,
existence, construction, and optimization questions concerning finite
sets. This text focuses on the first three types of questions and
covers basic counting and existence principles, distributions,
generating functions, recurrence relations, Pólya theory,
combinatorial designs, error correcting codes, partially ordered sets,
and selected applications to graph theory including the enumeration of
trees, the chromatic polynomial, and introductory Ramsey theory. The
only prerequisites are single-variable calculus and familiarity with
sets and basic proof techniques.

The text emphasizes the brands of
thinking that are characteristic of combinatorics: bijective and
combinatorial proofs, recursive analysis, and counting problem
classification. It is flexible enough to be used for undergraduate
courses in combinatorics, second courses in discrete mathematics,
introductory graduate courses in applied mathematics programs, as well
as for independent study or reading courses. What makes this text a
guided tour are the approximately 350 reading questions spread
throughout its eight chapters. These questions provide checkpoints for
learning and prepare the reader for the end-of-section exercises of
which there are over 470. Most sections conclude with Travel Notes
that add color to the material of the section via anecdotes, open
problems, suggestions for further reading, and biographical
information about mathematicians involved in the
discoveries.

#### Reviews & Endorsements

This is a well-written, reader-friendly, and self-contained undergraduate course on combinatorics, focusing on enumeration. The book includes plenty of exercises, and about half of them come with hints.

-- M. Bona, Choice Magazine

… The delineation of the topics is first rate—better than I have ever seen in any other book. … CAGT has both good breadth and great presentation; it is in fact a new standard in presentation for combinatorics, essential as a resource for any instructor, including those teaching out of a different text. For the student: If you are just starting to build a library in combinatorics, this should be your first book.

-- The UMAP Journal

… [This book] is an excellent candidate for a special topics course for mathematics majors; with the broad spectrum of applications that course can simultaneously be an advanced and a capstone course. This book would be an excellent selection for the textbook of such a course. … This book is the best candidate for a textbook in combinatorics that I have encountered.

-- Charles Ashbacher

# Table of Contents

## Combinatorics: A Guided Tour

- cover cover11
- copyright page ii3
- title page iii4
- Preface vii8
- Before you go xv16
- 1 Principles of Combinatorics 120
- 2 Distributions and Combinatorial Proofs 4968
- 3 Algebraic Tools 83102
- 4 Famous Number Families 141160
- 5 Counting Under Equivalence 187206
- 6 Combinatorics on Graphs 225244
- 7 Designs and Codes 271290
- 8 Partially Ordered Sets 317336
- Bibliography 365384
- Hints and Answers to Selected Exercises 369388
- Section 1.1 369388
- Section 1.2 370389
- Section 1.3 370389
- Section 1.4 371390
- Section 1.5 371390
- Section 2.1 371390
- Section 2.2 372391
- Section 2.3 372391
- Section 2.4 373392
- Section 3.1 373392
- Section 3.2 374393
- Section 3.3 374393
- Section 3.4 374393
- Section 3.5 374393
- Section 3.6 375394
- Section 4.1 375394
- Section 4.2 375394
- Section 4.3 376395
- Section 4.4 376395
- Section 5.2 377396
- Section 5.3 377396
- Section 5.4 378397
- Section 5.6 378397
- Section 6.1 378397
- Section 6.2 379398
- Section 6.3 379398
- Section 6.4 380399
- Section 7.1 380399
- Section 7.2 380399
- Section 7.3 381400
- Section 7.4 381400
- Section 7.5 381400
- Section 8.1 382401
- Section 8.2 382401
- Section 8.3 382401
- Section 8.4 383402
- Section 8.5 383402
- Section 8.6 384403

- List of Notation 385404
- Index 387406
- About the Author 391410

- cover cover1411
- copyright page ii413
- title page iii414
- Preface vii418
- Before you go xv426
- 1 Principles of Combinatorics 1430
- 2 Distributions and Combinatorial Proofs 49478
- 3 Algebraic Tools 83512
- 4 Famous Number Families 141570
- 5 Counting Under Equivalence 187616
- 6 Combinatorics on Graphs 225654
- 7 Designs and Codes 271700
- 8 Partially Ordered Sets 317746
- Bibliography 365794
- Hints and Answers to Selected Exercises 369798
- Section 1.1 369798
- Section 1.2 370799
- Section 1.3 370799
- Section 1.4 371800
- Section 1.5 371800
- Section 2.1 371800
- Section 2.2 372801
- Section 2.3 372801
- Section 2.4 373802
- Section 3.1 373802
- Section 3.2 374803
- Section 3.3 374803
- Section 3.4 374803
- Section 3.5 374803
- Section 3.6 375804
- Section 4.1 375804
- Section 4.2 375804
- Section 4.3 376805
- Section 4.4 376805
- Section 5.2 377806
- Section 5.3 377806
- Section 5.4 378807
- Section 5.6 378807
- Section 6.1 378807
- Section 6.2 379808
- Section 6.3 379808
- Section 6.4 380809
- Section 7.1 380809
- Section 7.2 380809
- Section 7.3 381810
- Section 7.4 381810
- Section 7.5 381810
- Section 8.1 382811
- Section 8.2 382811
- Section 8.3 382811
- Section 8.4 383812
- Section 8.5 383812
- Section 8.6 384813

- List of Notation 385814
- Index 387816
- About the Author 391820