Combinatorics of Compositions and Words

Combinatorics of Compositions and Words

Free Standard Shipping

Purchasing Options

ISBN 9781420072679
Cat# C7267
Add to cart
eBook (VitalSource)
$104.95 $73.47
ISBN 9781420072686
Cat# CE7267
Add to cart
SAVE 30%
eBook Rentals
Other eBook Options:


  • Presents a historical overview of the field
  • Describes the strengths and weaknesses of a wide variety of solution techniques and approaches
  • Includes tables that list the classification of patterns according to Wilf-equivalence for subsequence patterns and generalized patterns in words and compositions
  • Illustrates new methods and definitions with worked examples and Maple and Mathematica code where applicable
  • Offers C++ programs to compute the number of compositions and words with certain characteristics
  • Contains known and new results, end-of-chapter exercises, and directions for future research
  • Provides an extensive set of references on research in compositions, k-ary words, and pattern avoidance problems

Solutions manual available for qualifying instructors


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.

Table of Contents


Historical Overview—Compositions

Historical Overview—Words

A More Detailed Look

Basic Tools of the Trade


Solving Recurrence Relations

Generating Functions


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


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


Generating Trees

The ECO Method

Research Directions and Open Problems

Asymptotics for Compositions


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


Exercises appear at the end of each chapter.

Author Bio(s)

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.

Editorial Reviews

… 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

Recommended For You

Other CRC Press Sites
Featured Authors
Facebook Page for CRC Press Twitter Page for CRC Press You Tube Channel for CRC Press LinkedIn Page for CRC Press Google Plus Page for CRC Press
Sign Up for Email Alerts
© 2014 Taylor & Francis Group, LLC. All Rights Reserved. Privacy Policy | Cookie Use | Shipping Policy | Contact Us