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