Combinatorics of Permutations

Cover
Half Title
Series Page
Title Page
Copyright Page
Dedication
Contents
Foreword
Preface to the First Edition
Preface to the Third Edition
Acknowledgments
No Way around It. Introduction.
1. In One Line and Close. Permutations as Linear Orders.
1.1. Descents
1.1.1. Definition of Descents
1.1.2. Eulerian Numbers
1.1.3. Stirling Numbers and Eulerian Numbers
1.1.4. Generating Functions and Eulerian Numbers
1.1.5. Sequences of Eulerian Numbers
1.2. Alternating Runs
1.3. Alternating Subsequences
1.3.1. Definitions and a Recurrence Relation
1.3.2. Alternating Runs and Alternating Subsequences
1.3.3. Alternating Permutations
Exercises
Problems Plus
Solutions to Problems Plus
2. In One Line and Anywhere. Permutations as Linear Orders. Inversions.
2.1. Inversions
2.1.1. Generating Function of Permutations by Inversions
2.1.2. Major Index
2.1.3. Application: Determinants and Graphs
2.2. Inversions in Permutations of Multisets
2.2.1. Application: Gaussian Polynomials and Subset Sums
2.2.2. Inversions and Gaussian Coefficients
2.2.3. Major Index and Permutations of Multisets
Exercises
Problems Plus
Solutions to Problems Plus
3. In Many Circles. Permutations as Products of Cycles.
3.1. Decomposing a Permutation into Cycles
3.1.1. Application: Sign and Determinants
3.1.2. An Application: Geometric Transformations
3.2. Type and Stirling Numbers
3.2.1. Cycle Type of a Permutation
3.2.2. Application: Conjugate Permutations
3.2.3. Application: Trees and Transpositions
3.2.4. Permutations with a Given Number of Cycles
3.2.5. Generating Functions for Stirling Numbers
3.2.6. Application: Real Zeros and Probability
3.3. Cycle Decomposition versus Linear Order
3.3.1. Transition Lemma
3.3.2. Applications of the Transition Lemma
3.4. Permutations with Restricted Cycle Structure
3.4.1. Exponential Formula
3.4.2. Cycle Index and Its Applications
Exercises
Problems Plus
Solutions to Problems Plus
4. In Any Way but This. Pattern Avoidance. The Basics.
4.1. Notion of Pattern Avoidance
4.1.1. Permutation classes
4.2. Patterns of Length Three
4.3. Monotone Patterns
4.4. Patterns of Length Four
4.4.1. Pattern 1324
4.4.2. Pattern 1342
4.4.3. Pattern 1234
4.5. Proof of the Stanley-Wilf Conjecture
4.5.1. Furedi–Hajnal Conjecture
4.5.2. Avoiding Matrices versus Avoiding Permutations
4.5.3. Proof of the F¨uredi–Hajnal Conjecture
Exercises
Problems Plus
Solutions to Problems Plus
5. In This Way, but Nicely. Pattern Avoidance. Follow-Up.
5.1. Polynomial Recurrences
5.1.1. Polynomially Recursive Functions
5.1.2. Permutation classes again
5.1.3. Algebraic and Rational Power Series
5.1.4. The Generating Function Of Most Principal Classes Is Nonrational
5.1.5. Polynomial Recursiveness of Sn,r(132)
5.2. Containing a Pattern Many Times
5.2.1. Packing Densities
5.2.2. Layered Patterns
5.3. Containing a Pattern a Given Number of Times
5.3.1. Construction with a Given Number of Copies
5.3.2. Sequence {kn}n≥0
Exercises
Problems Plus
Solutions to Problems Plus
6. Mean and Insensitive. Random Permutations.
6.1. Probabilistic Viewpoint
6.1.1. Standard Young Tableaux
6.2. Expectation
6.2.1. Application: Finding the Maximum Element of a Sequence
6.2.2. Linearity of Expectation
6.3. Application: Rank in Decreasing Binary Trees
6.3.1. Two simple initial cases
6.3.2. Higher values of k
6.3.3. A System of Differential Equations
6.4. Variance and Standard Deviation
6.4.1. Application: Asymptotically Normal Distributions
6.5. Application: Longest Increasing Subsequences
Exercises
Problems Plus
Solutions to Problems Plus
7. Permutations and the Rest. Algebraic Combinatorics of Permutations.
7.1. Robinson–Schensted–Knuth Correspondence
7.2. Posets of Permutations
7.2.1. Posets on Sn
7.2.2. Posets on Pattern-Avoiding Permutations
7.2.3. Infinite Poset of Permutations
7.3. Simplicial Complexes of Permutations
7.3.1. Simplicial Complex of Restricted Permutations
7.3.2. Simplicial Complex of All n-Permutations
Exercises
Problems Plus
Solutions to Problems Plus
8. Get Them All. Algorithms and Permutations.
8.1. Generating Permutations
8.1.1. Generating All n-Permutations
8.1.2. Generating Restricted Permutations
8.2. Stack-Sorting Permutations
8.2.1. 2-Stack-Sortable Permutations
8.2.2. t-Stack-Sortable Permutations
8.2.3. Unimodality
8.3. Pop-stack sorting
8.4. Variations of Stack-Sorting
Exercises
Problems Plus
Solutions to Problems Plus
9. How Did We Get Here? Permutations as Genome Rearrangements.
9.1. Introduction
9.2. Block Transpositions
9.3. Block Interchanges
9.3.1. Average Number of Block Interchanges Needed to Sort p
Exercises
Problems Plus
Solutions to Problems Plus
10. Do Not Look Just Yet. Solutions to Odd-Numbered Exercises.
10.1. Solutions for Chapter 1
10.2. Solutions for Chapter 2
10.3. Solutions for Chapter 3
10.4. Solutions for Chapter 4
10.5. Solutions for Chapter 5
10.6. Solutions for Chapter 6
10.7. Solutions for Chapter 7
10.8. Solutions for Chapter 8
10.9. Solutions for Chapter 9
References
List of Frequently Used Notation
Index