| |
| |
| |
| What is Combinatorics? | |
| |
| |
| |
| Example: Perfect Covers of Chessboards | |
| |
| |
| |
| Example: Magic Squares | |
| |
| |
| |
| Example: The Four-Color Problem | |
| |
| |
| |
| Example: The Problem of the 36 Officers | |
| |
| |
| |
| Example: Shortest-Route Problem | |
| |
| |
| |
| Example: Mutually Overlapping Circles | |
| |
| |
| |
| Example: The Game of Nim | |
| |
| |
| |
| The Pigeonhole Principle | |
| |
| |
| |
| Pigeonhole Principle: Simple Form | |
| |
| |
| |
| Pigeonhole Principle: Strong Form | |
| |
| |
| |
| A Theorem of Ramsay | |
| |
| |
| |
| Permutations and Combinations | |
| |
| |
| |
| Four Basic Counting Principles | |
| |
| |
| |
| Permutations of Sets | |
| |
| |
| |
| Combinations of Sets | |
| |
| |
| |
| Permutations of Multisets | |
| |
| |
| |
| Combinations of Multisets | |
| |
| |
| |
| Finite Probability | |
| |
| |
| |
| Generating Permutations and Combinations | |
| |
| |
| |
| Generating Permutations | |
| |
| |
| |
| Inversions in Permutations | |
| |
| |
| |
| Generating Combinations | |
| |
| |
| |
| Generating r-Combinations | |
| |
| |
| |
| Partial Orders and Equivalence Relations | |
| |
| |
| |
| The Binomial Coefficients | |
| |
| |
| |
| Pascal's Formula | |
| |
| |
| |
| The Binomial Theorem | |
| |
| |
| |
| Unimodality of Binomial Coefficients | |
| |
| |
| |
| The Multinomial Theorem | |
| |
| |
| |
| Newton's Binomial Theorem | |
| |
| |
| |
| More on Partially Ordered Sets | |
| |
| |
| |
| The Inclusion-Exclusion Principle and Applications | |
| |
| |
| |
| The Inclusion-Exclusion Principle | |
| |
| |
| |
| Combinations with Repetition | |
| |
| |
| |
| Derangements | |
| |
| |
| |
| Permutations with Forbidden Positions | |
| |
| |
| |
| Another Forbidden Position Problem | |
| |
| |
| |
| M�bius Inversion | |
| |
| |
| |
| Recurrence Relations and Generating Functions | |
| |
| |
| |
| Some Number Sequences | |
| |
| |
| |
| Generating Functions | |
| |
| |
| |
| Exponential Generating Functions | |
| |
| |
| |
| Solving Linear Homogeneous Recurrence Relations | |
| |
| |
| |
| Nonhomogeneous Recurrence Relations | |
| |
| |
| |
| A Geometry Example | |
| |
| |
| |
| Special Counting Sequences | |
| |
| |
| |
| Catalan Numbers | |
| |
| |
| |
| Difference Sequences and Stirling Numbers | |
| |
| |
| |
| Partition Numbers | |
| |
| |
| |
| A Geometric Problem | |
| |
| |
| |
| Lattice Paths and Schr�der Numbers | |
| |
| |
| |
| Systems of Distinct Representatives | |
| |
| |
| |
| General Problem Formulation | |
| |
| |
| |
| Existence of SDRs | |
| |
| |
| |
| Stable Marriages | |
| |
| |
| |
| Combinatorial Designs | |
| |
| |
| |
| Modular Arithmetic | |
| |
| |
| |
| Block Designs | |
| |
| |
| |
| Steiner Triple Systems | |
| |
| |
| |
| Latin Squares | |
| |
| |
| |
| Introduction to Graph Theory | |
| |
| |
| |
| Basic Properties | |
| |
| |
| |
| Eulerian Trails | |
| |
| |
| |
| Hamilton Paths and Cycles | |
| |
| |
| |
| Bipartite Multigraphs | |
| |
| |
| |
| Trees | |
| |
| |
| |
| The Shannon Switching Game | |
| |
| |
| |
| More on Trees | |
| |
| |
| |
| More on Graph Theory | |
| |
| |
| |
| Chromatic Number | |
| |
| |
| |
| Plane and Planar Graphs | |
| |
| |
| |
| A 5-color Theorem | |
| |
| |
| |
| Independence Number and Clique Number | |
| |
| |
| |
| Matching Number | |
| |
| |
| |
| Connectivity | |
| |
| |
| |
| Digraphs and Networks | |
| |
| |
| |
| Digraphs | |
| |
| |
| |
| Networks | |
| |
| |
| |
| Matching in Bipartite Graphs Revisited | |
| |
| |
| |
| P�lya Counting | |
| |
| |
| |
| Permutation and Symmetry Groups | |
| |
| |
| |
| Burnside's Theorem | |
| |
| |
| |
| P�lya's Counting formula | |