Consecutive patterns in restricted permutations and involutions

MaRDI QIDQ5226841zbMATH OpenFDO

Authors Flavio Bonetti, Niccolò Castronuovo, Matteo Silimbani, Marilena Barnabei

Publication date 1 August 2019

Full work available at URL https://arxiv.org/abs/1902.02213, https://dmtcs.episciences.org/5519/pdf

zbMATH Keywords

cluster methodhistoire de LaguerreinvolutionMotzkin pathpermutation pattern

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: It is well-known that the set $mathbf{I}_n$ of involutions of the symmetric group $mathbf{S}_n$ corresponds bijectively - by the Foata map $F$ - to the set of $n$-permutations that avoid the two vincular patterns $underline123,$ $underline132.$ We consider a bijection $Gamma$ from the set $mathbf{S}_n$ to the set of histoires de Laguerre, namely, bicolored Motzkin paths with labelled steps, and study its properties when restricted to $mathbf{S}_n(1underline23,1underline32).$ In particular, we show that the set $mathbf{S}_n(underline123,132)$ of permutations that avoids the consecutive pattern $underline123$ and the classical pattern $132$ corresponds via $Gamma$ to the set of Motzkin paths, while its image under $F$ is the set of restricted involutions $mathbf{I}_n(3412).$ We exploit these results to determine the joint distribution of the statistics des and inv over $mathbf{S}_n(underline123,132)$ and over $mathbf{I}_n(3412).$ Moreover, we determine the distribution in these two sets of every consecutive pattern of length three. To this aim, we use a modified version of the well-known Goulden-Jacson cluster method.

Recommendations

• Restricted involutions and Motzkin paths
• Refined restricted involutions
• The joint distribution of consecutive patterns and descents in permutations avoiding 3-1-2
• Restricted 123-involutions
• Counting consecutive pattern matches in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)

Cited in

(10)

• Consecutive patterns in permutations
• Counting consecutive pattern matches in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)
• Permutations with small maximal \(k\)-consecutive sums
• A spectral approach to consecutive pattern-avoiding permutations
• scientific article; zbMATH DE number 7058688 (Why is no real title available?)
• Restricted involutions and Motzkin paths
• Recurrence relations for patterns of type (2,1) in flattened permutations
• Refined restricted involutions
• The joint distribution of consecutive patterns and descents in permutations avoiding 3-1-2
• Consecutive patterns: from permutations to column-convex polyominoes and back

This page was built for publication: Consecutive patterns in restricted permutations and involutions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5226841)