Combinatorics

Preface; Before you go; Notation; Part I. Principles of Combinatorics: 1. Typical counting questions, the product principle; 2. Counting, overcounting, the sum principle; 3. Functions and the bijection principle; 4. Relations and the equivalence principle; 5. Existence and the pigeonhole principle; Part II. Distributions and Combinatorial Proofs: 6. Counting functions; 7. Counting subsets and multisets; 8. Counting set partitions; 9. Counting integer partitions; Part III. Algebraic Tools: 10. Inclusion-exclusion; 11. Mathematical induction; 12. Using generating functions, part I; 13. Using generating functions, part II; 14. techniques for solving recurrence relations; 15. Solving linear recurrence relations; Part IV. Famous Number Families: 16. Binomial and multinomial coefficients; 17. Fibonacci and Lucas numbers; 18. Stirling numbers; 19. Integer partition numbers; Part V. Counting Under Equivalence: 20. Two examples; 21. Permutation groups; 22. Orbits and fixed point sets; 23. Using the CFB theorem; 24. Proving the CFB theorem; 25. The cycle index and Pólya's theorem; Part VI. Combinatorics on Graphs: 26. Basic graph theory; 27. Counting trees; 28. Colouring and the chromatic polynomial; 29. Ramsey theory; Part VII. Designs and Codes: 30. Construction methods for designs; 31. The incidence matrix, symmetric designs; 32. Fisher's inequality, Steiner systems; 33. Perfect binary codes; 34. Codes from designs, designs from codes; Part VIII. Partially Ordered Sets: 35. Poset examples and vocabulary; 36. Isomorphism and Sperner's theorem; 37. Dilworth's theorem; 38. Dimension; 39. Möbius inversion, part I; 40. Möbius inversion, part II; Bibliography; Hints and answers to selected exercises.