DISCRETE MATHEMATICS AND ITS APPLICATIONS Series Editor Kenneth H. AT&T Laboratories Middletown, New Jersey Miklós Bóna, Combinatorics of Permutations Kun-Mao Chao and Bang Ye Wu, Spanning Trees and Optimization Problems Charalambos A.Charalambides, Enumerative Combinatorics Charles J.Colbourn and Jeffrey H.Dinitz, The CRC Handbook of Combinatorial Designs Steven Furino, Ying Miao, and Jianxing Yin, Frames and Resolvable Designs: Uses, Constructions, and Existence Randy Goldberg and Lance Riek, A Practical Handbook of Speech Coders Jacob E.Goodman and Joseph O’Rourke, Handbook of Discrete and Computational Geometry, Second Edition Jonathan Gross and Jay Yellen, Graph Theory and Its Applications Jonathan Gross and Jay Yellen, Handbook of Graph Theory Darrel R.Harris, and Peter D.Johnson, Introduction to Information Theory and Data Compression, Second Edition Daryl D.Harms, Miroslav Kraetzl, Charles J.Colbourn, and John S.Devitt, Network Reliability: Experiments with a Symbolic Algebra Environment David M.Jackson and Terry I.Visentin, An Atlas of Smaller Maps in Orientable and Nonorientable Surfaces Richard E.Klima, Ernest Stitzinger, and Neil P.Sigmon, Abstract Algebra Applications with Maple Patrick Knupp and Kambiz Salari, Verification of Computer Codes in Computational Science and Engineering Donald L.Kreher and Douglas R.Stinson, Combinatorial Algorithms: Generation Enumeration and Search Charles C.Lindner and Christopher A.Rodgers, Design Theory Alfred J.van Oorschot, and Scott A.Vanstone, Handbook of Applied Cryptography Richard A.Mollin, Algebraic Number Theory Richard A.Mollin, Fundamental Number Theory with Applications © 2004 by Chapman & Hall/CRC Richard A.Mollin, An Introduction to Cryptography Richard A.Mollin, Quadratics Richard A.Mollin, RSA and Public-Key Cryptography Kenneth H.Rosen, Handbook of Discrete and Combinatorial Mathematics Douglas R.Wallenius, Applied Mathematical Modeling: A Multidisciplinary Approach Douglas R.Stinson, Cryptography: Theory and Practice, Second Edition Roberto Togneri and Christopher J.deSilva, Fundamentals of Information Theory and Coding Design Lawrence C.Washington, Elliptic Curves: Number Theory and Cryptography © 2004 by Chapman & Hall/CRC www.com DISCRETE MATHEMATICS AND ITS APPLICATIONS Series Editor KENNETH H.ROSEN Combinatorics of PERMUTATIONS Miklós Bóna CHAPMAN & HALL/CRC A CRC Press Company Boca Raton London New York Washington, D. © 2004 by Chapman & Hall/CRC www.com Library of Congress Cataloging-in-Publication Data Bóna, Miklós. Combinatorics of permutations/Miklós, Bóna.—(Discrete mathematics and its applications) Includes bibliographical references and index.64—dc22 2004045868 This book contains information obtained from authentic and highly regarded sources.
Reprinted material is quoted with permission, and sources are indicated. A wide variety of references are listed. Reasonable efforts have been made to publish reliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materials or for the consequences of their use. Neither this book nor any part may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, microfilming, and recording, or by any information storage or retrieval system, without prior permission in writing from the publisher.
The consent of CRC Press LLC does not extend to copying for general distribution, for promotion, for creating new works, or for resale. Specific permission must be obtained in writing from CRC Press LLC for such copying. Direct all inquiries to CRC Press LLC, 2000 N., Boca Raton, Florida 33431. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation, without intent to infringe.
Visit the CRC Press Web site at www.com © 2004 by Chapman & Hall/CRC No claim to original U. Government works International Standard Book Number 1-58488-434-7 Library of Congress Card Number 2004045868 Printed in the United States of America 1 2 3 4 5 6 7 8 9 0 Printed on acid-free paper © 2004 by Chapman & Hall/CRC www.com Foreword FOREWORD Permutations have a remarkably rich combinatorial structure. Part of the reason for this is that a permutation of a finite set can be represented in many equivalent ways, including as a word (sequence), a function, a collection of disjoint cycles, a matrix, etc. Each of these representations suggests a host of natural invariants (or “statistics”), operations, transformations, structures, etc., that can be applied to or placed on permutations.
The fundamental statistics, operations, and structures on permutations include descent set (with numerous specializations), excedance set, cycle type, records, subsequences, composition (product), partial orders, simplicial complexes, probability distributions, etc. 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, a thorough enjoyment and appreciation of a beautiful area of combinatorics is certain to ensue. Richard Stanley Cambridge, Massachusetts January 14, 2004 © 2004 by Chapman & Hall/CRC www.com Preface A few years ago, I was given the opportunity to teach a graduate Combinatorics class on a special topic of my choice. I wanted the class to focus on the Combinatorics of Permutations.
However, I instantly realized that while there were several excellent books that discussed some aspects of the subject, there was no single book that would have contained all, or even most, areas that I wanted to cover. Many areas were not covered in any book, which was easy to understand as the subject is developing at a breathtaking pace, producing new results faster than textbooks are published. Classic results, while certainly explained in various textbooks of very high quality, seemed to be scattered in numerous sources. This was again no surprise; indeed, permutations are omnipresent in modern combinatorics, and there are quite a few ways to look at them.
We can consider permutations as linear orders, we can consider them as elements of the symmetric group, we can model them by matrices, or by graphs. We can enumerate them according to countless interesting statistics, we can decompose them in many ways, and we can bijectively associate them to other structures. One common feature of these activities is that they all involve factual knowledge, new ideas, and serious fun. Another common feature is that they all evolve around permutations, and quite often, the remote-looking areas are connected by surprising results.
Briefly, they do belong to one book, and I am very glad that now you are reading such a book. *** As I have mentioned, there are several excellent books that discuss various aspects of permutations. Therefore, in this book, I cover these aspects less deeply than the areas that had previously not been contained in any book. Chapter 1 is about descents and runs of permutations.
While Eulerian numbers have been given plenty of attention during the last 200 years, most of the research was devoted to analytic concepts. Nothing shows this better than the fact that I was unable to find published proofs of two fundamental results of the area using purely combinatorial methods. Therefore, in this Chapter, I concentrated on purely combinatorial tools dealing with these issues. By and large, the same is true for Chapter 2.
Chapter 3 is devoted to permutations as products of cycles, which is probably the most-studied of all areas covered in this book. Therefore, there were many classic results we had to include there for the sake of © 2004 by Chapman & Hall/CRC www.com completeness, nevertheless we still managed to squeeze in less well-known topics, such as applications of Darroch’s theorem, or transpositions and trees. The area of pattern avoidance is a young one, and has not been given significant space in textbooks before. Therefore, we devoted two full chapters to it.
Chapter 4 walks the reader through the quest for the solution of the Stanley-Wilf conjecture, ending with the recent spectacular proof of Marcus and Tardos for this 23-year- old problem. Chapter 5 discusses aspects of pattern avoidance other than upper bounds or exact formulae. Chapter 6 looks at random permutations and Standard Young Tableaux, starting with two classic and difficult proofs of Greene, Nijenhaus and Wilf. Standard techniques for handling permutation statistics are presented.
A relatively new concept, that of min-wise independent families of permutations, is discussed in the Exercises. Chapter 7, Algebraic Combinatorics of Permutations, is the one in which we had to be most selective. Each of the three sections of that chapter covers an area that is sufficiently rich to be the subject of an entire book. Our goal with that chapter is simply to raise interest in these topics and prepare the reader for the more detailed literature that is available in those areas.
Finally, Chapter 8 is about combinatorial sorting algorithms, many of which are quite recent. This is the first time many of these algorithms (or at least, most aspects of them) are discussed in a textbook, so we treated them in depth. Besides the Exercises, each Chapter ends with a selection of Problems Plus. These are typically more difficult than the exercises, and are meant to raise interest in some questions for further research, and to serve as reference material of what is known.
Some of the Problems Plus are not classified as such because of their level of difficulty, but because they are less tightly connected to the topic at hand. A solution manual for the even-numbered Exercises is available for instructors teaching a class using this book, and can be obtained from the publisher. © 2004 by Chapman & Hall/CRC www.com Acknowledgments This book grew out of various graduate combinatorics courses that I taught at the University of Florida. I am indebted to the authors of the books I used in those courses, for shaping my vision, and for teaching me facts and techniques.
This books are “The Art of Computer Programming” by D.Knuth, “Enumerative Combinatorics” by Richard Stanley, “The Probabilistic Method” by Noga Alon and Joel Spencer, “The Symmetric Group” by Bruce Sagan, and “Enumerative Combinatorics” by Charalambos Charalambides. Needless to say, I am grateful to all the researchers whose results made a textbook devoted exclusively to the combinatorics of permutations possible. I am sure that new discoveries will follow. I am thankful to my former research advisor Richard Stanley for having introduced me into this fascinating field, and to Herb Wilf and Doron Zeilberger, who kept asking intriguing questions attracting scores of young mathematicians like myself to the subject.
Some of the presented material was part of my own research, sometimes in collaboration. I would like to say thanks to my co-authors, Richard Ehrenborg, Andrew MacLennan, Bruce Sagan, Rodica Simion, Daniel Spielman, Vincent Vatter, and Dennis White. I also owe thanks to Michael Atkinson, who introduced me into the history of stack sorting algorithms. I am deeply indebted to Aaron Robertson for an exceptionally thorough and knowledgeable reading of my first draft.
I am also deeply appreciative for manuscript reading by my colleague Andrew Vince, and by Rebecca Smith. A significant part of the book was written during the summer of 2003. In the first half of that summer, I enjoyed the stimulating professional environment at LABRI, at the University of Bordeaux I, in Bordeaux, France. The hospitality of colleagues Olivier Guibert and Sylvain Pelat-Alloin made it easy for me to keep writing during my one-month visit.
In the second half of the summer, I enjoyed the hospitality of my parents, Miklós and Katalin Bóna, at the Lake Balaton in Hungary. My gratitude is extended to Joseph Sciacca, who prepared the second cover page for a book of mine within two years. Last, but not least, I must be thankful to my wife Linda, my first reader and critic, who tolerated surprisingly well that I wrote a book again. I will not forget how much she helped me, and neither will she.
© 2004 by Chapman & Hall/CRC www.com Dedication To Linda, Mikike, Benjamin, and my future children.