1st Edition

Combinatorics of Compositions and Words

By Silvia Heubach, Toufik Mansour Copyright 2010
    504 Pages 50 B/W Illustrations
    by Chapman & Hall

    504 Pages 50 B/W Illustrations
    by Chapman & Hall

    A One-Stop Source of Known Results, a Bibliography of Papers on the Subject, and Novel Research Directions

    Focusing on a very active area of research in the last decade, Combinatorics of Compositions and Words provides an introduction to the methods used in the combinatorics of pattern avoidance and pattern enumeration in compositions and words. It also presents various tools and approaches that are applicable to other areas of enumerative combinatorics.

    After a historical perspective on research in the area, the text introduces techniques to solve recurrence relations, including iteration and generating functions. It then focuses on enumeration of basic statistics for compositions. The text goes on to present results on pattern avoidance for subword, subsequence, and generalized patterns in compositions and then applies these results to words. The authors also cover automata, the ECO method, generating trees, and asymptotic results via random compositions and complex analysis.

    Highlighting both established and new results, this book explores numerous tools for enumerating patterns in compositions and words. It includes a comprehensive bibliography and incorporates the use of the computer algebra systems Maple™ and Mathematica®, as well as C++ to perform computations.

    Introduction

    Historical Overview—Compositions

    Historical Overview—Words

    A More Detailed Look

    Basic Tools of the Trade

    Sequences

    Solving Recurrence Relations

    Generating Functions

    Compositions

    Definitions and Basic Results (One Variable)

    Restricted Compositions

    Compositions with Restricted Parts

    Connection between Compositions and Tilings

    Colored Compositions and Other Variations

    Research Directions and Open Problems

    Statistics on Compositions

    History and Connections

    Subword Patterns of Length 2: Rises, Levels, and Drops

    Longer Subword Patterns

    Research Directions and Open Problems

    Avoidance of Non-Subword Patterns in Compositions

    History and Connections

    Avoidance of Subsequence Patterns

    Generalized Patterns and Compositions

    Partially Ordered Patterns in Compositions

    Research Directions and Open Problems

    Words

    History and Connections

    Definitions and Basic Results

    Subword Patterns

    Subsequence Patterns—Classification

    Subsequence Patterns—Generating Functions

    Generalized Patterns of Type (2,1)

    Avoidance of Partially Ordered Patterns

    Research Directions and Open Problems

    Automata and Generating Trees

    History and Connections

    Tools from Graph Theory

    Automata

    Generating Trees

    The ECO Method

    Research Directions and Open Problems

    Asymptotics for Compositions

    History

    Tools from Probability Theory

    Tools from Complex Analysis

    Asymptotics for Compositions

    Asymptotics for Carlitz Compositions

    A Word on the Asymptotics for Words

    Research Directions and Open Problems

    Appendix A: Useful Identities and Generating Functions

    Appendix B: Linear Algebra and Algebra Review

    Appendix C: Chebychev Polynomials of the Second Kind

    Appendix D: Probability Theory

    Appendix E: Complex Analysis Review

    Appendix F: Using Mathematica and Maple

    Appendix G: C++ and Maple Programs

    Appendix H: Notation

    References

    Exercises appear at the end of each chapter.

    Biography

    Silvia Heubach is a Professor and the Chair of the Department of Mathematics at the California State University, Los Angeles, where she received the Outstanding Professor Award in 1999/2000.

    Toufik Mansour is an Associate Professor at the University of Haifa. The author or co-author of more than 60 papers, Professor Mansour’s general research interest is in discrete mathematics and its applications, with an emphasis on pattern avoidance problems.

    … contains a lot of hidden gems, which need to be explored. It is an advantage that the authors provide fragments of Maple and Mathematica code which would help such explorations. … The book is written in an accessible style … it is quite easy to use for the non-specialist in the area, given a basic computer science and/or mathematical background. It will be a useful reference for the researcher, as well as a very good textbook for a graduate-level course in the area. I recommend the book heartily to both specialists and beginning researchers in the area.
    —IACR Book Reviews, June 2011