Introduction to combinatorics

Cover
Half Title
Title Page
Copyright Page
Dedication
Table of Contents
List of Figures
Preface
1: Introduction
	1.1 Some Combinatorial Examples
	1.2 Sets, Relations, and Proof Techniques
	1.3 Two Principles of Enumeration
	1.4 Graphs
	1.5 Systems of Distinct Representatives
		Exercises 1A
		Exercises 1B
		Problems
2: Fundamentals of Enumeration
	2.1 Permutations and Combinations
	2.2 Applications of P(n, k) and
	2.3 Permutations and Combinations of Multisets
	2.4 Applications and Subtle Errors
	2.5 Algorithms
		Exercises 2A
		Exercises 2B
		Problems
3: Probability
	3.1 Introduction
	3.2 Some Definitions and Easy Examples
	3.3 Events and Probabilities
	3.4 Three Interesting Examples
	3.5 Probability Models
	3.6 Bernoulli Trials
	3.7 The Probabilities in Poker
	3.8 The Wild Card Poker Paradox
		Exercises 3A
		Exercises 3B
		Problems
4: The Pigeonhole Principle and Ramsey’s Theorem
	4.1 The Pigeonhole Principle
	4.2 Applications of the Pigeonhole Principle
	4.3 Ramsey’s Theorem—The Graphical Case
	4.4 Ramsey Multiplicity
	4.5 Sum-Free Sets
	4.6 Bounds on Ramsey Numbers
	4.7 The General Form of Ramsey’s Theorem
		Exercises 4A
		Exercises 4B
		Problems
5: The Principle of Inclusion and Exclusion
	5.1 Unions of Events
	5.2 The Principle
	5.3 Combinations with Limited Repetitions
	5.4 Derangements
		Exercises 5A
		Exercises 5B
		Problems
6: Generating Functions and Recurrence Relations
	6.1 Generating Functions
	6.2 Recurrence Relations
	6.3 From Generating Function to Recurrence
	6.4 Exponential Generating Functions
		Exercises 6A
		Exercises 6B
		Problems
7: Catalan, Bell, and Stirling Numbers
	7.1 Introduction
	7.2 Catalan Numbers
	7.3 Stirling Numbers of the Second Kind
	7.4 Bell Numbers
	7.5 Stirling Numbers of the First Kind
	7.6 Computer Algebra and Other Electronic Systems
		Exercises 7A
		Exercises 7B
		Problems
8: Symmetries and the Pólya–Redfield Method
	8.1 Introduction
	8.2 Basics of Groups
	8.3 Permutations and Colorings
	8.4 An Important Counting Theorem
	8.5 The P´olya and Redfield Theorem
		Exercises 8A
		Exercises 8B
		Problems
9: Partially Ordered Sets
	9.1 Introduction
	9.2 Examples and Definitions
	9.3 Bounds and Lattices
	9.4 Isomorphism and Cartesian Products
	9.5 Extremal Set Theory: Sperner’s and Dilworth’s Theorems
		Exercises 9A
		Exercises 9B
		Problems
10: Introduction to Graph Theory
	10.1 Degrees
	10.2 Paths and Cycles in Graphs
	10.3 Maps and Graph Coloring
		Exercises 10A
		Exercises 10B
		Problems
11: Further Graph Theory
	11.1 Euler Walks and Circuits
	11.2 Application of Euler Circuits to Mazes
	11.3 Hamilton Cycles
	11.4 Trees
	11.5 Spanning Trees
		Exercises 11A
		Exercises 11B
		Problems
12: Coding Theory
	12.1 Errors and Noise
	12.2 The Venn Diagram Code
	12.3 Binary Codes, Weight, and Distance
	12.4 Linear Codes
	12.5 Hamming Codes
	12.6 Codes and the Hat Problem
	12.7 Variable-Length Codes and Data Compression
		Exercises 12A
		Exercises 12B
		Problems
13: Latin Squares
	13.1 Introduction
	13.2 Orthogonality
	13.3 Idempotent Latin Squares
	13.4 Partial Latin Squares and Subsquares
	13.5 Applications
		Exercises 13A
		Exercises 13B
		Problems
14: Balanced Incomplete Block Designs
	14.1 Design Parameters
	14.2 Fisher’s Inequality
	14.3 Symmetric Balanced Incomplete Block Designs
	14.4 New Designs from Old
	14.5 Difference Methods
		Exercises 14A
		Exercises 14B
		Problems
15: Linear Algebra Methods in Combinatorics
	15.1 Recurrences Revisited
	15.2 State Graphs and the Transfer Matrix Method
	15.3 Kasteleyn’s Permanent Method
		Exercises 15A
		Exercises 15B
		Problems
Appendix A: Sets; Proof Techniques
	AA.1 Sets and Basic Set Operations
	AA.2 The Principle of Mathematical Induction
	AA.3 Some Applications of Induction
	AA.4 Binary Relations on Sets
		Exercises A
		Exercises B
Appendix B: Matrices and Vectors
	B.1 Definitions
	B.2 Vector and Matrix Products
	B.3 Inverses
	B.4 Determinants
		Exercises A
		Exercises B
Appendix C: Some Combinatorial People
Solutions to Set A Exercises
Hints for Problems
Solutions to Problems
References
Index