Active student engagement is key to this classroom-tested combinatorics text, boasting 1200+ carefully designed problems, ten mini-projects, section warm-up problems, and chapter opening problems. The author – an award-winning teacher – writes in a conversational style, keeping the reader in mind on every page. Students will stay motivated through glimpses into current research trends and open problems as well as the history and global origins of the subject. All essential topics are covered, including Ramsey theory, enumerative combinatorics including Stirling numbers, partitions of integers, the inclusion-exclusion principle, generating functions, introductory graph theory, and partially ordered sets. Some significant results are presented as sets of guided problems, leading readers to discover them on their own. More than 140 problems have complete solutions and over 250 have hints in the back, making this book ideal for self-study. Ideal for a one semester upper undergraduate course, prerequisites include the calculus sequence and familiarity with proofs.
Author(s): Shahriar Shahriari
Series: Cambridge Mathematical Textbooks
Publisher: Cambridge University Press
Year: 2021
Language: English
Tags: math,mathematics,combinatorics,textbook
Cover
Half-title
Series information
Title page
Copyright information
Dedication
Contents
Preface
Acknowledgments
Introduction
What is Combinatorics?
Typical Problems
How Do We “Count”?
1 Induction and Recurrence Relations
1.1 Induction
Problems
1.2 Strong Induction
Problems
1.3 Recurrence Relations
Problems
1.4 Linear Recurrence Relations; Unwinding a Recurrence Relation[sup(star)]
Problems
1.5 Open Problems and Conjectures
2 The Pigeonhole Principle and Ramsey Theory
2.1 The Pigeonhole Principle
Problems
2.2 Multisets and Graphs
Problems
2.3 Ramsey Theory
Problems
2.4 Schur, Van der Waerden, and Graph Ramsey Numbers[sup(star)]
Problems
2.5 Open Problems and Conjectures
3 Counting, Probability, Balls and Boxes
3.1 The Addition, Multiplication, and Subtraction Principles
Problems
3.2 Probability
Problems
3.3 A Framework for Counting Questions: The Counting Table
Problems
3.4 Bijective Maps and Counting
Problems
Collaborative Mini-project 1: Counting Monochromatic Triangles
Collaborative Mini-project 2: Binomial Coefficients
Collaborative Mini-project 3: Stirling Numbers
4 Permutations and Combinations
4.1 Permutations of a Set and Falling Factorials
Problems
4.2 Combinations of Sets and Binomial Coefficients
Problems
4.3 Permutations of Multisets and Multinomial Coefficients
Problems
4.4 Combinations of Multisets and Counting Integer Solutions
Problems
4.5 More Problems
Problems
5 Binomial and Multinomial Coefficients
5.1 Binomial Coefficients
Problems
5.2 The Binomial Theorem
Problems
5.3 Multinomials and the Multinomial Theorem
Problems
5.4 Binomial Inversion, Sums of Powers, Lattice Paths, Ming–Catalan Numbers, and More[sup(star)]
Problems
5.5 Open Problems and Conjectures
6 Stirling Numbers
6.1 Stirling Numbers of the Second Kind
Problems
6.2 Stirling Numbers of the First Kind
Problems
6.3 How Are the Stirling Numbers Related?
Problems
7 Integer Partitions
7.1 Partitions of an Integer
Problems
7.2 Asymptotics, Pentagonal Number Theorem, and More[sup(star)]
Problems
7.3 Open Problems and Conjectures
Colour Plates
Collaborative Mini-project 4: Generating Functions
Collaborative Mini-project 5: Graphic Sequences and Planar Graphs
Collaborative Mini-project 6: Connectivity of Graphs
8 The Inclusion–Exclusion Principle
8.1 The Inclusion–Exclusion Principle
Problems
8.2 Combinations of a Multiset
Problems
8.3 Permutations with Forbidden Positions
Problems
9 Generating Functions
9.1 Ordinary Generating Functions
Problems
9.2 Combinations of Multisets and Solving Recurrence Relations
Problems
9.3 Exponential Generating Functions
Problems
9.4 Generating Functions for Partitions, Stirling Numbers,Bernoulli Numbers, and More[sup(star)]
Problems
Interregnum: Counting Table Completed
Collaborative Mini-project 7: Ming–Catalan Numbers
Collaborative Mini-project 8: Sperner's Theorem
10 Graph Theory
10.1 Graphic Sequences
Problems
10.2 Paths, Cycles, and Trees
Problems
10.3 Bipartite Graphs
Problems
10.4 Eulerian Trails and Circuits
Problems
10.5 Hamiltonian Paths and Cycles
Problems
10.6 Planar Graphs and the Tiling of the Plane
Problems
10.7 Graph Coloring and More[sup(star)]
Problems
10.8 Open Problems and Conjectures
Collaborative Mini-project 9: Cayley's Tree Formula
Collaborative Mini-project 10: Incidence Matrices and Bipartite Graphs
11 Posets, Matchings, and Boolean Lattices
11.1 Posets, Total Orders, and Hasse Diagrams
Problems
11.2 Chains, Antichains, and Dilworth’s Theorem
Problems
11.3 Matchings and the Marriage Theorem
Problems
11.4 Boolean Lattices: Symmetric Chains, Theorems of Sperner, and Erdős–Ko–Rado[sup(star)]
Problems
11.5 Boolean Lattices and Graphs: Ramsey Theory Extended[sup(star)]
Problems
11.6 Möbius Inversion: Inclusion–Exclusion Extended[sup(star)]
Problems
11.7 Open Problems and Conjectures
Appendix A Short Answers for Warm-Up Problems
Appendix B Hints for Selected Problems
Appendix C Short Answers for Selected Problems
Appendix D Complete Solutions for Selected Problems
Bibliography
Index
