You are here

Combinatorics of Permutations

Miklós Bóna
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2012
Number of Pages: 
458
Format: 
Hardcover
Edition: 
2
Series: 
Discrete Mathematics and Its Applications
Price: 
89.95
ISBN: 
9781439850510
Category: 
Monograph
BLL Rating: 

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Fernando Q. Gouvêa
, on
12/22/2012
]

See our review of the first edition. The combinatorics of permutations remains an active topic of research, and the last eight years have brought many new results. As a result, says the author, the new edition required "some painful choices as to what to include." 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.

In One Line and Close. Permutations as Linear Orders.
Descents
Alternating Runs
Alternating Subsequences

 

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. Follow-Up.
Polynomial Recurrences
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 versus 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

 

How Did We Get Here? Permutations as Genome Rearrangements.
Introduction
Block Transpositions
Block Interchanges
Block Transpositions Revisited

 

Solutions to Odd-Numbered Exercises

References

List of Frequently Used Notation

Index