组合数学 英文版PDF电子书下载

Preface 1

Chapter 1. What is Combinatorics? 1

1.1 Example. Perfect covers of chessboards 4

1.2 Example. Cutting a cube 8

1.3 Example. Magic squares 10

1.4 Example. The 4-color problem 13

1.5 Example. The problem of the 36 officers 14

1.6 Example. Shortest-route problem 16

1.7 Example. The game of Nim 18

1.8 Exercises 21

2.1 Pigeonhole principle: Simple form 27

Chapter 2. The Pigeonhole Principle 27

2.2 Pigeonhole principle: Strong form 32

2.3 A theorem of Ramsey 36

2.4 Exercises 41

Chapter 3. Permutations and Combinations 45

3.1 Two basic counting principles 45

3.2 Permutations of sets 53

3.3 Combinations of Sets 60

3.4 Permutations of multisets 64

3.5 Combinations of multisets 70

3.6 Exercises 75

Chapter 4. Generating Permutations and Combinations 81

4.1 Generating permutations 81

4.2 Inversions in permutations 87

4.3 Generating combinations 93

4.5 Partial orders and equivalence relations 109

4.6 Exercises 116

Chapter 5. The Binomial Coefficients 122

5.1 Pascal s formula 122

5.2 The binomial theorem 127

5.3 Identities 130

5.4 Unimodality of binomial coefficients 137

5.5 The multinomial theorem 143

5.6 Newton s binomial theorem 147

5.7 More on partially ordered sets 149

5.8 Exercises 152

Chapter 6. The Inclusion-Exclusion Principle and Applications 159

6.1 The inclusion-exclusion principle 159

6.2 Combinations with repetition 168

6.3 Derangements 172

6.4 Permutations with forbidden positions 178

6.5 Another forbidden position problem 183

6.6 Exercises 185

Chapter 7. Recurrence Relations and Generating Functions 190

7.1 Some number sequences 191

7.2 Linear homogeneous recurrence relations 202

7.3 Non-homogeneous recurrence relations 213

7.4 Generating functions 220

7.5 Recurrences and generating functions 227

7.6 A geometry example 235

7.7 Exponential generating functions 240

7.8 Exercises 246

Chapter 8. Special Counting Sequences 252

8.1 Catalan numbers 252

8.2 Difference sequences and Stirling numbrs 261

8.3 Partition numbers 281

8.4 A geometric problem 285

8.5 Exercises 290

Chapter 9. Matchings in Bipartite Graphs 294

9.1 General problem formulation 295

9.2 Matchings 302

9.3 Systems of distinct representatives 319

9.4 Stable marriages 324

9.5 Exercises 332

Chapter 10. Combinatorial Designs 337

10.1 Modular arithmetic 337

10.2 Block designs 350

10.3 Steiner triple systems 362

10.4 Latin squares 369

10.5 Exercises 393

Chapter 11. Introduction to Graph Theory 400

11.1 Basic properties 401

11.2 Eulerian trails 412

11.3 Hamilton chains and cycles 422

11.4 Bipartite multigraphs 429

11.5 Trees 436

11.6 The Shannon switching game 443

11.7 More on trees 450

11.8 Exercises 463

Chapter 12. Digraphs and Networks 475

12.1 Digraphs 475

12.2 Networks 488

12.3 Exercises 496

Chapter 13. More on Graph Theory 501

13.1 Chromatic number 502

13.2 Plane and planar graphs 514

13.3 A 5-color theorem 519

13.4 Independence number and clique number 523

13.5 Connectivity 533

13.6 Exercises 540

Chapter 14. Polya Counting 546

14.1 Permutation and Symmetry groups 547

14.2 Burnside s theorem 559

14.3 Polya s counting formula 566

14.4 Exercises 586

Answers and Hints to Exercises 592

Bibliography 607

Index 609