DISCRETE MATHEMATICS AND ITS APPLICATIONS
Series Editor KENNETH H. ROSEN
COMBINATORIAL METHODS
WITH COMPUTER APPLICATIONS
JONATHAN L. GROSS
Columbia University
New York, U.S.A
^ l l C h a p m a n & Hall/CRC
M • Taylor & Francis Group
Boca Raton London N e w York
Chapman & Hall/CRC is an imprint of the
Taylor & Francis Group, an informa business
CONTENTS
Preface xiii
Author xvii
0. INTRODUCTION to COMBINATORICS 1
0.1 Objectives of Combinatorics 2
0.2 Ordering and Selection 6
0.3 Some Rules for Counting 9
0.4 Counting Selections 18
0.5 Permutations 26
0.6 Graphs 35
0.7 Number-Theoretic Operations 43
0.8 Combinatorial Designs 44
Glossary 46
1. SEQUENCES 49
1.1 Sequences as Lists 50
1.2 Recurrences 56
1.3 Pascal's Recurrence 63
1.4 Differences and Partial Sums 67
1.5 Falling Powers 74
1.6 Stirling Numbers: A Preview 79
1.7 Ordinary Generating Functions 85
1.8 Synthesizing Generating Functions 97
1.9 Asymptotic Estimates 102
Glossary 106
2. SOLVING RECURRENCES 111
2.1 Types of Recurrences 112
2.2 Finding Generating Functions 116
2.3 Partial Fractions 121
2.4 Characteristic Roots 123
2.5 Simultaneous Recursions 131
2.6 Fibonacci Number Identities 138
2.7 Non-Constant Coefficients 142
2.8 Divide-and-Conquer Relations 148
Glossary 159
3. EVALUATING SUMS 161
3.1 Normalizing Summations 162
3.2 Perturbation 169
3.3 Summing with Generating Functions 175
3.4 Finite Calculus 180
3.5 Iteration and Partitioning of Sums 191
3.6 Inclusion-Exclusion 199
Glossary 215
IX
Contents
BINOMIAL COEFFICIENTS 217
4.1 Binomial Coefficient Identities 218
4.2 Binomial Inversion Operation 232
4.3 Applications to Statistics 239
4.4 The Catalan Recurrence 247
Glossary 256
PARTITIONS and PERMUTATIONS 259
5.1 Stirling Subset Numbers 260
5.2 Stirling Cycle Numbers 275
5.3 Inversions and Ascents 288
5.4 Derangements 293
5.5 Exponential Generating Functions 296
5.6 Posets and Lattices 305
Glossary 321
INTEGER OPERATORS 325
6.1 Euclidean Algorithm 326
6.2 Chinese Remainder Theorem 335
6.3 Polynomial Divisibility 342
6.4 Prime and Composite Moduli 346
6.5 Euler Phi-Function 356
6.6 The Möbius Function 362
Glossary 369
GRAPH FUNDAMENTALS 371
7.1 Regulär Graphs 372
7.2 Walks and Distance 379
7.3 Trees and Acyclic Digraphs 384
7.4 Graph Isomorphism 392
7.5 Graph Automorphism 399
7.6 Subgraphs 404
7.7 Spanning Trees 408
7.8 Edge Weights 413
7.9 Graph Operations 418
Glossary 426
GRAPH THEORY TOPICS 431
8.1 Traversability 432
8.2 Planarity 440
8.3 Coloring 448
8.4 Analytic Graph Theory 456
8.5 Digraph Models 463
8.6 Network Flows 469
8.7 Topological Graph Theory 476
Glossary 485
Contents xi
9. GRAPH ENUMERATION 489
9.1 Burnside-Polya Counting 490
9.2 Burnside's L e m m a 503
9.3 Counting Small Simple Graphs 514
9.4 Partitions of Integers 522
9.5 Calculating a Cycle Index 527
9.6 General Graphs and Digraphs 534
Glossary 538
10. COMBINATORIAL DESIGNS 541
10.1 Latin Squares 542
10.2 Block Designs 551
10.3 Classical Finite Geometries 560
10.4 Projective Planes 565
10.5 Affine Planes 571
Glossary 577
APPENDIX 581
AI Relations and Functions 581
A2 Algebraic Systems 584
A3 Finite Fields and Vector Spaces 590
BIBLIOGRAPHY 595
Bl General Reading 595
B2 References 599
SOLUTIONS and HINTS 603
INDEXES 629
11 Index of Notations 629
12 General Index 635