๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Shape Avoiding Permutations

โœ Scribed by Ron M. Adin; Yuval Roichman

Book ID
102586732
Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
121 KB
Volume
97
Category
Article
ISSN
0097-3165

No coin nor oath required. For personal study only.

โœฆ Synopsis

Permutations avoiding all patterns of a given shape (in the sense of Robinson, Schensted, and Knuth) are considered. We show that the shapes of all such permutations are contained in a suitable thick hook and deduce an exponential growth rate for their number.

๐Ÿ“œ SIMILAR VOLUMES

Almost avoiding permutations
Almost avoiding permutations
โœ Robert Brignall; Shalosh B. Ekhad; Rebecca Smith; Vincent Vatter ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 385 KB
Restricted 132-Avoiding Permutations
Restricted 132-Avoiding Permutations
โœ Toufik Mansour; Alek Vainshtein ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 104 KB

We study generating functions for the number of permutations on n letters avoiding 132 and an arbitrary permutation ฯ„ on k letters, or containing ฯ„ exactly once. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.

Permutations of a Multiset Avoiding Perm
Permutations of a Multiset Avoiding Permutations of Length 3
โœ M.H. Albert; R.E.L. Aldred; M.D. Atkinson; C. Handley; D. Holton ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 107 KB

We consider permutations of a multiset which do not contain certain ordered patterns of length 3. For each possible set of patterns we provide a structural description of the permutations avoiding those patterns, and in many cases a complete enumeration of such permutations according to the underlyi