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 (TM) and Mathematica (R), as well as C++ to perform computations.
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.
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.