Introduction to Enumerative and Analytic Combinatorics

3. Auflage 2025
ISBN: 978-1-032-30270-6
Verlag: Taylor & Francis Ltd

Buch, Englisch, 566 Seiten, Format (B × H): 163 mm x 240 mm, Gewicht: 1004 g

Reihe: Discrete Mathematics and Its Applications

This award-winning textbook targets the gap between introductory texts in discrete mathematics and advanced graduate texts in enumerative combinatorics. The author’s goal is to make combinatorics more accessible to encourage student interest and to expand the number of students studying this rapidly expanding field.

The book first deals with basic counting principles, compositions and partitions, and generating functions. It then focuses on the structure of permutations, graph enumeration, and extremal combinatorics. Lastly, the text discusses supplemental topics, including error-correcting codes, properties of sequences, and magic squares.

Updates to the Third Edition include:

- Quick Check exercises at the end of each section, which are typically easier than the regular exercises at the end of each chapter.

- A new section discussing the Lagrange Inversion Formula and its applications, strengthening the analytic flavor of the book.

- An extended section on multivariate generating functions.

Numerous exercises contain material not discussed in the text allowing instructors to extend the time they spend on a given topic. A chapter on analytic combinatorics and sections on advanced applications of generating functions, demonstrating powerful techniques that do not require the residue theorem or complex integration, and extending coverage of the given topics are highlights of the presentation.

The second edition was recognized as an Outstanding Academic Title of the Year by Choice Magazine, published by the American Library Association.

Zielgruppe

Undergraduate Advanced and Undergraduate Core

Autoren/Hrsg.

Bona, Miklos

Fachgebiete

• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik

Inhaltsverzeichnis

Basic methods
When we add and when we subtract
When we multiply
When we divide
Applications of basic counting principles
The pigeonhole principle
Notes
Chapter review
Exercises
Solutions to exercises
Supplementary exercises

Applications of basic methods
Multisets and compositions
Set partitions
Partitions of integers
The inclusion-exclusion principle
The twelvefold way
Notes
Chapter review
Exercises
Solutions to exercises
Supplementary exercises

Generating functions
Power series
Warming up: Solving recurrence relations
Products of generating functions
Compositions of generating functions
A different type of generating functions
Notes
Chapter review
Exercises
Solutions to exercises
Supplementary exercises

TOPICS

Counting permutations
Eulerian numbers
The cycle structure of permutations
Cycle structure and exponential generating functions
Inversions
Advanced applications of generating functions to permutation enumeration
Notes
Chapter review
Exercises
Solutions to exercises
Supplementary exercises

Counting graphs
Trees and forests
Graphs and functions
When the vertices are not freely labeled
Graphs on colored vertices
Graphs and generating functions
Notes
Chapter review
Exercises
Solutions to exercises
Supplementary exercises

Extremal combinatorics
Extremal graph theory
Hypergraphs
Something is more than nothing: Existence proofs
Notes
Chapter review
Exercises
Solutions to exercises
Supplementary exercises

AN ADVANCED METHOD

Analytic combinatorics
Exponential growth rates
Polynomial precision
More precise asymptotics
Notes
Chapter review
Exercises
Solutions to exercises
Supplementary exercises

SPECIAL TOPICS

Symmetric structures
Designs
Finite projective planes
Error-correcting codes
Counting symmetric structures
Notes
Chapter review
Exercises
Solutions to exercises
Supplementary exercises

Sequences in combinatorics
Unimodality
Log-concavity
The real zeros property
Notes
Chapter review
Exercises
Solutions to exercises
Supplementary exercises

Counting magic squares and magic cubes
A distribution problem
Magic squares of fixed size
Magic squares of fixed line sum
Why magic cubes are different
Notes
Chapter review
Exercises
Solutions to exercises
Supplementary exercises

Appendix: The method of mathematical induction
Weak induction
Strong induction

Über Autor(innen)

Miklós Bóna received his Ph.D in mathematics from the Massachusetts Institute of Technology in 1997. Since 1999, he has taught at the University of Florida, where, in 2010, he was inducted into the Academy of Distinguished Teaching Scholars. Professor Bóna has mentored numerous graduate and undergraduate students. He is the author of four books and more than 65 research articles, mostly focusing on enumerative and analytic combinatorics. His book, Combinatorics of Permutations, won a 2006 Outstanding Title Award from Choice, the journal of the American Library Association. He is also an Editor-in-Chief for the Electronic Journal of Combinatorics, and for two book series at CRC Press.