Recurrence relations for patterns of type (2,1) in flattened permutations

DOI10.1080/10236198.2013.812083MaRDI QIDQ5746468zbMATH OpenOpenAlexFDO

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

Publication date 18 February 2014

Published in Journal of Difference Equations and Applications (Search for Journal in Brave)

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

zbMATH Keywords

pattern avoidancepermutationrecurrence relationsymmetric function

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Recurrences (11B37)

Abstract: We consider the problem of counting the occurrences of patterns of the form $xy-z$ within flattened permutations of a given length. Using symmetric functions, we find recurrence relations satisfied by the distributions on $mathcal{S}_n$ for the patterns 12-3, 21-3, 23-1 and 32-1, and develop a unified approach to obtain explicit formulas. By these recurrences, we are able to determine simple closed form expressions for the number of permutations that, when flattened, avoid one of these patterns as well as expressions for the average number of occurrences. In particular, we find that the average number of 23-1 patterns and the average number of 32-1 patterns in $extFlatten(pi)$, taken over all permutations $pi$ of the same length, are equal, as are the number of permutations avoiding either of these patterns. We also find that the average number of 21-3 patterns in $extFlatten(pi)$ over all $pi$ is the same as it is for 31-2 patterns.

Recommendations

• Recurrence relations in counting the pattern 13-2 in flattened permutations
• scientific article; zbMATH DE number 2192093
• scientific article; zbMATH DE number 5904291
• Permutations with \(k\)-regular descent patterns
• Pattern avoidance in flattened permutations
• On an extension of a recurrent relation from combinatorics
• Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
• Consecutive patterns in restricted permutations and involutions
• Recurrence relation with two indices and plane compositions

Cites work

• Combinatorics of Compositions and Words
• Counting occurrences of 132 in a permutation
• Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
• Counting subwords in flattened permutations
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• Pattern avoidance in ``flattened partitions
• Patterns in permutations and words.
• The enumeration of permutations with a prescribed number of ``forbidden patterns
• The On-Line Encyclopedia of Integer Sequences

Cited in

(5)

• On pattern avoiding flattened set partitions
• Counting subwords in flattened permutations
• The sets of flattened partitions with forbidden patterns
• Recurrence relations in counting the pattern 13-2 in flattened permutations
• Avoidance of vincular patterns by flattened derangements

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Recurrence relations for patterns of type (2,1) in flattened permutations

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