- ホーム
- > 洋書
- > 英文書
- > Science / Mathematics
Full Description
Appropriate for one- or two-semester, junior- to senior-level combinatorics courses.This trusted best-seller covers the key combinatorial ideas-including the pigeon-hole principle, counting techniques, permutations and combinations, Polya counting, binomial coefficients, inclusion-exclusion principle, generating functions and recurrence relations, combinatortial structures (matchings, designs, graphs), and flows in networks. The Fifth Edition incorporates feedback from users to the exposition throughout and adds a wealth of new exercises.
Contents
1. What is Combinatorics?1.1 Example: Perfect Covers of Chessboards1.2 Example: Magic Squares1.3 Example: The Four-Color Problem1.4 Example: The Problem of the 36 Officers1.5 Example: Shortest-Route Problem1.6 Example: Mutually Overlapping Circles1.7 Example: The Game of Nim2. The Pigeonhole Principle2.1 Pigeonhole Principle: Simple Form2.2 Pigeonhole Principle: Strong Form2.3 A Theorem of Ramsay3. Permutations and Combinations3.1 Four Basic Counting Principles3.2 Permutations of Sets3.3 Combinations of Sets3.4 Permutations of Multisets3.5 Combinations of Multisets3.6 Finite Probability4. Generating Permutations and Combinations4.1 Generating Permutations4.2 Inversions in Permutations4.3 Generating Combinations4.4 Generating r-Combinations4.5 Partial Orders and Equivalence Relations5. The Binomial Coefficients5.1 Pascal's Formula5.2 The Binomial Theorem5.3 Unimodality of Binomial Coefficients5.4 The Multinomial Theorem5.5 Newton's Binomial Theorem5.6 More on Partially Ordered Sets6. The Inclusion-Exclusion Principle and Applications6.1 The Inclusion-Exclusion Principle6.2 Combinations with Repetition6.3 Derangements6.4 Permutations with Forbidden Positions6.5 Another Forbidden Position Problem6.6 Moebius Inversion7. Recurrence Relations and Generating Functions7.1 Some Number Sequences7.2 Generating Functions7.3 Exponential Generating Functions7.4 Solving Linear Homogeneous Recurrence Relations7.5 Nonhomogeneous Recurrence Relations7.6 A Geometry Example8. Special Counting Sequences8.1 Catalan Numbers8.2 Difference Sequences and Stirling Numbers8.3 Partition Numbers8.4 A Geometric Problem8.5 Lattice Paths and Schroeder Numbers9. Systems of Distinct Representatives9.1 General Problem Formulation9.2 Existence of SDRs9.3 Stable Marriages10. Combinatorial Designs10.1 Modular Arithmetic10.2 Block Designs10.3 Steiner Triple Systems10.4 Latin Squares11. Introduction to Graph Theory11.1 Basic Properties11.2 Eulerian Trails11.3 Hamilton Paths and Cycles11.4 Bipartite Multigraphs11.5 Trees11.6 The Shannon Switching Game11.7 More on Trees12. More on Graph Theory12.1 Chromatic Number12.2 Plane and Planar Graphs12.3 A 5-color Theorem12.4 Independence Number and Clique Number12.5 Matching Number12.6 Connectivity13. Digraphs and Networks13.1 Digraphs13.2 Networks13.3 Matching in Bipartite Graphs Revisited14. Polya Counting14.1 Permutation and Symmetry Groups14.2 Burnside's Theorem14.3 Polya's Counting formula
