This trusted best-seller emphasizes combinatorial ideas–including the pigeon-hole principle, counting techniques, permutations and combinations, Pólya counting, binomial coefficients, inclusion-exclusion principle, generating functions and recurrence relations, combinatortial structures (matchings, designs, graphs), and flows in networks. The Fifth Edition clarifies the exposition throughout and adds a wealth of new exercises. Appropriate for one- or two-semester, junior- to senior-level combinatorics courses.
Author(s): Richard A. Brualdi
Edition: 5
Publisher: Prentice Hall
Year: 2009
Language: English
Pages: 617
Contents......Page 9
Preface......Page 5
1 What Is Combinatorics?......Page 13
1.1 Example: Perfect Covers of Chessboards......Page 15
1.2 Example: Magic Squares......Page 19
1.3 Example: The Four-Color Problem......Page 22
1.4 Example: The Problem of the 36 Officers......Page 23
1.5 Example: Shortest-Route Problem......Page 26
1.6 Example: Mutually Overlapping Circles......Page 27
1.7 Example: The Game of Nim......Page 29
1.8 Exercises......Page 32
2.1 Four Basic Counting Principles......Page 39
2.2 Permutations of Sets......Page 47
2.3 Combinations (Subsets) of Sets......Page 53
2.4 Permutations of Multisets......Page 58
2.5 Combinations of Multisets......Page 64
2.6 Finite Probability......Page 68
2.7 Exercises......Page 72
3.1 Pigeonhole Principle: Simple Form......Page 81
3.2 Pigeonhole Principle: Strong Form......Page 85
3.3 A Theorem of Ramsey......Page 89
3.4 Exercises......Page 94
4.1 Generating Permutations......Page 99
4.2 Inversions in Permutations......Page 105
4.3 Generating Combinations......Page 110
4.4 Generating r-Subsets......Page 121
4.5 Partial Orders and Equivalence Relations......Page 125
4.6 Exercises......Page 130
5.1 Pascal's Triangle......Page 139
5.2 The Binomial Theorem......Page 142
5.3 Unimodality of Binomial Coefficients......Page 151
5.4 The Multinomial Theorem......Page 155
5.5 Newton's Binomial Theorem......Page 158
5.6 More on Partially Ordered Sets......Page 161
5.7 Exercises......Page 166
6.1 The Inclusion-Exclusion Principle......Page 173
6.2 Combinations with Repetition......Page 180
6.3 Derangements......Page 184
6.4 Permutations with Forbidden Positions......Page 189
6.5 Another Forbidden Position Problem......Page 193
6.6 Mobius Inversion......Page 195
6.7 Exercises......Page 210
7 Recurrence Relations and Generating Functions......Page 217
7.1 Some Number Sequences......Page 218
7.2 Generating Functions......Page 227
7.3 Exponential Generating Functions......Page 234
7.4 Solving Linear Homogeneous Recurrence Relations......Page 240
7.5 Nonhomogeneous Recurrence Relations......Page 257
7.6 A Geometry Example......Page 265
7.7 Exercises......Page 269
8.1 Catalan Numbers......Page 277
8.2 Difference Sequences and Stirling Numbers......Page 286
8.3 Partition Numbers......Page 303
8.4 A Geometric Problem......Page 310
8.5 Lattice Paths and Schroder Numbers......Page 313
8.6 Exercises......Page 327
9 Systems of Distinct Representatives......Page 333
9.1 General Problem Formulation......Page 334
9.2 Existence of SDRs......Page 338
9.3 Stable Marriages......Page 342
9.4 Exercises......Page 349
10.1 Modular Arithmetic......Page 353
10.2 Block Designs......Page 365
10.3 Steiner Triple Systems......Page 374
10.4 Latin Squares......Page 380
10.5 Exercises......Page 400
11 Introduction to Graph Theory......Page 407
11.1 Basic Properties......Page 408
11.2 Eulerian Trails......Page 418
11.3 Hamilton Paths and Cycles......Page 426
11.4 Bipartite Multigraphs......Page 431
11.5 Trees......Page 438
11.6 The Shannon Switching Game......Page 444
11.7 More on Trees......Page 450
11.8 Exercises......Page 461
12 More on Graph Theory......Page 473
12.1 Chromatic Number......Page 474
12.2 Plane and Planar Graphs......Page 484
12.3 A Five-Color Theorem......Page 488
12.4 Independence Number and Clique Number......Page 492
12.5 Matching Number......Page 500
12.6 Connectivity......Page 505
12.7 Exercises......Page 510
13.1 Digraphs......Page 517
13.2 Networks......Page 528
13.3 Matchings in Bipartite Graphs Revisited......Page 535
13.4 Exercises......Page 545
14 Polya Counting......Page 553
14.1 Permutation and Symmetry Groups......Page 554
14.2 Burnside's Theorem......Page 564
14.3 Polya's Counting Formula......Page 571
14.4 Exercises......Page 588
Answers and Hints to Exercises......Page 594
Bibliography......Page 608
Index......Page 610
