Principles and techniques in combinatorics

Preface
Notation and Abbreviation
Contents
1. Permutations and Combinations
1.1. Two Basic Counting Principles
1.2. Permutations
1.3. Circular Permutations
1.4. Combinations
1.5. The Injection and Bijection Principles
1.6. Arrangements and Selections with Repetitions
1.7. Distribution Problems
Exercise 1
2. Binomial Coefficients and Multinomial Coefficients
2.2. The Binomial Theorem
2.3. Combinatorial Identities
2.4. The Pascal’s Triangle
2.5. Chu Shih-Chieh’s Identity
2.6. Shortest Routes in a Rectangular Grid
2.7. Some Properties of Binomial Coefficients
2.8. Multinomial Coefficients and the Multinomial Theorem
Exercise 2
3. The Pigeonhole Principle and Ramsey Numbers
3.1. Introduction
3.2. The Pigeonhole Principle
3.3. More Examples
3.4. Ramsey Type Problems and Ramsey Numbers
3.5. Bounds for Ramsey Numbers
Exercise 3
4. The Principle of Inclusion and Exclusion
4.1. Introduction
4.2. The Principle
4.3. A Generalization
4.4. Integer Solutions and Shortest Routes
4.5. Surjective Mappings and Stirling Numbers of the Second Kind
4 .6 . Derangements and A Generalization
4.7. The Sieve of Eratosthenes and Euler φ-function
4.8. The ‘Probléme des Ménages’
Exercise 4
5. Generating Functions
5.1. Ordinary Generating Functions
5.2. Some Modelling Problems
5.3. Partitions of Integers
5.4. Exponential Generating Functions
Exercise 5
6. Recurrence Relations
6.1. Introduction
6.2. Two Examples
6.3. Linear Homogeneous Recurrence Relations
6.4. General Linear Recurrence Relations
6.5. Two Applications
6 .6 . A System of Linear Recurrence Relations
6.7. The Method of Generating Functions
6 .8 . A Nonlinear Recurrence Relation and Catalan Numbers
6.9. Oscillating Permutations and an Exponential Generating Function
Exercise 6
Bibliography
Answers to Exercises
Exercise 1
Exercise 2
Exercise 4
Exercise 5
Exercise 6
Index