2nd Edition

Introduction to Enumerative and Analytic Combinatorics

By Miklos Bona Copyright 2016
    556 Pages 147 B/W Illustrations
    by Chapman & Hall

    Introduction to Enumerative and Analytic Combinatorics fills the gap between introductory texts in discrete mathematics and advanced graduate texts in enumerative combinatorics. 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.

    Strengthening the analytic flavor of the book, this Second Edition:

    • Features a new chapter on analytic combinatorics and new sections on advanced applications of generating functions
    • Demonstrates powerful techniques that do not require the residue theorem or complex integration
    • Adds new exercises to all chapters, significantly extending coverage of the given topics

    Introduction to Enumerative and Analytic Combinatorics, Second Edition makes combinatorics more accessible, increasing interest in this rapidly expanding field.

    Outstanding Academic Title of the Year, Choice magazine, American Library Association.

     

    METHODS

    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

    Biography

    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.

    Bona's work is a superb text for any reader learning the vast topic of combinatorics. It includes a well-written description of the fundamentals of combinatorics and several chapters of applications. Each chapter concludes with a list of important formulas available for future reference and a lengthy list of exercises. These exercises are quite comprehensive in that they include a wide range of topics, many exploring other interesting topics unexplained in the text. Most of these exercises are accompanied by complete, well-explained solutions to assist struggling readers. One of the best aspects of the book is the conversational tone in which it is written. When reading through the numerous proofs in the text, readers will feel as though they are actually in the classroom with Bona (Univ. of Florida). His explanations are clear and concise, and his dry humor is both entertaining and essential to the text's development. People spreading rumors, wearing colorful hats, and embarking on hazardous vacations are much more enjoyable to count than indistinguishable balls in jars. This work is an excellent addition to the combinatorics library.

    --A. Misseldine, Southern Utah University