An Invitation to Combinatorics

Description

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. 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