Principles and Techniques in Combinatorics

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 repititions -- 1.7. Distribution problems -- Exercise 1 -- 2. Binomial coefficients and multinomial coefficients. 2.1. Introduction -- 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. Subjective mappings and Stirling numbers of the second kind -- 4.6. Derangements and a generalization -- 4.7. The Sieve of Eratosthenes and Euler [symbol]-function -- 4.8. The "Probleme des Menages" -- 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