Combinatorics of Permutations

by Miklos Bona

Overview

The new edition of this award-winning, graduate textbook is upated throughout. Including mostly enumerative combinatorics, yet there are algebraic, analytic, and topological parts as well, and many applications. The author continues to reveal the usefulness of the subject for both students and researchers.

Product Details

ISBN-13:	9781032223506
Publisher:	CRC Press
Publication date:	08/26/2024
Series:	Discrete Mathematics and Its Applications
Edition description:	3rd ed.
Pages:	528
Product dimensions:	6.12(w) x 9.19(h) x (d)

About the Author

Miklós Bóna received his Ph.D in mathematics from the Massachusetts Institute of Technology in 1997. Since 1999, he has taught at the University of Florida, where, in 2010, he was inducted into the Academy of Distinguished Teaching Scholars. Professor Bóna has mentored numerous graduate and undergraduate students. He is the author of four books and more than 65 research articles, mostly focusing on enumerative and analytic combinatorics. His book, Combinatorics of Permutations, won a 2006 Outstanding Title Award from Choice, the journal of the American Library Association. He is also an editor-in-chief for the Electronic Journal of Combinatorics, and for two book series at CRC Press.

Table of Contents

	No Way Around It. Introduction	1
1	In One Line And Close. Permutations as Linear Orders. Runs	3
1.1	Descents	3
1.1.1	The definition of descents	3
1.1.2	Eulerian numbers	4
1.1.3	Stirling numbers and Eulerian numbers	11
1.1.4	Generating functions and Eulerian numbers	14
1.1.5	The sequence of Eulerian numbers	16
1.2	Alternating runs	24
	Exercises	31
	Problems Plus	36
	Solutions to Problems Plus	38
2	In One Line And Anywhere. Permutations as Linear Orders. Inversions	43
2.1	Inversions	43
2.1.1	The generating function of permutations by inversions	43
2.1.2	Major index	52
2.1.3	An Application: Determinants and Graphs	55
2.2	Inversions in Permutations of Multisets	57
2.2.1	Inversions and Gaussian Coefficients	60
2.2.2	Major Index and Permutations of Multisets	61
	Exercises	64
	Problems Plus	67
	Solutions to Problems Plus	69
3	In Many Circles. Permutations as Products of Cycles	73
3.1	Decomposing a permutation into cycles	73
3.1.1	An Application: Sign and Determinants	75
3.1.2	An Application: Geometric transformations	78
3.2	Type and Stirling numbers	79
3.2.1	The type of a permutation	79
3.2.2	An Application: Conjugate permutations	80
3.2.3	An Application: Trees and Transpositions	81
3.2.4	Permutations with a given number of cycles	85
3.2.5	Generating functions for Stirling numbers	92
3.2.6	An Application: Real Zeros and Probability	95
3.3	Cycle Decomposition versus Linear Order	96
3.3.1	The Transition Lemma	96
3.3.2	Applications of the Transition Lemma	98
3.4	Permutations with restricted cycle structure	100
3.4.1	The exponential formula	100
3.4.2	The cycle index and its applications	110
	Exercises	115
	Problems Plus	120
	Solutions to Problems Plus	123
4	In Any Way But This. Pattern Avoidance. The Basics	129
4.1	The notion of Pattern avoidance	129
4.2	Patterns of length three	130
4.3	Monotone Patterns	133
4.4	Patterns of length four	135
4.4.1	The Pattern 1324	137
4.4.2	The Pattern 1342	144
4.4.3	The Pattern 1234	158
4.5	The Proof of The Stanley-Wilf Conjecture	159
4.5.1	The Furedi-Hajnal conjecture	159
4.5.2	Avoiding Matrices vs. Avoiding Permutations	160
4.5.3	The Proof of the Furedi-Hajnal conjecture	161
	Exercises	164
	Problems Plus	168
	Solutions to Problems Plus	170
5	In This Way, But Nicely. Pattern Avoidance. Followup	175
5.1	Polynomial Recursions	175
5.1.1	Polynomially Recursive Functions	175
5.1.2	Closed Classes of Permutations	176
5.1.3	Algebraic and Rational Power Series	178
5.1.4	The P-recursiveness of S[subscript n,r](132)	182
5.2	Containing a pattern many times	191
5.2.1	Packing Densities	191
5.2.2	Layered Patterns	193
5.3	Containing a pattern a given number of times	198
5.3.1	A Construction With a Given Number of Copies	199
5.3.2	The sequence {k[subscript n]}[subscript n greater than or equal 0]	201
	Exercises	205
	Problems Plus	207
	Solutions to Problems Plus	208
6	Mean and Insensitive. Random Permutations	213
6.1	The Probabilistic Viewpoint	213
6.1.1	Standard Young Tableaux	214
6.2	Expectation	229
6.2.1	Linearity of Expectation	231
6.3	Variance and Standard Deviation	233
6.4	An Application: Longest Increasing Subsequences	237
	Exercises	238
	Problems Plus	242
	Solutions to Problems Plus	243
