Introduction to Combinatorics

W.D. Wallis is Emeritus Professor of Mathematics at Southern Illinois University. His research interests include combinatorial designs, Latin squares, graph labeling, one-factorizations, and intelligent networks. Dr. Wallis is the author of Introduction to Combinatorial Designs, Second Edition (CRC Press, 2007). J.C. George is an assistant professor of mathematics in the Division of Mathematics and Natural Sciences at Gordon College in Barnesville, Georgia. His research interests include one-factorizations, graph products, and the relationships of algebraic structures to combinatorial objects.

Introduction
Some Combinatorial Examples
Sets, Relations and Proof Techniques
Two Principles of Enumeration
Graphs
Systems of Distinct Representatives





Fundamentals of Enumeration
Permutations and Combinations
Applications of P(n, k) and (n k)
Permutations and Combinations of Multisets
Applications and Subtle Errors
Algorithms





The Pigeonhole Principle and Ramsey’s Theorem
The Pigeonhole Principle
Applications of the Pigeonhole Principle
Ramsey’s Theorem — the Graphical Case
Ramsey Multiplicity
Sum-Free Sets
Bounds on Ramsey Numbers
The General Form of Ramsey’s Theorem





The Principle of Inclusion and Exclusion
Unions of Events
The Principle
Combinations with Limited Repetitions
Derangements





Generating Functions and Recurrence Relations
Generating Functions
Recurrence Relations
From Generating Function to Recurrence
Exponential Generating Functions





Catalan, Bell and Stirling Numbers
Introduction
Catalan Numbers
Stirling Numbers of the Second Kind
Bell Numbers
Stirling Numbers of the First Kind
Computer Algebra and Other Electronic Systems





Symmetries and the Pólya–Redfield Method
Introduction
Basics of Groups
Permutations and Colorings
An Important Counting Theorem
Pólya and Redfield’s Theorem


Introduction to Graph Theory
Degrees
Paths and Cycles in Graphs
Maps and Graph Coloring





Further Graph Theory
Euler Walks and Circuits
Application of Euler Circuits to Mazes
Hamilton Cycles
Trees
Spanning Trees





Coding Theory
Errors; Noise
The Venn Diagram Code
Binary Codes; Weight; Distance
Linear Codes
Hamming Codes
Codes and the Hat Problem
Variable-Length Codes and Data Compression





Latin Squares
Introduction
Orthogonality
Idempotent Latin Squares
Partial Latin Squares and Subsquares
Applications





Balanced Incomplete Block Designs
Design Parameters
Fisher’s Inequality
Symmetric Balanced Incomplete Block Designs
New Designs from Old
Difference Method





Linear Algebra Methods in Combinatorics
Recurrences Revisited
State Graphs and the Transfer Matrix Method
Kasteleyn’s Permanent Method





Appendix 1: Sets; Proof Techniques
Appendix 2: Matrices and Vectors
Appendix 3: Some Combinatorial People





Solutions to Set A Exercises
Hints for Problems
Solutions to Problems
References
Index


Exercises and Problems appear at the end of each chapter.