Combinatorics

Author: Brian
Publisher:
Publish Date: 2004-02-01
Features: The 3rd edition contains material sufficient for two semester courses. The first semester can focus on counting methods, while the second semester focuses on graph theory. A brief overview of the content of each chapter and the relationships between the chapters are as follows: Chapter 1 is an introductory chapter. Chapter 2 is the pigeonhole principle, which must at least be discussed in a condensed form. However, this does little to help understand some difficult applications of the pigeonhole principle and the Ramsey theorem in later chapters. Chapters 3 to 8 mainly deal with certain properties of sequences of counting results and counting techniques. Chapter 4 is about the generation methods of permutations and combinations, and as mentioned above, it also includes an introduction to partially ordered sets and equivalence relations. However, except for the section on partially ordered sets in Chapter 5, the chapters after Chapter 4 are basically unrelated to Chapter 4, so Chapter 4 can be omitted or compressed. Chapter 5 discusses the properties of binomial coefficients, and Chapter 6 covers the inclusion-exclusion principle. Chapter 7 is relatively long, discussing the solution of recurrence relations and the use of generating functions in counting. Chapter 8 mainly involves Catalan numbers, classes, and second-kind Stirling numbers, as well as partition numbers. The chapters that follow are unrelated to Chapter 8. Chapter 9 discusses the matching problem of bipartite graphs (even graphs). Although this book introduces bipartite graphs before graph theory, the chapters on graph theory later are basically unrelated to this chapter. Except for the application of matching theory to Latin squares, the discussion of combinatorial designs in Chapter 10 is independent of the other chapters. However, at the end of Section 10.4, the matching theory developed in Chapter 9 is used. Chapters 11 and 13 involve extensive discussions on graph theory, with a focus on graph theory algorithms. Chapter 12 covers directed graphs and networks. Chapter 14 deals with counting problems under the action of permutation groups, where many of the previous counting concepts are indeed used. Except for the last example, this chapter is independent of the graph theory and combinatorial design chapters. After Chapter 14, some solutions and hints for the nearly 600 exercises in this book are provided. This book is a lively and precise introduction to combinatorics. It is based on the fundamental combinatorial theorems in combinatorics, including the well-known pigeonhole principle, and expands discussions on permutations and combinations, binomial coefficients, generating functions, and combinatorial structures, as well as graph image processing techniques. It is worth mentioning that this book proposes an excellent polynomial counting theory that does not require readers to have advanced combinatorics knowledge. Due to its vivid and easy-to-understand content and slightly broad coverage, it is particularly suitable for students to study and read.