7	Permutations vs. Everything Else. Algebraic Combinatorics of Permutations	247
7.1	The Robinson-Schensted-Knuth correspondence	247
7.2	Posets of permutations	257
7.2.1	Posets on S[subscript n]	257
7.2.2	Posets on Pattern Avoiding Permutations	265
7.2.3	An Infinite Poset of Permutations	267
7.3	Simplicial Complexes of permutations	269
7.3.1	A Simplicial Complex of Restricted Permutations	269
7.3.2	A Simplicial Complex of All n-Permutations	271
	Exercises	272
	Problems Plus	276
	Solutions to Problems Plus	278
8	Get Them All. Algorithms and Permutations	283
8.1	Generating Permutations	283
8.1.1	Generating All n-permutations	283
8.1.2	Generating Restricted Permutations	284
8.2	Stack Sorting Permutations	287
8.2.1	2-Stack Sortable Permutations	289
8.2.2	t-Stack Sortable Permutations	291
8.2.3	Unimodality	297
8.3	Variations Of Stack Sorting	300
	Exercises	307
	Problems Plus	311
	Solutions to Problems Plus	313
	Do Not Look Just Yet. Solutions to Odd-numbered Exercises	319
Solutions for Chapter 1319
Solutions for Chapter 2326
Solutions for Chapter 3330
Solutions for Chapter 4339
Solutions for Chapter 5347
Solutions for Chapter 6351
Solutions for Chapter 7355
Solutions for Chapter 8358
	References	363
	List of Frequently Used Notations	377
	Index	379

Editorial Reviews

The extended new edition of Bóna’s textbook will continue to provide a wealth of information on the combinatorial facet of permutations, to both students and researchers in the subject.
— Martin Kiazar, in Mathematical Review Clippings

There is a new chapter nine, ‘devoted to sorting algorithms whose original motivation comes from molecular biology.’ Chapters 1, 3, 4, and 6 have been ‘significantly changed and expanded’ and all chapters have new exercises and problems, some of which reflect recent results. This is an excellent book on an important subject.
—Fernando Q. Gouvêa, MAA Reviews, December 2012 (This book is in the MAA's basic library list.)

How is the newcomer to this subject able to make sense of and sort out these bewildering possibilities? Until now it was necessary to consult a myriad of sources, from textbooks to journal articles, in order to grasp the whole picture. Now, however, Miklós Bóna has provided us with a comprehensive, engaging, and eminently readable introduction to all aspects of the combinatorics of permutations. The chapter on pattern avoidance is especially timely and gives the first systematic treatment of this fascinating and active area of research.
This book can be utilized at a variety of levels, from random samplings of the treasures therein to a comprehensive attempt to master all the material and solve all the exercises. In whatever direction the reader’s tastes lead, thorough enjoyment and appreciation of a beautiful area of combinatorics are certain to ensue.
—From the Foreword by Richard Stanley, MIT

Praise for the First Edition:
Winner of a 2006 CHOICE Outstanding Academic Title Award
One can easily imagine gems from this book forming the basis of a Martin Gardner-type column … the fascinating chapters here on pattern avoidance, particularly the formulation and proof of the Stanley-Wilf and Furedi-Hajnal conjectures, make this book essential … The author shows himself the master expositor, always efficient while never terse, ever the clairvoyant and generous anticipator of misreadings that might trip readers. Summing Up: Essential.
—CHOICE

Throughout the book, there are frequent references to the excellent bibliography of more than two hundred research articles and books. It is clear that the author finds his topic to be full of ‘serious fun.’ This enthusiasm is conveyed in the conversational and engaging style of the writing … This book was written to be used in a graduate-level topics course. For that purpose it is ideally suited … Experienced researchers in combinatorics will find the book useful as a guide to the literature on permutations. For graduate students with advanced interests in any field of combinatorics, the faculty who work with these students, or the libraries that support them, this book is an excellent choice.
—SIAM Review

This advanced-level textbook grew out of a graduate combinatorics topics class. It serves that role quite well. … Applications are nicely sprinkled throughout the text. … a very extensive list of references with 208 entries … will be attractive to researchers in the area. This excellent text would serve a graduate seminar very well, but could also be used by advanced undergraduates who already have a background in combinatorics.
—Herbert E. Kasube, MAA Reviews

The literature on permutations is as extensive as permutations are manifold … What was missing until now was a comprehensive, up-to-date treatment of all aspects of the combinatorics of permutations … This is the first book which gives a systematic introduction to this fascinating and active area of research … All the subjects are presented in a very pleasant way: developments are always well motivated, explanations are transparent and illustrated by numerous examples. At the end of each chapter the reader finds a list of exercises, with detailed solutions … [containing] references [that] … are excellent starting points for further research.
—Zentralblatt für Mathematik

We found the author’s explanations very clear, and there is an abundance of useful examples and helpful figures . . . There is a rich bibliography for those seeking more information or full proofs of cited results.
—R. Gregory Taylor, SIGACT News, October 2008

[This book] was written by the author with love and enthusiasm for the subject and is a pleasure to read. Undergraduate and graduate students in combinatorics as well as researchers will find in it many interesting results and inspiring questions.
—Mathematical Reviews, 2005

From the Publisher