Combinatorial Methods with Computer Applications

by Gross; Jonathan L.

• ISBN13: 9781584887430
• ISBN10: 1584887435
• Edition: 1st
• Format: Hardcover
• Copyright: 2007-11-16
• Publisher: Chapman & Hall/

Summary

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.

Table of Contents

Preface	p. xiii
Author	p. xviii
Introduction to Combinatorics	p. 1
Objectives of Combinatorics	p. 2
Ordering and Selection	p. 6
Some Rules for Counting	p. 9
Counting Selections	p. 18
Permutations	p. 26
Graphs	p. 35
Number-Theoretic Operations	p. 43
Combinatorial Designs	p. 44
Glossary	p. 46
Sequences	p. 49
Sequences as Lists	p. 50
Recurrences	p. 56
Pascal's Recurrence	p. 63
Differences and Partial Sums	p. 67
Falling Powers	p. 74
Stirling Numbers: A Preview	p. 79
Ordinary Generating Functions	p. 85
Synthesizing Generating Functions	p. 97
Asymptotic Estimates	p. 102
Glossary	p. 106
Solving Recurrences	p. 111
Types of Recurrences	p. 112
Finding Generating Functions	p. 116
Partial Fractions	p. 121
Characteristic Roots	p. 123
Simultaneous Recursions	p. 131
Fibonacci Number Identities	p. 138
Non-Constant Coefficients	p. 142
Divide-and-Conquer Relations	p. 148
Glossary	p. 159
Evaluating Sums	p. 161
Normalizing Summations	p. 162
Perturbation	p. 169
Summing with Generating Functions	p. 175
Finite Calculus	p. 180
Iteration and Partitioning of Sums	p. 191
Inclusion-Exclusion	p. 199
Glossary	p. 215
Binomial Coefficients	p. 217
Binomial Coefficient Identities	p. 218
Binomial Inversion Operation	p. 232
Applications to Statistics	p. 239
The Catalan Recurrence	p. 247
Glossary	p. 256
Partitions and Permutations	p. 259
Stirling Subset Numbers	p. 260
Stirling Cycle Numbers	p. 275
Inversions and Ascents	p. 288
Derangements	p. 293
Exponential Generating Functions	p. 296
Posets and Lattices	p. 305
Glossary	p. 321
Integer Operators	p. 325
Euclidean Algorithm	p. 326
Chinese Remainder Theorem	p. 335
Polynomial Divisibility	p. 342
Prime and Composite Moduli	p. 346
Euler Phi-Function	p. 356
The Mobius Function	p. 362
Glossary	p. 369
Graph Fundamentals	p. 371
Regular Graphs	p. 372
Walks and Distance	p. 379
Trees and Acyclic Digraphs	p. 384
Graph Isomorphism	p. 392
Graph Automorphism	p. 399
Subgraphs	p. 404
Spanning Trees	p. 408
Edge Weights	p. 413
Graph Operations	p. 418
Glossary	p. 426
Graph Theory Topics	p. 431
Traversability	p. 432
Planarity	p. 440
Coloring	p. 448
Analytic Graph Theory	p. 456
Digraph Models	p. 463
Network Flows	p. 469
Topological Graph Theory	p. 476
Glossary	p. 485
Graph Enumeration	p. 489
Burnside-Polya Counting	p. 490
Burnside's Lemma	p. 503
Counting Small Simple Graphs	p. 514
Partitions of Integers	p. 522
Calculating a Cycle Index	p. 527
General Graphs and Digraphs	p. 534
Glossary	p. 538
Combinatorial Designs	p. 541
Latin Squares	p. 542
Block Designs	p. 551
Classical Finite Geometries	p. 560
Projective Planes	p. 565
Affine Planes	p. 571
Glossary	p. 577
Appendix	p. 581
Relations and Functions	p. 581
Algebraic Systems	p. 584
Finite Fields and Vector Spaces	p. 590
Bibliography	p. 595
General Reading	p. 595
References	p. 599
Solutions and Hints	p. 603
Indexes	p. 629
Index of Notations	p. 629
General Index	p. 635
Table of Contents provided by Ingram. All Rights Reserved.