Combinatorial Methods with Computer Applications provides in-depth coverage of recurrences, generating functions, partitions, and permutations, along with some of the most interesting graph and network topics, design constructions, and finite geometries. Requiring only a foundation in discrete mathematics, it can serve as the textbook in a combinatorial methods course or in a combined graph theory and combinatorics course.
After an introduction to combinatorics, the book explores six systematic approaches within a comprehensive framework: sequences, solving recurrences, evaluating summation expressions, binomial coefficients, partitions and permutations, and integer methods. The author then focuses on graph theory, covering topics such as trees, isomorphism, automorphism, planarity, coloring, and network flows. The final chapters discuss automorphism groups in algebraic counting methods and describe combinatorial designs, including Latin squares, block designs, projective planes, and affine planes. In addition, the appendix supplies background material on relations, functions, algebraic systems, finite fields, and vector spaces.
Paving the way for students to understand and perform combinatorial calculations, this accessible text presents the discrete methods necessary for applications to algorithmic analysis, performance evaluation, and statistics as well as for the solution of combinatorial problems in engineering and the social sciences.
INTRODUCTION TO COMBINATORICS
Objectives of Combinatorics
Ordering and Selection
Some Rules of Counting
Counting Selections
Permutations
Graphs
Number-Theoretic Operations
Combinatorial Designs
SEQUENCES
Sequences as Lists
Recurrences
Pascal's Recurrence
Differences and Partial Sums
Falling Powers
Stirling Numbers: A Preview
Ordinary Generating Functions
Synthesizing Generating Functions
Asymptotic Estimates
SOLVING RECURRENCES
Types of Recurrences
Finding Generating Functions
Partial Fractions
Characteristic Roots
Simultaneous Recursions
Fibonacci Number Identities
Nonconstant Coefficients
Divide-and-Conquer Relations
EVALUATING SUMS
Normalizing Summations
Perturbation
Summing with Generating Functions
Finite Calculus
Iteration and Partitioning of Sums
Inclusion-Exclusion
SUBSETS AND BINOMIALS
Binomial Coefficient Identities
Binomial Inversion Operation
Applications to Statistics
The Catalan Recurrence
PARTITIONS AND PERMUTATIONS
Stirling Subset Numbers
Stirling Cycle Numbers
Inversions and Ascents
Derangements
Exponential Generating Functions
Posets and Lattices
INTEGER OPERATIONS
Euclidean Algorithm
Chinese Remainder Theorem
Polynomial Divisibility
Prime and Composite Moduli
Euler Phi-Function
The Möbius Function
GRAPH FUNDAMENTALS
Regular Graphs
Walks and Distance
Trees and Acyclic Digraphs
Graph Isomorphism
Graph Automorphism
Subgraphs
Spanning Trees
Edge Weights
Graph Operations
GRAPH THEORY TOPICS
Traversability
Planarity
Coloring
Analytic Graph Theory
Digraph Models
Network Flows
Topological Graph Theory
GRAPH ENUMERATION
Burnside-Pólya Counting
Burnside's Lemma
Counting Small Simple Graphs
Partitions of Integers
Calculating a Cycle Index
General Graphs and Digraphs
DESIGNS
Latin Squares
Block Designs
Classical Finite Geometries
Projective Planes
Affine Planes
APPENDIX
Relations and Functions
Algebraic Systems
Finite Fields and Vector Spaces
BIBLIOGRAPHY
General Reading
References
SOLUTIONS AND HINTS
INDICES
A Glossary appears at the end of each chapter.
Biography
Jonathan L. Gross
… The book is very carefully written and might be a good starting point for undergraduate students. …
—Zentralblatt MATH 1168I recently got [this] book on combinatorics and applications to computer science, and I like it so much that I am trying to re-shape some of the discrete maths courses I teach so that I could use it. I liked particularly [the] section on asymptotics, which is much more accessible for my undergrads than Graham, Knuth, and Patashnik.
—Josef Lauri, University of Malta