Applied Combinatorics, 5th Edition

by Alan Tucker (State Univ. of New York at Stony Brook)

• ISBN13: 9780471735076
• ISBN10: 0471735078
• Edition: 5th
• Format: Hardcover
• Copyright: 2006-11-01
• Publisher: WILEY

Summary

Updated with new material, this"Fifth Edition" of the most widely used book in combinatorial problems explains how to reason and model combinatorically. It also stresses the systematic analysis of different possibilities, exploration of the logical structure of a problem, and ingenuity. Combinatorical reasoning underlies all analysis of computer systems. It plays a similar role in discrete operations research problems and in finite probability. This bookseeks to develop proficiency in basic discrete math problem solving in the way that a calculus text develops proficiency in basic analysis problem solving.

Author Biography

Alan Tucker is Deputy Department Chair and Undergraduate Program Director in the Department of Applied Mathematics and Statistics at SUNY Stony Brook.

Table of Contents

Prelude	xi
PART ONE GRAPH THEORY	1	(174)
Elements of Graph Theory	3	(46)
Graph Models	3	(10)
Isomorphism	13	(10)
Edge Counting	23	(6)
Planar Graphs	29	(13)
Summary and References	42	(7)
Supplementary Exercises	43	(6)
Covering Circuits and Graph Coloring	49	(44)
Euler Cycles	49	(7)
Hamilton Circuits	56	(12)
Graph Coloring	68	(9)
Coloring Theorems	77	(8)
Summary and References	85	(8)
Supplement Graph Model for Instant Insanity	86	(5)
Supplement Exercises	91	(2)
Trees and Searching	93	(34)
Properties of Trees	93	(10)
Search Trees and Spanning Trees	103	(10)
The Traveling Salesperson Problem	113	(8)
Tree Analysis of Sorting Algorithms	121	(4)
Summary and References	125	(2)
Network Algorithms	127	(48)
Shortest Paths	127	(4)
Minimal Spanning Trees	131	(4)
Network Flows	135	(18)
Algorithmic Matching	153	(10)
The Transportation Problem	163	(11)
Summary and References	174	(1)
PART TWO ENUMERATION	175	(172)
General Counting Methods for Arrangements and Selections	177	(68)
Two Basic Counting Principles	177	(10)
Simple Arrangements and Selections	187	(15)
Arrangements and Selections with Repetitions	202	(8)
Distributions	210	(13)
Binomial Identities	223	(9)
Summary and References	232	(13)
Supplement Selected Solutions to Problems in Chapter 5	233	(12)
Generating Functions	245	(34)
Generating Function Models	245	(7)
Calculating Coefficients of Generating Functions	252	(10)
Partitions	262	(5)
Exponential Generating Functions	267	(6)
A Summation Method	273	(4)
Summary and References	277	(2)
Recurrence Relations	279	(36)
Recurrence Relation Models	279	(12)
Divide-and-Conquer Relations	291	(5)
Solution of Linear Recurrence Relations	296	(4)
Solution of Inhomogeneous Recurrence Relations	300	(4)
Solutions with Generating Functions	304	(8)
Summary and References	312	(3)
Inclusion--Exclusion	315	(32)
Counting with Venn Diagrams	315	(8)
Inclusion--Exclusion Formula	323	(12)
Restricted Positions and Rook Polynomials	335	(10)
Summary and Reference	345	(2)
PART THREE ADDITIONAL TOPICS	347	(64)
Polya's Enumeration Formula	349	(28)
Equivalence and Symmetry Groups	349	(8)
Burnside's Theorem	357	(5)
The Cycle Index	362	(7)
Polya's Formula	369	(7)
Summary and References	376	(1)
Computer Science Approaches to Enumeration	377	(18)
Generating Permutations and Combinations and Programming Projects	377	(6)
Formal Languages and Grammars	383	(5)
Finite-State Machines	388	(5)
Summary and References	393	(2)
Games with Graphs	395	(16)
Progressively Finite Games	395	(8)
Nim-Type Games	403	(7)
Summary and References	410	(1)
APPENDIX	411	(20)
Set Theory	411	(5)
Mathematical Induction	416	(3)
A Little Probability	419	(4)
The Pigeonhole Principle	423	(3)
Computational Complexity and NP-completeness	426	(5)
Glossary of Counting and Graph Theory Terms	431	(4)
Bibliography	435	(2)
Solutions to Odd-Numbered Problems	437	(34)
Index	471