# Combinatorial Methods with Computer Applications

#### By **Jonathan L. Gross**

#### Series Editor: **Kenneth H. Rosen**

Chapman and Hall/CRC – 2007 – 664 pages

Chapman and Hall/CRC – 2007 – 664 pages

**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.

… The book is very carefully written and might be a good starting point for undergraduate students. …

—*Zentralblatt MATH* 1168

I 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

PREFACE

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.

Name: Combinatorial Methods with Computer Applications (Hardback) – Chapman and Hall/CRC

Description: By Jonathan L. GrossSeries Editor: Kenneth H. Rosen. 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...

Categories: Combinatorics, Discrete Mathematics, Algorithms & Complexity