The subject of combinatorics is so vast that the author of a textbook faces a difficult decision as to what topics to include.There is no more-or-less canonical corpus as in such other subjects as number theory and com-plex variable theory.Miklos Bona has succeeded admirably in blending classic results that would be on anyone’s list for inclusion in a textbook,a sprinkling of more advanced topics that are essential for further study of combinatorics,and a taste of recent work bringing the reader to the frontiers of current research.All three items are conveyed in an engag-ing style,with many interesting examples and exercises.A worthy fea-ture of the book is the many exercises that come with complete solutions.There are also numerous exercises without solutions that can be assigned for homework.
Some relatively advanced topics covered by Bona include permutations with restricted cycle structure,the Matrix-Tree theorem,Ramsey theory(going well beyond the classical Ramsey’s theorem for graphs),the prob-abilistic method,and the Mobius function of a partially ordered set.Any of these topics could be a springboard for a subsequent course or read-ing project which will further convince the student of the extraordinary richness,variety,depth,and applicability of combinatorics.The most un-usual topic covered by Bona is pattern avoidance in permutations and the connection with stack sortable permutations.This is are latively re-cent research area in which most of the work has been entirely elemen-tary.An undergraduate student eager to do some original research has a good chance of making a worthwhile contribution in the area of pattern avoidance.
I only wish that when I was a student beginning to learn combinatorics there was a textbook available as attractive as Bona's.Students today are fortunate to be able to sample the treasures available herein.
Richard Stanley
Cambridge,Massachusetts
February6,2002
Table of Contents
Chapter1 Seven Is More Than Six.The Pigeon－Hole Principle 1
1.1 The Basic Pigeon－Hole Principle 1
Quick Check 3
1.2 The Generalized Pigeon－Hole Principle 4
Quick Chek 10
Exercises 10
Supplementary Exercises 12
Solutions to Exercises 14
Chapter2 One Step at a Time.The Method of Mathematical Induction 23
2.1 Weak Induction 23
Quick Check 28
2.2 Strong Induction 29
Quick Check 30
Exercises 31
Supplementary Exercises 33
Solutions to Exercises 35
Chapter3 There Are A Lot Of Them.Elementary Counting Problems 43
3.1 Permutations 43
Quick Check 46
3.2 Strings over a Finite Alphabet 46
Quick Check 50
3.3 Choice Problems 50
Quick Check 53
Exercises 54
Supplementary Exercises 58
Solutions to Exercises 60
Chapter4 No Matter How You Slice It.The Binomial Theorem and Related Identities 73
4.1 The Binomial Theorem 73
Quick Check 78
4.2 The Multinomial Theorem 78
Quick Check 81
4.3 When the Exponent Is Not a Positive Integer 81
Quick Check 83
Exercises 83
Supplementary Exercises 87
Solutions to Exercises 90
