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:

BLL*

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

MAA Review
Table of Contents

[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

Tags:

Combinatorics