Consecutive patterns in restricted permutations and involutions

zbMATH Open1417.05002arXiv1902.02213MaRDI QIDQ5226841FDOQ5226841

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

Publication date: 1 August 2019

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.

Full work available at URL: https://arxiv.org/abs/1902.02213

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)\)

zbMATH Keywords

involutionpermutation patternMotzkin pathcluster methodhistoire de Laguerre

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cited In (10)

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

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)