文件名称：Combinatorics and Graph Theory
文件大小：1.16MB
文件格式：PDF
更新时间：2021-12-23 12:34:50
数学
组合数学与图论，英文版。内置高清图片，缺陷没有书签。 目录如下： 1 Fundamentals 7 1.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 Combinations and permutations . . . . . . . . . . . . . . . . . 11 1.3 Binomial coefficients . . . . . . . . . . . . . . . . . . . . . . . 16 1.4 Bell numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.5 Choice with repetition . . . . . . . . . . . . . . . . . . . . . . 27 1.6 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . 32 1.7 Sperner’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . 36 1.8 Stirling numbers . . . . . . . . . . . . . . . . . . . . . . . . . 39 2 Inclusion-Exclusion 45 2.1 The Inclusion-Exclusion Formula . . . . . . . . . . . . . . . . . 45 2.2 Forbidden Position Permutations . . . . . . . . . . . . . . . . . 48 3 3 Generating Functions 53 3.1 Newton’s Binomial Theorem . . . . . . . . . . . . . . . . . . . 53 3.2 Exponential Generating Functions . . . . . . . . . . . . . . . . 56 3.3 Partitions of Integers . . . . . . . . . . . . . . . . . . . . . . . 59 3.4 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . 62 3.5 Catalan Numbers . . . . . . . . . . . . . . . . . . . . . . . . . 66 4 Systems of Distinct Representatives 71 4.1 Existence of SDRs . . . . . . . . . . . . . . . . . . . . . . . . 72 4.2 Partial SDRs . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.3 Latin Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.4 Introduction to Graph Theory . . . . . . . . . . . . . . . . . . 83 4.5 Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5 Graph Theory 91 5.1 The Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.2 Euler Circuits and Walks . . . . . . . . . . . . . . . . . . . . . 96 5.3 Hamilton Cycles and Paths . . . . . . . . . . . . . . . . . . . 100 5.4 Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . 103 5.5 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.6 Optimal Spanning Trees . . . . . . . . . . . . . . . . . . . . 108 5.7 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5.8 Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.9 The Chromatic Polynomial . . . . . . . . . . . . . . . . . . . 124 5.10 Coloring Planar Graphs . . . . . . . . . . . . . . . . . . . . . 125 5.11 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . 129 6 P´olya–Redfield Counting 135 6.1 Groups of Symmetries . . . . . . . . . . . . . . . . . . . . . 137 6.2 Burnside’s Theorem . . . . . . . . . . . . . . . . . . . . . . 140 6.3 P´olya-Redfield Counting . . . . . . . . . . . . . . . . . . . . 146 A Hints 151 Index 153