A Course in Enumeration Book

Introduction 1

Part I Basics

1 Fundamental Coefficients 5

1.1 Elementary Counting Principles 5

Exercises 9

1.2 Subsets and Binomial Coefficients 10

Exercises 18

1.3 Set-partitions and Stirling Numbers S_n,k 20

Exercises 23

1.4 Permutations and Stirling Numbers S_n,k 24

Exercises 29

1.5 Number-Partitions 31

Exercises 35

1.6 Lattice Paths and Gaussian Coefficients 36

Exercises 42

Highlight: Aztec Diamonds 44

Notes and References 51

2 Formal Series and Infinite Matrices 53

2.1 Algebra of Formal Series 53

Exercises 59

2.2 Types of Formal Series 60

Exercises 65

2.3 Infinite Sums and Products 66

Exercises 70

2.4 Infinite Matrices and Inversion of Sequences 71

Exercises 76

2.5 Probability Generating Functions 77

Exercises 84

Highlight: The Point of (No) Return 85

Notes and References 90

Part II Methods

3 Generating Functions 93

3.1 Solving Recurrences 93

Exercises 102

3.2 Evaluating Sums 105

Exercises 110

3.3 The Exponential Formula 112

Exercises 122

3.4 Number-Partitions and Infinite Products 124

Exercises 132

Highlight: Ramanujan's Most Beautiful Formula 136

Notes and References 141

4 Hypergeometric Summation 143

4.1 Summation by Elimination 143

Exercises 148

4.2 Indefinite Sums and Closed Forms 148

Exercises 155

4.3 Recurrences for Hypergeometric Sums 155

Exercises 161

4.4 Hypergeometric Series 162

Exercises 168

Highlight: New Identities from Old 171

Notes and References 178

5 Sieve Methods 179

5.1 Inclusion-Exclusion 179

Exercises 189

5.2 Möbius Inversion 191

Exercises 200

5.3 The Involution Principle 202

Exercises 215

5.4 TheLemma of Gessel-Viennot 217

Exercises 229

Highlight: Tutte's Matrix-Tree Theorem 231

Notes and References 237

6 Enumeration of Patterns 239

6.1 Symmetries and Patterns 239

Exercises 248

6.2 The Theorem of Pólya-Redfield 249

Exercises 260

6.3 Cycle Index 262

Exercises 269

6.4 Symmetries on N and R 270

Exercises 276

Highlight: Patterns of Polyominoes 278

Notes and References 285

Part III Topics

7 The Catalan Connection 289

7.1 Catalan Matrices and Orthogonal Polynomials 290

Exercises 297

7.2 Catalan Numbers and Lattice Paths 300

Exercises 305

7.3 Generating Functions and Operator Calculus 306

Exercises 320

7.4 Combinatorial Interpretation of Catalan Numbers 323

Exercises 333

Highlight: Chord Diagrams 337

Notes and References 344

8 Symmetric Functions 345

8.1 Symmetric Polynomials and Functions 345

Exercises 349

8.2 Homogeneous Symmetric Functions 350

Exercises 355

8.3 Schur Functions 356

Exercises 366

8.4 The RSK Algorithm 367

Exercises 378

8.5 Standard Tableaux 380

Exercises 383

Highlight: Hook-Length Formulas 385

Notes and References 391

9 Counting Polynomials 393

9.1 The Tutte Polynomial of Graphs 393

Exercises 405

9.2 Eulerian Cycles and the Interlace Polynomial 407

Exercises 419

9.3 Plane Graphs and Transition Polynomials 420

Exercises 432

9.4 Knot Polynomials 434

Exercises 443

Highlight: The Best Theorem 445

Notes and References 449

10 Models from Statistical Physics 451

10.1 The Dimer Problem and Perfect Matchings 451

Exercises 465

10.2 The Ising Problem and Eulerian Subgraphs 467

Exercises 480

10.3 Hard Models 481

Exercises 489

10.4 Square Ice 490

Exercises 504

Highlight: The Rogers-Ramanujan Identities 506

Notes and References 517

Solutions to Selected Exercises 519

Chapter 1 519

Chapter 2 521

Chapter 3 524

Chapter 4 528

Chapter 5 529

Chapter 6 533

Chapter 7 536

Chapter 8 540

Chapter 9 544

Chapter 10 547

Notation 553

Index 557