Combinatorics of Permutations
1st Edition
Published on 25. June 2004
Book
Hardback
383 pages
978-1-58488-434-7 (ISBN)
Description
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.
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.
Reviews / Votes
"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, in 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, 2005f
"The literature on permutations is as extensive as permutations are manifold. ... What was missing until now was a comprehensive up-to-date treatment to all aspects of the combinatorics of permutations. The author [of this book] has written it. ... 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 fuer Mathematik
"One can easily imagine gems from this book forming the basis of a Martin Gardner-type column. ... [T]he 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
"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, Miklos Bona has provided us with a comprehensive, engaging, and eminently readable introduction to all aspects of the combinatorics of permutations...
"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."
- From the Foreword by Richard Stanley
"This book aims to round up any topic related to the combinatorial nature of permutations and present it between one set of covers...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
More details
Series
Language
English
Place of publication
United States
Publishing group
Taylor & Francis Inc
Target group
Professional and scholarly
Students of mathematics, professional mathematicians, computer scientists, statisticians, molecular biologists, electrical engineers
Illustrations
80 s/w Abbildungen
80 Illustrations, black and white
Dimensions
Height: 235 mm
Width: 156 mm
Weight
680 gr
ISBN-13
978-1-58488-434-7 (9781584884347)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
New editions
Miklos Bona
Combinatorics of Permutations
Book
06/2012
2nd Edition
Taylor & Francis
€210.46
Article exhausted; check for reprint
Person
Content
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
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