Combinatorial Methods with Computer Applications: Discrete Mathematics and Its Applications

ISBN-13: 9781584887430 / Angielski / Twarda / 2007 / 664 str.

Jonathan L. Gross

Opis

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.

Spis treści

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.

O autorze

Jonathan L. Gross