Combinatorics of permutations

Miklos Bona1584884347, 9781584884347, 9781420035186

There are 650 articles with the word permutation in the title whose primary classification is combinatorics, but, until now, there have been no books addressing the topic. The very first book to be published on the subject, Combinatorics of Permutations contains a comprehensive, up to date treatment of the subject. Covering both enumerative and external combinatorics, this book can be used as either a graduate text or as a reference for professional mathematicians. The book includes many applications from computer science, molecular biology, probabilistic methods, and pattern avoidance, and the numerous exercises show readers a fairly comprehensive list of recent results from the field.

---

Table of contents :
Combinatorics of PERMUTATIONS……Page 3
FOREWORD……Page 5
Preface……Page 6
Acknowledgments……Page 8
Dedication……Page 9
Contents……Page 10
Do Not Look Just Yet. Solutions to Odd-numbered Exercises…….Page 324
References……Page 368
List of Frequently Used Notations……Page 382
No Way Around It. Introduction…….Page 14
1.1.1 The definition of descents……Page 15
1.1.2 Eulerian numbers……Page 16
1.1.3 Stirling numbers and Eulerian numbers……Page 23
1.1.4 Generating functions and Eulerian numbers……Page 26
1.1.5 The sequence of Eulerian numbers……Page 28
1.2 Alternating runs……Page 36
Exercises……Page 43
Problems Plus……Page 48
Solutions to Problems Plus……Page 50
2.1.1 The generating function of permutations by inversions……Page 54
2.1.2 Major index……Page 63
2.1.3.1 The Explicit Definition of Determinants……Page 66
2.1.3.2 Perfect matchings in bipartite graphs……Page 67
2.2 Inversions in Permutations of Multisets……Page 68
2.2.0.3 An Application: Gaussian Polynomials And Subset Sums……Page 70
2.2.1 Inversions and Gaussian Coefficients……Page 71
2.2.2 Major Index and Permutations of Multisets……Page 72
Exercises……Page 75
Problems Plus……Page 78
Solutions to Problems Plus……Page 80
3.1 Decomposing a permutation into cycles……Page 83
3.1.1 An Application: Sign and Determinants……Page 85
3.1.2 An Application: Geometric transformations……Page 88
3.2.1 The type of a permutation……Page 89
3.2.2 An Application: Conjugate permutations……Page 90
3.2.3 An Application: Trees and Transpositions……Page 91
3.2.4 Permutations with a given number of cycles……Page 95
3.2.5 Generating functions for Stirling numbers……Page 102
3.2.6 An Application: Real Zeros and Probability……Page 105
3.3.1 The Transition Lemma……Page 106
3.3.2 Applications of the Transition Lemma……Page 108
3.4.1 The exponential formula……Page 110
3.4.2 The cycle index and its applications……Page 120
3.4.2.1 Proving the formula of Schlömilch……Page 123
Exercises……Page 125
Problems Plus……Page 130
Solutions to Problems Plus……Page 133
4.1 The notion of Pattern avoidance……Page 138
4.2 Patterns of length three……Page 139
4.3 Monotone Patterns……Page 142
4.4 Patterns of length four……Page 144
4.4.1 The Pattern 1324……Page 146
4.4.1.1 An exponential upper bound……Page 149
4.4.2 The Pattern 1342……Page 153
4.4.3 The Pattern 1234……Page 167
4.5.1 The Füredi-Hajnal conjecture……Page 168
4.5.2 Avoiding Matrices vs. Avoiding Permutations……Page 169
4.5.3 The Proof of the Füredi-Hajnal conjecture……Page 170
Exercises……Page 173
Problems Plus……Page 177
Solutions to Problems Plus……Page 179
5.1.1 Polynomially Recursive Functions……Page 183
5.1.2 Closed Classes of Permutations……Page 184
5.1.3 Algebraic and Rational Power Series……Page 186
5.1.4 The P-recursiveness of Sn,r(132)……Page 190
5.1.4.2 The initial step……Page 193
5.1.4.3 The induction step……Page 194
5.2.1 Packing Densities……Page 199
5.2.2 Layered Patterns……Page 201
5.2.2.1 The pattern 132……Page 202
5.3 Containing a pattern a given number of times……Page 206
5.3.1 A Construction With a Given Number of Copies……Page 207
5.3.2 The sequence………Page 209
Exercises……Page 213
Problems Plus……Page 215
Solutions to Problems Plus……Page 216
6.1 The Probabilistic Viewpoint……Page 220
6.1.1 Standard Young Tableaux……Page 221
6.1.1.1 The Hooklength Formula……Page 222
6.1.1.2 The Frobenius formula……Page 228
6.2 Expectation……Page 236
6.2.0.3 An Application: Finding the maximum element of a sequence…….Page 237
6.2.1 Linearity of Expectation……Page 238
6.3 Variance and Standard Deviation……Page 240
6.4 An Application: Longest Increasing Subsequences……Page 244
Exercises……Page 245
Problems Plus……Page 249
Solutions to Problems Plus……Page 250
7.1 The Robinson-Schensted-Knuth correspondence……Page 253
7.2.1.1 The Bruhat Order……Page 263
7.2.1.2 The Weak Bruhat Order……Page 266
7.2.2 Posets on Pattern Avoiding Permutations……Page 271
7.2.3 An Infinite Poset of Permutations……Page 273
7.3.1 A Simplicial Complex of Restricted Permutations……Page 275
7.3.2 A Simplicial Complex of All n-Permutations……Page 277
Exercises……Page 278
Problems Plus……Page 282
Solutions to Problems Plus……Page 284
8.1.1 Generating All n-permutations……Page 288
8.1.2 Generating Restricted Permutations……Page 289
8.2 Stack Sorting Permutations……Page 292
8.2.1 2-Stack Sortable Permutations……Page 294
8.2.2 t-Stack Sortable Permutations……Page 296
8.2.2.1 Symmetry……Page 297
8.2.3 Unimodality……Page 302
8.2.3.1 Log-concavity……Page 304
8.3 Variations Of Stack Sorting……Page 305
Nondeterministic General Deque Sorting……Page 308
Determinstic IR Deque Sorting……Page 310
Exercises……Page 312
Problems Plus……Page 316
Solutions to Problems Plus……Page 318
Solutions for Chapter 2……Page 331
Solutions for Chapter 3……Page 335
Solutions for Chapter 4……Page 344
Solutions for Chapter 5……Page 352
Solutions for Chapter 6……Page 356
Solutions for Chapter 7……Page 360
Solutions for Chapter 8……Page 363