Combinatorics, Second Edition

Description

Combinatorics, Second Edition is a well-rounded, general introduction to the subjects of enumerative, bijective, and algebraic combinatorics. The textbook emphasizes bijective proofs, which provide elegant solutions to counting problems by setting up one-to-one correspondences between two sets of combinatorial objects. The author has written the textbook to be accessible to readers without any prior background in abstract algebra or combinatorics. Part I of the second edition develops an array of mathematical tools to solve counting problems: basic counting rules, recursions, inclusion-exclusion techniques, generating functions, bijective proofs, and linear algebraic methods. These tools are used to analyze combinatorial structures such as words, permutations, subsets, functions, graphs, trees, lattice paths, and much more. Part II cover topics in algebraic combinatorics including group actions, permutation statistics, symmetric functions, and tableau combinatorics. This edition provides greater coverage of the use of ordinary and exponential generating functions as a problem-solving tool. Along with two new chapters, several new sections, and improved exposition throughout, the textbook is brimming with many examples and exercises of various levels of difficulty. Content: Cover Half Title Discrete Mathematics and Its Application Title Copyright Dedication Contents Preface to the Second Edition Introduction Part I Counting Chapter 1 Basic Counting 1.1 the Product Rule 1.2 the Sum Rule 1.3 Counting Words and Permutations 1.4 Counting Subsets 1.5 Counting Anagrams 1.6 Counting Rules for Set Operations 1.7 Probability 1.8 Lotteries and Card Games 1.9 Conditional Probability and Independence 1.10 Counting Functions 1.11 Cardinality and the Bijection Rule 1.12 Counting Multisets and Compositions 1.13 Counting Balls in Boxes 1.14 Counting Lattice Paths1.15 Proofs of the Sum Rule and the Product Rule Summary Exercises Chapter 2 Combinatorial Identities and Recursions 2.1 Initial Examples of Combinatorial Proofs 2.2 the Geometric Series Formula 2.3 the Binomial Theorem 2.4 the Multinomial Theorem 2.5 More Binomial Coefficient Identities 2.6 Sums of Powers of Integers 2.7 Recursions 2.8 Recursions for Multisets and Anagrams 2.9 Recursions for Lattice Paths 2.10 Catalan Recursions 2.11 Integer Partitions 2.12 Set Partitions 2.13 Surjections, Balls in Boxes, and Equivalence Relations 2.14 Stirling Numbers and Rook Theory2.15 Stirling Numbers and Polynomials 2.16 Solving Recursions with Constant Coefficients Summary Exercises Chapter 3 Counting Problems in Graph Theory 3.1 Graphs and Digraphs 3.2 Walks and Matrices 3.3 Directed Acyclic Graphs and Nilpotent Matrices 3.4 Vertex Degrees 3.5 Functional Digraphs 3.6 Cycle Structure of Permutations 3.7 Counting Rooted Trees 3.8 Connectedness and Components 3.9 Forests 3.10 Trees 3.11 Counting Trees 3.12 Pruning Maps 3.13 Bipartite Graphs 3.14 Matchings and Vertex Covers 3.15 Two Matching Theorems 3.16 Graph Coloring3.17 Spanning Trees 3.18 the Matrix-tree Theorem 3.19 Eulerian Tours Summary Exercises Chapter 4 Inclusion-exclusion, Involutions, and Möbius Inversion 4.1 the Inclusion-exclusion Formula 4.2 Examples of the Inclusion-exclusion Formula 4.3 Surjections and Stirling Numbers 4.4 Euler's F Function 4.5 Derangements 4.6 Involutions 4.7 Involutions Related to Inclusion-exclusion 4.8 Generalized Inclusion-exclusion Formulas 4.9 Möbius Inversion in Number Theory 4.10 Partially Ordered Sets 4.11 Möbius Inversion for Posets 4.12 Product Posets Summary Exercises Chapter 5 Generating Functions5.1 What Is a Generating Function? 5.2 Convergence of Power Series 5.3 Examples of Analytic Power Series 5.4 Operations on Power Series 5.5 Solving Recursions with Generating Functions 5.6 Evaluating Summations with Generating Functions 5.7 Generating Function for Derangements 5.8 Counting Rules for Weighted Sets 5.9 Examples of the Product Rule for Weighted Sets 5.10 Generating Functions for Trees 5.11 Tree Bijections 5.12 Exponential Generating Functions 5.13 Stirling Numbers of the First Kind 5.14 Stirling Numbers of the Second Kind