Analytic Combinatorics

A Multidimensional Approach

Marni Mishna

• Publisher: Chapman and Hall/CRC
• Year: 2019
• Print ISBN: 9781032475134
• eBook ISBN: 9781351036801
• Edition: 1
• Topic: Mathematics
• Subtopic: Counting & Numeration
• Index: Mathematics

Analytic Combinatorics: A Multidimensional Approach is written in a reader-friendly fashion to better facilitate the understanding of the subject. Naturally, it is a firm introduction to the concept of analytic combinatorics and is a valuable tool to help readers better understand the structure and large-scale behavior of discrete objects. Primarily, the textbook is a gateway to the interactions between complex analysis and combinatorics. The study will lead readers through connections to number theory, algebraic geometry, probability and formal language theory.

The textbook starts by discussing objects that can be enumerated using generating functions, such as tree classes and lattice walks. It also introduces multivariate generating functions including the topics of the kernel method, and diagonal constructions. The second part explains methods of counting these objects, which involves deep mathematics coming from outside combinatorics, such as complex analysis and geometry.

Features

• Written with combinatorics-centric exposition to illustrate advanced analytic techniques
• Each chapter includes problems, exercises, and reviews of the material discussed in them
• Includes a comprehensive glossary, as well as lists of figures and symbols

About the author

Marni Mishna is a professor of mathematics at Simon Fraser University in British Columbia. Her research investigates interactions between discrete structures and many diverse areas such as representation theory, functional equation theory, and algebraic geometry. Her specialty is the development of analytic tools to study the large-scale behavior of discrete objects.

Part I

Enumerative Combinatorics

1

A Primer on Combinatorial Calculus

CONTENTS

1.1Combinatorial Classes

1.2Words and Walks

1.2.1Words and Languages

1.2.2Lattice Walks

1.2.3What Is a Good Combinatorial Formula?

1.2.4Bijections

1.2.5Combinatorial Operations

1.3Formal Power Series

1.3.1Ordinary Generating Functions

1.3.2Coefficient Extraction Techniques

1.4Basic Building Blocks

1.4.1Epsilon Class

1.4.2Atomic Class

1.4.3Admissible Operators and Generating Functions

1.5Combinatorial Specifications

1.6S-regular Classes and Regular Languages

1.6.1Finite Automata

1.7Tree Classes

1.7.1Lagrange Inversion

1.8Algebraic Classes

1.9Discussion

1.10Problems

A principle objective of combinatorial enumeration is to count the number of objects of a certain size in a given family. This might be the number of graphs on a fixed number of nodes or the number of arrangements of a set of objects under some symmetry constraints. To approach this in a systematic manner, we build a formalism that starts with a precise notion of a combinatorial class. The intuition is developed using two common families of objects: random walks and formal languages. The study becomes systematic as we define a combinatorial calculus with combinatorial operators that simulate addition, multiplication and a quasi-inverse. We will use this to determine counting formulas in a systematic way using generating functions. We will consider some high level techniques that process a wide number of classes systematically and algorithmically.

1.1 Co...

Table of contents

• Cover
• Half Title
• Series Page
• Title Page
• Copyright Page
• Dedication
• Contents
• Preface
• Symbols
• Welcome to Analytic Combinatorics
• Part I: Enumerative Combinatorics
• Part II: Methods for Asymptotic Analysis
• Bibliography
• Glossary
• Index