Combinatorics of Permutations
Chapman & Hall/CRC (Verlag)
978-1-58488-434-7 (ISBN)
- Titel erscheint in neuer Auflage
- Artikel merken
WINNER of a CHOICE Outstanding Academic Title Award for 2006!
As linear orders, as elements of the symmetric group, modeled by matrices, modeled by graphs…permutations are omnipresent in modern combinatorics. They are omnipresent but also multifaceted, and while several excellent books explore particular aspects of the subject, no one book has covered them all. Even the classic results are scattered in various resources.
Combinatorics of Permutations offers the first comprehensive, up to date treatment of both enumerative and extremal combinatorics and looks at permutation as linear orders and as elements of the symmetric group. The author devotes two full chapters to the young but active area of pattern avoidance. He explores the quest for the Stanley-Wilf conjecture and includes the recent and spectacular Marcus-Tardos proof of this problem. He examines random permutations and Standard Young Tableaux and provides an overview of the very rich algebraic combinatorics of permutations. The final chapter takes an in-depth look at combinatorial sorting algorithms.
The author's style is relaxed, entertaining, and clearly reflects his enthusiasm for the "serious fun" the subject holds. Filled with applications from a variety of fields and exercises that draw upon recent research results, this book serves equally well as a graduate-level text and a reference for combinatorics researchers.
IN ONE LINE AND CLOSE. PERMUTATIONS AS LINEAR ORDERS. RUNS
Descents
Alternating Runs
IN ONE LINE AND ANYWHERE. PERMUTATIONS AS LINEAR ORDERS. INVERSIONS
Inversions
Inversion in Permutations of Multisets
IN MANY CIRCLES: PERMUTATIONS AS PRODUCTS OF CYCLES
Decomposing a Permutation into Cycles
Type and Stirling Numbers
Cycle Decomposition versus Linear Order
Permutations with Restricted Cycle Structure
IN ANY WAY BUT THIS: PATTERN AVOIDANCE; THE BASICS
The Notion of Pattern Avoidance
Patterns of Length Three
Monotone Patterns
Patterns of Length Four
The Proof of the Stanley-Wilf Conjecture
IN THIS WAY, BUT NICELY: PATTERN AVOIDANCE; THE FOLLOW-UP
Polynomial Recursions
Containing a Pattern Many Times
Containing a Pattern a Given Number of Times
MEAN AND INSENSITIVE: RANDOM PERMUTATIONS
The Probabilistic Viewpoint
Expectation
Variance and Standard Deviation
An Application: Longest Increasing Subsequences
PERMUTATIONS vs. EVERYTHING ELSE: ALGEBRAIC COMBINATORICS OF PERMUTATIONS
The Robinson-Schensted-Knuth Correspondence
Posets of Permutations
Simplicial Complexes of Permutations
GET THEM ALL: ALGORITHMS AND PERMUTATIONS
Generating Permutations
Stack Sorting Permutations
Variations of Stack Sorting
SOLUTIONS TO ODD-NUMBERED EXERCISES
REFERENCES
LIST OF FREQUENTLY USED NOTATIONS
INDEX
Each chapter also includes Exercises, Problems Plus, and Solutions to Problems Plus sections
| Erscheint lt. Verlag | 25.6.2004 |
|---|---|
| Reihe/Serie | Discrete Mathematics and Its Applications |
| Zusatzinfo | 80 Illustrations, black and white |
| Sprache | englisch |
| Maße | 156 x 235 mm |
| Gewicht | 680 g |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Graphentheorie |
| ISBN-10 | 1-58488-434-7 / 1584884347 |
| ISBN-13 | 978-1-58488-434-7 / 9781584884347 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
