Enhanced descriptions from Syndetics:

Focusing on the core material of value to students in a wide variety of fields, this book presents a broad comprehensive survey of modern combinatorics at an introductory level. The author begins with an introduction of concepts fundamental to all branches of combinatorics in the context of combinatorial enumeration. Chapter 2 is devoted to enumeration problems that involve counting the number of equivalence classes of an equivalence relation. Chapter 3 discusses somewhat less direct methods of enumeration, the principle of inclusion and exclusion and generating functions. The remainder of the book is devoted to a study of combinatorial structures.

Table of contents provided by Syndetics

• Preface (p. v)
• 1 An Introduction to Enumeration
• Section 1 Elementary Counting Principles (p. 1)
• What Is Combinatorics? (p. 1)
• The Sum Principle (p. 1)
• The Product Principle (p. 3)
• Ordered Paris (p. 4)
• Cartesian Product of Sets (p. 4)
• The General Form of the Product Principle (p. 4)
• Lists with Distinct Elements (p. 5)
• Lists with Repeats Allowed (p. 7)
• Stirling's Approximation for n! (p. 7)
• Exercises (p. 8)
• Section 2 Functions and the Pigeonhole Principle (p. 14)
• Functions (p. 14)
• Relations (p. 15)
• Definition of Function (p. 15)
• The Number of Functions (p. 16)
• One-to-One Functions (p. 16)
• Onto Functions and Bijections (p. 18)
• The Extended Pigeonhole Principle (p. 20)
• Ramsey Numbers (p. 21)
• *Using Functions to Describe Ramsey Numbers (p. 22)
• Exercises (p. 23)
• Section 3 Subsets (p. 27)
• The Number of Subsets of a Set (p. 27)
• Binomial Coefficients (p. 28)
• [kappa]-Element Subsets (p. 29)
• Labelings with Two Labels (p. 29)
• Pascal's Triangle (p. 30)
• How Fast Does the Number of Subsets Grow? (p. 33)
• Recursion and Iteration (p. 34)
• Exercises (p. 35)
• Section 4 Using Binomial Coefficients (p. 40)
• The Binomial Theorem (p. 40)
• Multinomial Coefficients (p. 43)
• The Multinomial Theorem (p. 45)
• Multinomial Coefficients from Binomial Coefficients (p. 46)
• Lattice Paths (p. 46)
• Exercises (p. 50)
• Section 5 Mathematical Induction (p. 54)
• The Principle of Induction (p. 54)
• Proving That Formulas Work (p. 54)
• Informal Induction Proofs (p. 56)
• Inductive Definition (p. 56)
• The General Sum Principle (p. 58)
• An Application to Computing (p. 59)
• Proving That a Recurrence Works (p. 60)
• A Sample of the Strong Form of Mathematical Induction (p. 61)
• Double Induction (p. 62)
• Ramsey Numbers (p. 62)
• Exercises (p. 64)
• Suggested Reading for Chapter 1 (p. 68)
• 2 Equivalence Relations, Partitions, and Multisets
• Section 1 Equivalence Relations (p. 69)
• The Idea of Equivalence (p. 69)
• Equivalence Relations (p. 70)
• Circular Arrangements (p. 70)
• Equivalence Classes (p. 72)
• Counting Equivalence Classes (p. 73)
• The Inverse Image Relation (p. 74)
• The Number of Partitions with Specified Class Sizes (p. 77)
• Exercises (p. 79)
• Section 2 Distributions and Multisets (p. 83)
• The Idea of a Distribution (p. 83)
• Ordered Distributions (p. 87)
• Distributing Identical Objects to Distinct Recipients (p. 89)
• Ordered Compositions (p. 92)
• Multisets (p. 93)
• Broken Permutations of a Set (p. 94)
• Exercises (p. 96)
• Section 3 Partitions and Stirling Numbers (p. 99)
• Partitions of an m-Element Set into n Classes (p. 99)
• Stirling's Triangle of the Second Kind (p. 99)
• The Inverse Image Partition of a Function (p. 100)
• Onto Functions and Stirling Numbers (p. 101)
• Stirling Numbers of the First Kind (p. 101)
• Stirling Numbers of the Second Kind as Polynomial Coefficients (p. 102)
• Stirling's Triangle of the First Kind (p. 104)
• The Total Number of Partitions of a Set (p. 105)
• Exercises (p. 106)
• Section 4 Partitions of Integers (p. 110)
• Distributing Identical Objects to Identical Recipients (p. 110)
• Type Vector of a Partition and Decreasing Lists (p. 110)
• The Number of Partitions of m into n Parts (p. 111)
• Ferrers Diagrams (p. 112)
• Conjugate Partitions (p. 112)
• The Total Number of Partitions of m (p. 114)
• Exercises (p. 115)
• Suggested Reading for Chapter 2 (p. 118)
• 3 Algebraic Counting Techniques
• Section 1 The Principle of Inclusion and Exclusion (p. 119)
• The Size of a Union of Three Overlapping Sets (p. 119)
• The Number of Onto Functions (p. 120)
• Counting Arrangements with or without Certain Properties (p. 122)
• The Basic Counting Functions N[greater than or equal] and N= (p. 123)
• The Principle of Inclusion and Exclusion (p. 124)
• Onto Functions and Stirling Numbers (p. 126)
• Examples of Using the Principle of Inclusion and Exclusion (p. 127)
• Derangements (p. 131)
• Level Sums and Inclusion-Exclusion Counting (p. 131)
• Examples of Level Sum Inclusion and Exclusion (p. 133)
• Exercises (p. 134)
• Section 2 The Concept of a Generating Function (p. 138)
• Symbolic Series (p. 138)
• Power Series (p. 143)
• What Is a Generating Function? (p. 144)
• The Product Principle for Generating Functions (p. 145)
• The Generating Function for Multisets (p. 146)
• Polynomial Generating Functions (p. 147)
• Extending the Definition of Binomial Coefficients (p. 148)
• The Extended Binomial Theorem (p. 148)
• Exercises (p. 149)
• Section 3 Applications to Partitions and Inclusion-Exclusion (p. 154)
• Polya's Change-Making Example (p. 154)
• Systems of Linear Recurrences from Products of Geometric Series (p. 155)
• Generating Functions for Integer Partitions (p. 158)
• Generating Functions Sometimes Replace Inclusion-Exclusion (p. 162)
• Generating Functions and Inclusion-Exclusion on Level Sums (p. 163)
• Exercises (p. 165)
• Section 4 Recurrence Relations and Generating Functions (p. 169)
• The Idea of a Recurrence Relation (p. 169)
• How Generating Functions Are Relevant (p. 170)
• Second-Order Linear Recurrence Relations (p. 172)
• The Original Fibonacci Problem (p. 177)
• General Techniques (p. 178)
• Exercises (p. 180)
• Section 5 Exponential Generating Functions (p. 184)
• Indicator Functions (p. 184)
• Exponential Generating Functions (p. 184)
• Products of Exponential Generating Functions (p. 185)
• The Exponential Generating Function for Onto Functions (p. 188)
• The Product Principle for Exponential Generating Functions (p. 189)
• Putting Lists Together and Preserving Order (p. 190)
• Exponential Generating Functions for Words (p. 192)
• Solving Recurrence Relations with Other Generating Functions (p. 193)
• Using Calculus with Exponential Generating Functions (p. 194)
• Exercises (p. 196)
• Suggested Reading for Chapter 3 (p. 198)
• 4 Graph Theory
• Section 1 Eulerian Walks and the Idea of Graphs (p. 200)
• The Concept of a Graph (p. 200)
• Multigraphs and the Konigsberg Bridge Problem (p. 202)
• Walks, Paths, and Connectivity (p. 204)
• Eulerian Graphs (p. 206)
• Exercises (p. 208)
• Section 2 Trees (p. 211)
• The Chemical Origins of Trees (p. 211)
• Basic Facts about Trees (p. 212)
• Spanning Trees (p. 215)
• The Number of Trees (p. 217)
• Exercises (p. 222)
• Section 3 Shortest Paths and Search Trees (p. 226)
• Rooted Trees (p. 226)
• Breadth-First Search Trees (p. 228)
• Shortest Path Spanning Trees (p. 229)
• Bridges (p. 231)
• Depth-First Search (p. 232)
• Depth-First Numbering (p. 233)
• Finding Bridges (p. 234)
• An Efficient Bridge-Finding Algorithm for Computers (p. 235)
• Backtracking (p. 235)
• Decision Graphs (p. 237)
• Exercises (p. 238)
• Section 4 Isomorphism and Planarity (p. 242)
• The Concept of Isomorphism (p. 242)
• Checking Whether Two Graphs Are Isomorphic (p. 243)
• Planarity (p. 245)
• Euler's Formula (p. 246)
• An Inequality to Check for Nonplanarity (p. 246)
• Exercises (p. 249)
• Section 5 Digraphs (p. 252)
• Directed Graphs (p. 252)
• Walks and Connectivity (p. 253)
• Tournament Digraphs (p. 253)
• Hamiltonian Paths (p. 254)
• Transitive Closure (p. 255)
• Reachability (p. 256)
• Modifying Breadth-First Search for Strict Reachability (p. 257)
• Orientable Graphs (p. 258)
• Graphs without Bridges Are Orientable (p. 258)
• Exercises (p. 259)
• Section 6 Coloring (p. 263)
• The Four-Color Theorem (p. 263)
• Chromatic Number (p. 263)
• Maps and Duals (p. 264)
• The Five-Color Theorem (p. 265)
• Kempe's Attempted Proof (p. 268)
• Using Backtracking to Find a Coloring (p. 269)
• Exercises (p. 272)
• Section 7 Graphs and Matrices (p. 277)
• Adjacency Matrix of a Graph (p. 277)
• Matrix Powers and Walks (p. 277)
• Connectivity and Transitive Closure (p. 279)
• Boolean Operations (p. 280)
• The Matrix-Tree Theorem (p. 281)
• The Number of Eulerian Walks in a Digraph (p. 284)
• Exercises (p. 285)
• Suggested Reading for Chapter 4 (p. 290)
• 5 Matching and Optimization
• Section 1 Matching Theory (p. 291)
• The Idea of Matching (p. 291)
• Making a Bigger Matching (p. 294)
• A Procedure for Finding Alternating Paths in Bipartite Graphs (p. 295)
• Constructing Bigger Matchings (p. 296)
• Testing for Maximum-Sized Matchings by Means of Vertex Covers (p. 297)
• Hall's "Marriage" Theorem (p. 299)
• Term Rank and Line Covers of Matrices (p. 300)
• Permutation Matrices and the Birkhoff-von Neumann Theorem (p. 301)
• Finding Alternating Paths in Nonbipartite Graphs (p. 302)
• Exercises (p. 308)
• Section 2 The Greedy Algorithm (p. 314)
• The SDR Problem with Representatives That Cost Money (p. 314)
• The Greedy Method (p. 314)
• The Greedy Algorithm (p. 316)
• Matroids Make the Greedy Algorithm Work (p. 316)
• How Much Time Does the Algorithm Take? (p. 318)
• The Greedy Algorithm and Minimum-Cost Independent Sets (p. 320)
• The Forest Matroid of a Graph (p. 321)
• Minimum-Cost Spanning Trees (p. 322)
• Exercises (p. 324)
• Section 3 Network Flows (p. 328)
• Transportation Networks (p. 328)
• The Concept of Flow (p. 328)
• Cuts in Networks (p. 330)
• Flow-Augmenting Paths (p. 332)
• The Labeling Algorithm for Finding Flow-Augmenting Paths (p. 333)
• The Max-Flow Min-Cut Theorem (p. 336)
• More Efficient Algorithms (p. 337)
• Exercises (p. 340)
• Section 4 Flows, Connectivity, and Matching (p. 345)
• Connectivity and Menger's Theorem (p. 345)
• Flows, Matchings, and Systems of Distinct Representatives (p. 348)
• Minimum-Cost SDRs (p. 350)
• Minimum-Cost Matchings and Flows with Edge Costs (p. 352)
• The Potential Algorithm for Finding Minimum-Cost Paths (p. 353)
• Finding a Maximum Flow of Minimum Cost (p. 354)
• Exercises (p. 356)
• Suggested Reading for Chapter 5 (p. 358)
• 6 Combinatorial Designs
• Section 1 Latin Squares and Graeco-Latin Squares (p. 359)
• How Latin Squares Are Used (p. 359)
• Randomization for Statistical Purposes (p. 360)
• Orthogonal Latin Squares (p. 362)
• Euler's 36-Officers Problem (p. 363)
• Congruence Modulo an Integer n (p. 363)
• Using Arithmetic Modulo n to Construct Latin Squares (p. 365)
• Orthogonality and Arithmetic Modulo n (p. 367)
• Compositions of Orthogonal Latin Squares (p. 368)
• Orthogonal Arrays and Latin Squares (p. 372)
• The Construction of a 10 by 10 Graeco-Latin Square (p. 375)
• Exercises (p. 377)
• Section 2 Block Designs (p. 379)
• How Block Designs Are Used (p. 379)
• Basic Relationships among the Parameters (p. 380)
• The Incidence Matrix of a Design (p. 381)
• An Example of a BIBD (p. 383)
• Isomorphism of Designs (p. 383)
• The Dual of a Design (p. 384)
• Symmetric Designs (p. 385)
• The Necessary Conditions Need Not Be Sufficient (p. 387)
• Exercises (p. 388)
• Section 3 Construction and Resolvability of Designs (p. 391)
• A Problem That Requires a Big Design (p. 391)
• Cyclic Designs (p. 391)
• Resolvable Designs (p. 395)
• [infinity]-Cyclic Designs (p. 396)
• Triple Systems (p. 397)
• Kirkman's Schoolgirl Problem (p. 398)
• Constructing New Designs from Old (p. 399)
• Complementary Designs (p. 400)
• Unions of Designs (p. 401)
• Product Designs (p. 402)
• Composition of Designs (p. 402)
• The Construction of Kirkman Triple Systems (p. 403)
• Exercises (p. 406)
• Section 4 Affine and Projective Planes (p. 409)
• Affine Planes (p. 409)
• Postulates for Affine Planes (p. 412)
• The Concept of a Projective Plane (p. 414)
• Basic Facts about Projective Planes (p. 417)
• Projective Planes and Block Designs (p. 418)
• Planes and Resolvable Designs (p. 419)
• Planes and Orthogonal Latin Squares (p. 420)
• Exercises (p. 422)
• Section 5 Codes and Designs (p. 424)
• The Concept of an Error-Correcting Code (p. 424)
• Hamming Distance (p. 425)
• Perfect Codes (p. 427)
• Linear Codes (p. 429)
• The Hamming Codes (p. 431)
• Constructing Designs from Codes (p. 433)
• Highly Balanced Designs (p. 434)
• t-Designs (p. 435)
• Codes and Latin Squares (p. 436)
• Exercises (p. 438)
• Suggested Reading for Chapter 6 (p. 440)
• 7 Ordered Sets
• Section 1 Partial Orderings (p. 442)
• What Is an Ordering? (p. 442)
• Linear Orderings (p. 444)
• Maximal and Minimal Elements (p. 445)
• The Diagram and Covering Graph (p. 446)
• Ordered Sets as Transitive Closures of Digraphs (p. 449)
• Trees as Ordered Sets (p. 449)
• Weak Orderings (p. 450)
• Interval Orders (p. 451)
• Exercises (p. 454)
• Section 2 Linear Extensions and Chains (p. 458)
• The Idea of a Linear Extension (p. 458)
• Dimension of an Ordered Set (p. 459)
• Topological Sorting Algorithms (p. 460)
• Chains in Ordered Sets (p. 460)
• Chain Decompositions of Posets (p. 462)
• Finding Chain Decompositions (p. 464)
• Alternating Walks (p. 467)
• Finding Alternating Walks (p. 470)
• Exercises (p. 471)
• Section 3 Lattices (p. 477)
• What Is a Lattice? (p. 477)
• The Partition Lattice (p. 479)
• The Bond Lattice of a Graph (p. 481)
• The Algebraic Description of Lattices (p. 482)
• Exercises (p. 484)
• Section 4 Boolean Algebras (p. 488)
• The Idea of a Complement (p. 488)
• Boolean Algebras (p. 490)
• Boolean Algebras of Statements (p. 491)
• Combinatorial Gate Networks (p. 494)
• Boolean Polynomials (p. 496)
• DeMorgan's Laws (p. 496)
• Disjunctive Normal Form (p. 497)
• All Finite Boolean Algebras Are Subset Lattices (p. 499)
• Exercises (p. 501)
• Section 5 Mobius Functions (p. 505)
• A Review of Inclusion and Exclusion (p. 505)
• The Zeta Matrix (p. 506)
• The Mobius Matrix (p. 508)
• The Mobius Function (p. 509)
• Equations That Describe the Mobius Function (p. 511)
• The Number-Theoretic Mobius Function (p. 513)
• The Number of Connected Graphs (p. 515)
• A General Method of Computing Mobius Functions of Lattices (p. 517)
• The Mobius Function of the Partition Lattice (p. 518)
• Exercises (p. 519)
• Section 6 Products of Orderings (p. 523)
• The Idea of a Product (p. 523)
• Products of Ordered Sets and Mobius Functions (p. 524)
• Products of Ordered Sets and Dimension (p. 526)
• Width and Dimension of Ordered Sets (p. 528)
• Exercises (p. 529)
• Suggested Reading for Chapter 7 (p. 531)
• 8 Enumeration under Group Action
• Section 1 Permutation Groups (p. 532)
• Permutations and Equivalence Relations (p. 532)
• The Group Properties (p. 535)
• Powers of Permutations (p. 537)
• Permutation Groups (p. 538)
• Associating a Permutation with a Geometric Motion (p. 539)
• Abstract Groups (p. 540)
• Exercises (p. 542)
• Section 2 Groups Acting on Sets (p. 545)
• Groups Acting on Sets (p. 545)
• Orbits as Equivalence Classes (p. 547)
• The Subgroup Fixing a Point and Cosets (p. 548)
• The Size of a Subgroup (p. 551)
• The Subgroup Generated by a Set (p. 552)
• The Cycles of a Permutation (p. 553)
• Exercises (p. 557)
• Section 3 Polya's Enumeration Theorem (p. 562)
• The Cauchy-Frobenius-Burnside Theorem (p. 562)
• Enumerators of Colorings (p. 564)
• Generating Functions for Orbits (p. 566)
• Using the Orbit-Fixed Point Lemma (p. 568)
• Orbits of Functions (p. 570)
• The Orbit Enumerator for Functions (p. 572)
• How Cycle Structure Interacts with Colorings (p. 573)
• The Polya-Redfield Theorem (p. 575)
• Exercises (p. 578)
• Suggested Reading for Chapter 8 (p. 580)
• Answers to Exercises (p. 581)
• Index (p. 642)