Counting subwords in flattened permutations

DOI10.4310/JOC.2013.V4.N3.A4MaRDI QIDQ376559zbMATH OpenFDO

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

Publication date 5 November 2013

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

Full work available at URL https://arxiv.org/abs/1307.3637, http://intlpress.com/site/pub/pages/journals/items/joc/content/vols/0004/0003/a004/index.html

zbMATH Keywords

permutationpattern avoidancekernel method

Mathematics Subject Classification ID

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

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.

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

Cited in

(9)

• On pattern avoiding flattened set partitions
• Counting subwords in a partition of a set
• Recurrence relations in counting the pattern 13-2 in flattened permutations
• Counting subword patterns in permutations arising as flattened partitions of sets
• Counting subwords and regular languages
• Recurrence relations for patterns of type (2,1) in flattened permutations
• 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)