The first half of the book walks the reader through methods of counting, both direct elementary methods and the more advanced method of generating functions. Then, in the second half of the book, the reader learns how to apply these methods to fascinating objects, such as graphs, designs, random variables, partially ordered sets, and algorithms. In short, the first half emphasizes depth by discussing counting methods at length; the second half aims for breadth, by showing how numerous the applications of our methods are.New to this fifth edition of A Walk Through Combinatorics is the addition of Instant Check exercises -- more than a hundred in total -- which are located at the end of most subsections. As was the case for all previous editions, the exercises sometimes contain new material that was not discussed in the text, allowing instructors to spend more time on a given topic if they wish to do so. With a thorough introduction into enumeration and graph theory, as well as a chapter on permutation patterns (not often covered in other textbooks), this book is well suited for any undergraduate introductory combinatorics class.
Author(s): Miklos Bona
Edition: 5
Publisher: World Scientific Publishing Company
Year: 2023
Language: English
Commentary: Publisher PDF
Pages: 636
City: New Jersey
Tags: Combinatorial Analysis; Combinatorial Enumeration; Graph Theory
Contents
Foreword
Preface
Acknowledgments
I. Basic Methods
1. Seven Is More Than Six. The Pigeon-Hole Principle
1.1 The Basic Pigeon-Hole Principle
Quick Check
1.2 The Generalized Pigeon-Hole Principle
Quick Check
Exercises
Supplementary Exercises
Solutions to Exercises
2. One Step at a Time. The Method of Mathematical Induction
2.1 Weak Induction
Quick Check
2.2 Strong Induction
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
II. Enumerative Combinatorics
3. There are a Lot of Them. Elementary Counting Problems
3.1 Permutations
Quick Check
3.2 Strings Over a Finite Alphabet
Quick Check
3.3 Choice Problems
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
4. No Matter How You Slice It. The Binomial Theorem and Related Identities
4.1 The Binomial Theorem
Quick Check
4.2 The Multinomial Theorem
Quick Check
4.3 When the Exponent is Not a Positive Integer
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
5. Divide and Conquer. Partitions
5.1 Compositions
Quick Check
5.2 Set Partitions
Quick Check
5.3 Integer Partitions
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
6. Not So Vicious Cycles. Cycles in Permutations
6.1 Cycles in Permutations
6.2 Permutations with Restricted Cycle Structure
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
7. You Shall Not Overcount. The Sieve
7.1 Enumerating the Elements of Intersecting Sets
Quick Check
7.2 Applications of the Sieve Formula
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
8. A Function is Worth Many Numbers. Generating Functions
8.1 Ordinary Generating Functions
8.1.1 Recurrence Relations and Generating Functions
Instant Check
8.1.2 Products of Generating Functions
Instant Check
8.1.2.1 The Catalan Numbers
8.1.3 Compositions of Generating Functions
Instant Check
Quick Check
8.2 Exponential Generating Functions
8.2.1 Recurrence Relations and Exponential Generating Functions
Instant Check
8.2.2 Products of Exponential Generating Functions
Instant Check
8.2.3 Compositions of Exponential Generating Functions
Instant Check
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
III. Graph Theory
9. Dots and Lines. The Origins of Graph Theory
9.1 The Notion of Graphs. Eulerian Trails
Quick Check
9.2 Hamiltonian Cycles
Quick Check
9.3 Directed Graphs
Quick Check
9.4 The Notion of Isomorphisms
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
10. Staying Connected. Trees
10.1 Minimally Connected Graphs
Quick Check
10.2 Minimum-weight Spanning Trees. Kruskal’s Greedy Algorithm
Quick Check
10.3 Adjacency Matrices of Graphs
Quick Check
10.4 The Number of Spanning Trees of a Graph
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
11. Finding A Good Match. Coloring and Matching
11.1 Introduction
Quick Check
11.2 Bipartite Graphs
Quick Check
11.3 Matchings in Bipartite Graphs
11.3.1 Bipartite Graphs with Perfect Matchings
Instant Check
11.3.2 Stable Matchings in Bipartite Graphs
Instant Check
Quick Check
11.4 More Than Two Colors
Quick Check
11.5 Matchings in Graphs That Are Not Bipartite
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
12. Do Not Cross. Planar Graphs
12.1 Euler’s Theorem for Planar Graphs
Quick Check
12.2 Polyhedra
Quick Check
12.3 Coloring Maps
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
IV. Horizons
13. Does it Clique? Ramsey Theory
13.1 Ramsey Theory for Finite Graphs
Quick Check
13.2 Generalizations of the Ramsey Theorem
Quick Check
13.3 Ramsey Theory in Geometry
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
14. So Hard To Avoid. Subsequence Conditions on Permutations
14.1 Pattern Avoidance
Quick Check
14.2 Stack Sortable Permutations
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
15. Who Knows What it Looks Like, But it Exists. The Probabilistic Method
15.1 The Notion of Probability
Quick Check
15.2 Non-constructive Proofs
Quick Check
15.3 Independent Events
15.3.1 The Notion of Independence and Bayes’ Theorem
Instant Check
15.3.2 More Than Two Events
Instant Check
Quick Check
15.4 Expected Values
15.4.1 Linearity of Expectation
Instant Check
15.4.2 Existence Proofs Using Expectation
Instant Check
15.4.3 Conditional Expectation
Instant Check
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
16. At Least Some Order. Partial Orders and Lattices
16.1 The Notion of Partially Ordered Set
Quick Check
16.2 The M¨obius Function of a Poset
Quick Check
16.3 Lattices
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
17. As Evenly As Possible. Block Designs and Error Correcting Codes
17.1 Introduction
17.1.1 Moto-cross Races
17.1.2 Incompatible Computer Programs
Quick Check
17.2 Balanced Incomplete Block Designs
Quick Check
17.3 New Designs From Old
Quick Check
17.4 Existence of Certain BIBDs
17.4.1 A Residual Design of a Projective Plane
Quick Check
17.5 Codes and Designs
17.5.1 Coding Theory
17.5.2 Error Correcting Codes
Instant Check
17.5.3 Formal Definitions About Codes
Instant Check
17.5.4 Perfect Codes
Instant Check
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
18. Are They Really Different? Counting Unlabeled Structures
18.1 Enumeration Under Group Action
18.1.1 Introduction
18.1.2 Groups
18.1.2.1 Groups in General
Instant Check
18.1.2.2 Subgroups and Cosets
Instant Check
18.1.3 Permutation Groups
Instant Check
Quick Check
18.2 Counting Unlabeled Trees
18.2.1 Counting Rooted Non-plane 1–2 Trees
Instant Check
18.2.2 Counting Rooted Non-plane Trees
Instant Check
18.2.3 Counting Unrooted Trees
Instant Check
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
19. The Sooner The Better. Combinatorial Algorithms
19.1 In Lieu of Definitions
Quick Check
19.2 Sorting Algorithms
19.2.1 BubbleSort
Instant Check
19.2.2 MergeSort
Instant Check
19.2.3 Comparing the Growth of Functions
Instant Check
Quick Check
19.3 Algorithms on Graphs
19.3.1 Minimum-cost Spanning Trees, Revisited
Instant Check
19.3.2 Finding the Shortest Path
Instant Check
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
20. Does Many Mean More Than One? Computational Complexity
20.1 Turing Machines
Quick Check
20.2 Complexity Classes
20.2.1 The Class P
Instant Check
20.2.2 The Class NP
20.2.2.1 The Class coNP
20.2.2.2 Nondeterministic Turing Machines
Instant Check
20.2.3 NP-complete Problems
Instant Check
20.2.4 Other Complexity Classes
Instant Check
Quick Check
Notes
Exercises
Supplementary Exercises
Solutions to Exercises
Bibliography
Index
