### Available:*

Library | Call Number | Material Type | Home Location | Status |
---|---|---|---|---|

Central Library | QA164 .H36 2000 | Adult Non-Fiction | Non-Fiction Area-Reference | Searching... |

### On Order

### Summary

### Summary

The importance of discrete and combinatorial mathematics continues to increase as the range of applications to computer science, electrical engineering, and the biological sciences grows dramatically. Providing a ready reference for practitioners in the field, the Handbook of Discrete and Combinatorial Mathematics, Second Editionpresents additional material on Google's matrix, random graphs, geometric graphs, computational topology, and other key topics. New chapters highlight essential background information on bioinformatics and computational geometry. Each chapter includes a glossary, definitions, facts, examples, algorithms, major applications, and references.

### Reviews 1

### Choice Review

Rosen is a researcher at AT&T Laboratories, well known for his textbooks in discrete mathematics and number theory (Discrete Mathematics and Its Applications (4th ed., 1998; Elementary Number Theory and Its Applications, 1st ed., CH, Jan'85; 3rd ed., 1992). Together with dozens of contributors, Rosen has assembled essays on a wide range of topics in discrete mathematics, including enumerative combinatorics, number theory, linear and abstract algebra, discrete probability, graph theory, optimization, coding theory, and data structures. The book is organized into 17 chapters, each on a major area of this part of mathematics. Within each chapter there are essays on particular topics within the area, a glossary, a list of references, and a list of Internet resources. Many of the articles contain algorithms and tables of important formulas. A 60-page index makes it easy to locate particular terms. Although many areas covered by this book are discussed in other reference works, no other book covers such a wide range of topics in discrete mathematics. A very useful resource for upper-division undergraduate and graduate students, faculty, researchers, and professionals. B. Borchers; New Mexico Institute of Mining and Technology

### Table of Contents

1. Foundations | p. 1 |

1.1 Propositional and Predicate Logic | p. 12 |

1.2 Set Theory | p. 21 |

1.3 Functions | p. 31 |

1.4 Relations | p. 40 |

1.5 Proof Techniques | p. 50 |

1.6 Axiomatic Program Verification | p. 61 |

1.7 Logic-Based Computer Programming Paradigms | p. 67 |

2. Counting Methods | p. 81 |

2.1 Summary of Counting Problems | p. 84 |

2.2 Basic Counting Techniques | p. 90 |

2.3 Permutations and Combinations | p. 96 |

2.4 Inclusion/Exclusion | p. 107 |

2.5 Partitions | p. 113 |

2.6 Burnside/Polya Counting Formula | p. 120 |

2.7 Mobius Inversion Counting | p. 127 |

2.8 Young Tableaux | p. 129 |

3. Sequences | p. 135 |

3.1 Special Sequences | p. 138 |

3.2 Generating Functions | p. 171 |

3.3 Recurrence Relations | p. 178 |

3.4 Finite Differences | p. 189 |

3.5 Finite Sums and Summation | p. 195 |

3.6 Asymptotics of Sequences | p. 201 |

3.7 Mechanical Summation Procedures | p. 204 |

4. Number Theory | p. 213 |

4.1 Basic Concepts | p. 219 |

4.2 Greatest Common Divisors | p. 226 |

4.3 Congruences | p. 231 |

4.4 Prime Numbers | p. 236 |

4.5 Factorization | p. 255 |

4.6 Arithmetic Functions | p. 259 |

4.7 Primitive Roots and Quadratic Residues | p. 268 |

4.8 Diophantine Equations | p. 281 |

4.9 Diophantine Approximation | p. 289 |

4.10 Quadratic Fields | p. 295 |

5. Algebraic Structures | p. 299 |

5.1 Algebraic Models | p. 305 |

5.2 Groups | p. 307 |

5.3 Permutation Groups | p. 319 |

5.4 Rings | p. 323 |

5.5 Polynomial Rings | p. 329 |

5.6 Fields | p. 331 |

5.7 Lattices | p. 341 |

5.8 Boolean Algebras | p. 344 |

6. Linear Algebra | p. 355 |

6.1 Vector Spaces | p. 361 |

6.2 Linear Transformations | p. 371 |

6.3 Matrix Algebra | p. 377 |

6.4 Linear Systems | p. 392 |

6.5 Eigenanalysis | p. 405 |

6.6 Combinatorial Matrix Theory | p. 417 |

7. Discrete Probability | p. 427 |

7.1 Fundamental Concepts | p. 432 |

7.2 Independence and Dependence | p. 435 |

7.3 Random Variables | p. 441 |

7.4 Discrete Probability Computations | p. 448 |

7.5 Random Walks | p. 452 |

7.6 System Reliability | p. 459 |

7.7 Discrete-Time Markov Chains | p. 468 |

7.8 Queueing Theory | p. 477 |

7.9 Simulation | p. 484 |

8. Graph Theory | p. 495 |

8.1 Introduction to Graphs | p. 509 |

8.2 Graph Models | p. 525 |

8.3 Directed Graphs | p. 526 |

8.4 Distance, Connectivity, Traversability | p. 539 |

8.5 Graph Invariants and Isomorphism Types | p. 549 |

8.6 Graph and Map Coloring | p. 557 |

8.7 Planar Drawings | p. 567 |

8.8 Topological Graph Theory | p. 574 |

8.9 Enumerating Graphs | p. 580 |

8.10 Algebraic Graph Theory | p. 586 |

8.11 Analytic Graph Theory | p. 590 |

8.12 Hypergraphs | p. 595 |

9. Trees | p. 603 |

9.1 Characterizations and Types of Trees | p. 607 |

9.2 Spanning Trees | p. 616 |

9.3 Enumerating Trees | p. 622 |

10. Networks and Flows | p. 629 |

10.1 Minimum Spanning Trees | p. 633 |

10.2 Matchings | p. 641 |

10.3 Shortest Paths | p. 652 |

10.4 Maximum Flows | p. 663 |

10.5 Minimum Cost Flows | p. 673 |

10.6 Communication Networks | p. 683 |

10.7 Difficult Routing and Assignment Problems | p. 692 |

10.8 Network Representations and Data Structures | p. 706 |

11. Partially Ordered Sets | p. 717 |

11.1 Basic Poset Concepts | p. 724 |

11.2 Poset Properties | p. 738 |

12. Combinatorial Designs | p. 753 |

12.1 Block Designs | p. 759 |

12.2 Symmetric Designs and Finite Geometries | p. 770 |

12.3 Latin Squares and Orthogonal Arrays | p. 778 |

12.4 Matroids | p. 786 |

13. Discrete and Computational Geometry | p. 797 |

13.1 Arrangements of Geometric Objects | p. 805 |

13.2 Space Filling | p. 824 |

13.3 Combinatorial Geometry | p. 830 |

13.4 Polyhedra | p. 839 |

13.5 Algorithms and Complexity in Computational Geometry | p. 844 |

13.6 Geometric Data Structures and Searching | p. 853 |

13.7 Computational Techniques | p. 861 |

13.8 Applications of Geometry | p. 867 |

14. Coding Theory and Cryptology | p. 889 |

14.1 Communication Systems and Information Theory | p. 896 |

14.2 Basics of Coding Theory | p. 900 |

14.3 Linear Codes | p. 903 |

14.4 Bounds for Codes | p. 915 |

14.5 Nonlinear Codes | p. 917 |

14.6 Convolutional Codes | p. 918 |

14.7 Basics of Cryptography | p. 923 |

14.8 Symmetric-Key Systems | p. 927 |

14.9 Public-Key Systems | p. 935 |

15. Discrete Optimization | p. 955 |

15.1 Linear Programming | p. 959 |

15.2 Location Theory | p. 986 |

15.3 Packing and Covering | p. 996 |

15.4 Activity Nets | p. 1006 |

15.5 Game Theory | p. 1016 |

15.6 Sperner's Lemma and Fixed Points | p. 1027 |

16. Theoretical Computer Science | p. 1039 |

16.1 Computational Models | p. 1048 |

16.2 Computability | p. 1062 |

16.3 Languages and Grammars | p. 1066 |

16.4 Algorithmic Complexity | p. 1077 |

16.5 Complexity Classes | p. 1085 |

16.6 Randomized Algorithms | p. 1091 |

17. Information Structures | p. 1101 |

17.1 Abstract Datatypes | p. 1108 |

17.2 Concrete Data Structures | p. 1117 |

17.3 Sorting and Searching | p. 1125 |

17.4 Hashing | p. 1139 |

17.5 Dynamic Graph Algorithms | p. 1142 |

Biographies | p. 1153 |

Index | p. 1173 |