Roberts / Tesman Applied Combinatorics, Second Edition

2. Auflage 2011
ISBN: 978-1-4200-9983-6
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 848 Seiten

Now with solutions to selected problems, Applied Combinatorics, Second Edition presents the tools of combinatorics from an applied point of view. This bestselling textbook offers numerous references to the literature of combinatorics and its applications that enable readers to delve more deeply into the topics.

After introducing fundamental counting rules and the tools of graph theory and relations, the authors focus on three basic problems of combinatorics: counting, existence, and optimization problems. They discuss advanced tools for dealing with the counting problem, including generating functions, recurrences, inclusion/exclusion, and Pólya theory. The text then covers combinatorial design, coding theory, and special problems in graph theory. It also illustrates the basic ideas of combinatorial optimization through a study of graphs and networks.

Zielgruppe

statisticians and life scientists and others doing extensive investigations.

Autoren/Hrsg.

Roberts, Fred

Tesman, Barry

Fachgebiete

• Mathematik | Informatik EDV | Informatik Betriebssysteme
• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik
• Mathematik | Informatik EDV | Informatik Technische Informatik Computersicherheit

Inhaltsverzeichnis

What Is Combinatorics?
The Three Problems of Combinatorics
The History and Applications of Combinatorics
THE BASIC TOOLS OF COMBINATORICS
Basic Counting Rules
The Product Rule
The Sum Rule
Permutations
Complexity of Computation
r-Permutations
Subsets
r-Combinations
Probability
Sampling with Replacement
Occupancy Problems
Multinomial Coefficients
Complete Digest by Enzymes
Permutations with Classes of Indistinguishable Objects Revisited
The Binomial Expansion
Power in Simple Games
Generating Permutations and Combinations
Inversion Distance between Permutations and the Study of Mutations
Good Algorithms
Pigeonhole Principle and Its Generalizations

Introduction to Graph Theory
Fundamental Concepts
Connectedness
Graph Coloring and Its Applications
Chromatic Polynomials
Trees
Applications of Rooted Trees to Searching, Sorting, and Phylogeny Reconstruction
Representing a Graph in the Computer
Ramsey Numbers Revisited
Relations
Relations
Order Relations and Their Variants
Linear Extensions of Partial Orders
Lattices and Boolean Algebras
THE COUNTING PROBLEM
Generating Functions and Their Applications
Examples of Generating Functions
Operating on Generating Functions
Applications to Counting
The Binomial Theorem
Exponential Generating Functions and Generating Functions for Permutations
Probability Generating Functions
The Coleman and Banzhaf Power Indices
Recurrence Relations
Some Examples
The Method of Characteristic Roots
Solving Recurrences Using Generating Functions
Some Recurrences Involving Convolutions

The Principle of Inclusion and Exclusion
The Principle and Some of Its Applications
The Number of Objects Having Exactly m Properties
The Pólya Theory of Counting
Equivalence Relations
Permutation Groups
Burnside’s Lemma
Distinct Colorings
The Cycle Index
Pólya’s Theorem
THE EXISTENCE PROBLEM
Combinatorial Designs
Block Designs
Latin Squares
Finite Fields and Complete Orthogonal Families of Latin Squares
Balanced Incomplete Block Designs
Finite Projective Planes

Coding Theory
Information Transmission
Encoding and Decoding
Error-Correcting Codes
Linear Codes
The Use of Block Designs to Find Error-Correcting Codes

Existence Problems in Graph Theory
Depth-First Search: A Test for Connectedness
The One-Way Street Problem
Eulerian Chains and Paths
Applications of Eulerian Chains and Paths
Hamiltonian Chains and Paths
Applications of Hamiltonian Chains and Paths

COMBINATORIAL OPTIMIZATION
Matching and Covering
Some Matching Problems
Some Existence Results: Bipartite Matching and Systems of Distinct Representatives
The Existence of Perfect Matchings for Arbitrary Graphs
Maximum Matchings and Minimum Coverings
Finding a Maximum Matching
Matching as Many Elements of X as Possible
Maximum-Weight Matching
Stable Matchings

Optimization Problems for Graphs and Networks
Minimum Spanning Trees
The Shortest Route Problem
Network Flows
Minimum-Cost Flow Problems
Appendix: Answers to Selected Exercises
Author Index
Subject Index
References appear at the end of each chapter.

Über Autor(innen)

Fred S. Roberts is Professor of Mathematics and Director of DIMACS at Rutgers University.
Barry Tesman is Professor of Mathematics at Dickinson College.