1st Edition

Combinatorial Methods with Computer Applications

By Jonathan L. Gross Copyright 2008
    726 Pages 287 B/W Illustrations
    by Chapman & Hall

    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.

    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.

    Biography

    Jonathan L. Gross

    … 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