Chapter 1. What is Combinatorics?
1.1 Example. Perfect covers of chessboards
1.2 Example. Cutting a cube
1.3 Example. Magic squares
1.4 Example. The 4-color problern
1.5 Example. The problem of the 36 officers
1.6 Example. Shortest-route problem
1.7 Example. The game of Nim
1.8 Exercises
Chapter 2. The Pigeonhole Principle
2.1 Pigeonhole principle: Simple form
2.2 Pigeonhole principle: Strong form
2.3 A theorem of Ramsey
2.4 Exercises
Chapter 3. Permutations and Combinations
3.1 Two basic counting principles
3.2 Permutations of sets
3.3 Combinations of sets
3.4 Permutations of multisets
3.5 Combinations of multisets
3.6 Exercises
Chapter 4. Generating Permutations and Combinations
4.1 Generating permutations
4.2 Inversions in permutations
4.3 Generating combinations
4.5 Partial orders and equivalence relations
4.6 Exercises
Chapter 5. The Binomial Coemcients
5.1 Pascal's formula
5.2 The binomial theorem
5.3 Identities
5.4 Unimodality of binomial coemcients
5.5 The multinomial theorem
5.6 Newton's binomial theorem
5.7 More on partially ordered sets
5.8 Exercises
ChHpter 6. The Inclusion-Exclusion Principle and Applicutions
6.1 The inclusion-exclusion principle
6.2 Combinations with repetition
6.3 Derangements
6.4 Permutations with forbidden positions
6.5 Another forbidden position problem
6.6 Exercises
Chapter 7. necurrence Helations and thenerating Functions
7.1 Some number sequences
7.2 Linear homogeneous recurrence relations
7.3 Non-homogeneous recurrence relations
7.4 Generating functions
7.5 Recurrences and generating functions
7.6 A geometry example
7.7 Exponential generating functions
7.8 Exercises
Chnpter 8. Specinl Counting Sequences
8.1 Catalan numbers
8.2 Difference sequences and Stirling numbers
8.3 Partition numbers
8.4 A geometric problem
8.5 Exercises
Chapter 9. Matchings in BipHrtite Oraphs
9.1 General problem formulation
9.2 Matchings
9.3 Systems of distinct representatives
9.4 Stable Inarriages
9.5 Exercises
Chapter 10. Combinatorial nesigns
10.1 Modular arithmetic
10.2 Block designs
10.3 Steiner triple systems
10.4 Latin squares
10.5 Exercises
Chapter 11. Introduction to Orsiph Theory
11.1 Basic properties
11.2 Eulerian trails
11.3 Hamilton chains and cycles
11.4 Bipartite multigraphs
11.5 Trees
11.6 The Shannon switching game
11.7 More on trees
11.8 Exercises
Chapter 12. nigrHphs Hnd Networks
12.1 Digraphs
12.2 Networks
12.3 Exercises
Chupter 13. More on Oruph Theory
13.1 Chromatic number
13.2 Plane and planar graphs
13.3 A 5-color theorem
13.4 Independence number and clique number
13.5 Connectivity
13.6 Exercises
Chapter 14. Polya Counting
14.1 Permutation and symmetry groups
14.2 Burnside's theorem
14.3 Polya's counting formula
14.4 Exercises
Answers sind Hints to Exercises
Bibliography
Index
鄂公网安备 42010302001612号 