Counting subwords in flattened permutations

DOI10.4310/JOC.2013.V4.N3.A4zbMATH Open1275.05008arXiv1307.3637MaRDI QIDQ376559FDOQ376559

Authors: Toufik Mansour, Mark Shattuck, David G. L. Wang 

Publication date: 5 November 2013

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: In this paper, we consider the number of occurrences of descents, ascents, 123-subwords, 321-subwords, peaks and valleys in flattened permutations, which were recently introduced by Callan in his study of finite set partitions. For descents and ascents, we make use of the kernel method and obtain an explicit formula (in terms of Eulerian polynomials) for the distribution on $mathcal{S}_n$ in the flattened sense. For the other four patterns in question, we develop a unified approach to obtain explicit formulas for the comparable distributions. We find that the formulas so obtained for 123- and 321-subwords can be expressed in terms of the Chebyshev polynomials of the second kind, while those for peaks and valleys are more related to the Eulerian polynomials. We also provide a bijection showing the equidistribution of descents in flattened permutations of a given length with big descents in permutations of the same length in the usual sense.

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

Recommendations

• Counting subword patterns in permutations arising as flattened partitions of sets
• Counting subwords in flattened partitions of sets
• Recurrence relations in counting the pattern 13-2 in flattened permutations
• Recurrence relations for patterns of type (2,1) in flattened permutations
• The sets of flattened partitions with forbidden patterns

zbMATH Keywords

permutationpattern avoidancekernel method

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18)

Cited In (9)

• On pattern avoiding flattened set partitions
• Recurrence relations in counting the pattern 13-2 in flattened permutations
• Counting subwords in a partition of a set
• Counting subword patterns in permutations arising as flattened partitions of sets
• Recurrence relations for patterns of type (2,1) in flattened permutations
• Counting subwords and regular languages
• Lipschitz polytopes of posets and permutation statistics
• Counting subwords in flattened partitions of sets
• Counting subwords in flattened involutions and Kummer functions

This page was built for publication: Counting subwords in flattened permutations

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