Applied Combinatorics

by Roberts, Fred; Tesman, Barry

• ISBN13: 9780130796035
• ISBN10: 0130796034
• Edition: 2nd
• Format: Hardcover
• Copyright: 2005-01-01
• Publisher: Prentice Hall

Summary

For courses in undergraduate Combinatorics for juniors or seniors. This carefully crafted text emphasizes applications and problem solving. It is divided into 4 parts. Part I introduces basic tools of combinatorics, Part II discusses advanced tools, Part III covers the existence problem, and Part IV deals with combinatorial optimization.

Table of Contents

What Is Combinatorics?

Basic Counting Rules

Introduction to Graph Theory

Generating Functions and Their Applications

Recurrence Relations

The Principle of Inclusion and Exclusion

The Polya Theory of Counting

Experimental Design

Coding Theory

Existence Problems in Graph Theory

Matching and Covering

Optimization Problems for Graphs and Networks

Table of Contents provided by Publisher. All Rights Reserved.

Excerpts

The second edition ofApplied Combinatoricscomes 20 years after the first one. It has been substantially rewritten with more than 200 pages of new material and significant changes in numerous sections. There are many new examples and exercises. On the other hand, the main philosophy of the book is unchanged. The following three paragraphs are from the preface of the first edition and these words still ring true today. Perhaps the fastest growing area of modern mathematics is combinatorics. A major reason for this rapid growth is its wealth of applications, to computer science, communications, transportation, genetics, experimental design, scheduling, and so on. This book introduces the reader to the tools of combinatorics from an applied point of view. Much of the growth of combinatorics has gone hand in hand with the development of the computer. Today's high-speed computers make it possible to implement solutions to practical combinatorial problems from a wide variety of fields, solutions that could not be implemented until quite recently. This has resulted in increased emphasis on the development of solutions to combinatorial problems. At the same time, the development of computer science has brought with it numerous challenging combinatorial problems of its own. Thus, it is hard to separate combinatorial mathematics from computing. The reader will see the emphasis on computing here by the frequent use of examples from computer science, the frequent discussion of algorithms, and so on. On the other hand, the general point of view taken in this book is that combinatorics has a wealth of applications to a large number of subjects, and this book has tried to emphasize the variety of these applications rather than just focusing on one. Many of the mathematical topics presented here are relatively standard topics from the rapidly growing textbook literature of combinatorics. Others are taken from the current research literature, or are chosen because they illustrate interesting applications of the subject. The book is distinguished, we believe, by its wide-ranging treatment of applications. Entire sections are devoted to such applications as switching functions, the use of enzymes to uncover unknown RNA chains, searching and sorting problems of information retrieval, construction of error-correcting codes, counting of chemical compounds, calculation of power in voting situations, and uses of Fibonacci numbers. There are entire sections on applications of recurrences involving convolutions, applications of eulerian chains, applications of generating functions, and so on, that are unique to the literature. WHAT'S NEW IN THIS EDITION? Much of the appeal of this book has stemmed from its references to modern literature and real applications. The applications that motivate the development and use of combinatorics are expanding greatly, especially in the natural and social sciences. In particular, computer science and biology are primary sources of many of the new applications appearing in this second edition. Along with these additions, we have also added some major new topics, deleted some specialized ones, made organizational changes, and updated and improved the examples, exercises, and references to the literature. Some of the major changes in the second edition are the following: Chapter 1 (What is Combinatorics?):We have added major new material on list colorings, expanding discussion of scheduling legislative committees. List colorings are returned to in various places in the book. Chapter 2 (Basic Counting Rules):Section 2.16, that previously only discussed algorithmic methods for generating permutations, has been substantially expanded and broken into subsections. Section 2.18, that introduces the notion of "good algorithms" and NP-completeness, has been substantially rewritten and modernized. A new section on the pigeonhole principle has been added. The