Pattern frequency sequences and internal zeros

DOI10.1006/AAMA.2001.0789MaRDI QIDQ696813zbMATH OpenOpenAlexFDO

Authors Miklós Bóna, Bruce E. Sagan, Vincent Vatter

Publication date 12 September 2002

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

patternspermutations

Mathematics Subject Classification ID

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

Abstract: Consider the number of permutations in the symmetric group on n letters that contain c copies of a given pattern. As c varies (with n held fixed) these numbers form a sequence whose properties we study for the monotone patterns and the patterns 1, l, l-1, ..., 2. We show that, except for the patterns 1, 2 and 2, 1 where the sequence is well-known to be log concave, there are infinitely many n where the sequence has internal zeros.

Review text

Let \(p= p_1p_2\cdots p_n\) and \(q= q_1q_2\cdots q_m\) be two permutations. Then \(p\) contains a \(q\)-pattern if and only if there is a subsequence \(p_{i_1}p_{i_2}\cdots p_{i_m}\) of \(p\) whose elements are in the same relative order as those in \(q\). The authors completely determine the existence of internal zeros for all patterns of length at most \(3\).

Recommendations

• Generalized pattern frequency in large permutations
• Generalized permutation patterns -- a short survey
• Permutations containing many patterns
• On multi-dimensional patterns
• Multi-avoidance of generalised patterns

Cites work

• Continued fractions and Catalan problems
• scientific article; zbMATH DE number 568836 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• scientific article; zbMATH DE number 1504635 (Why is no real title available?)
• Permutation patterns and continued fractions
• Permutations with one or two 132-subsequences
• Permutations with restricted patterns and Dyck paths
• Restricted permutations
• The enumeration of permutations with a prescribed number of ``forbidden patterns
• The number of permutations containing exactly one increasing subsequence of length three
• The number of permutations with exactly \(r\) 132-subsequences is \(P\)-recursive in the size!

Cited in

(6)

• Packing sets of patterns
• The pure descent statistic on permutations
• Asymptotics of principal evaluations of Schubert polynomials for layered permutations
• Subsequence frequency in binary words
• Counting occurrences of patterns in permutations
• Bounding quantities related to the packing density of 1(+1) 2

This page was built for publication: Pattern frequency sequences and internal zeros

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