A short proof for the number of permutations containing pattern 321 exactly once

MaRDI QIDQ640473zbMATH OpenFDO

Authors Alexander Burstein

Publication date 18 October 2011

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

Full work available at URL http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i2p21.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

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

Review text

A \textit{pattern} is an equivalence class of sequences under order isomorphism; a sequence \(\sigma\) \textit{contains} a pattern \(\tau\) if \(\sigma\) has a subsequence which is order-isomorphic to \(\tau\). The set of permutations in \(S_n\) containing pattern \(\tau\) exactly \(r\) times is denoted by \(S_n(\tau;r)\). The author provides a ``short proof of \textbf{Theorem 3}: \(\left|S_n(321;1)\right|=\frac3n\cdot{\binom{2n}{n-3}}\) [\textit{J. Noonan}, ``The number of permutations containing exactly one increasing subsequence of length three, Discrete Math.\ 152, No.\ 1--3, 307--313 (1996; Zbl 0852.05009)], using the ``block decomposition method of [\textit{T. Mansour} and \textit{A. Vainshtein}, ``Restricted permutations and Chebyshev polynomials, Sémin.\ Lothar.\ Comb.\ 47, 17 p.\ (2002; Zbl 1022.05005)].

Recommendations

• scientific article; zbMATH DE number 1375582
• scientific article; zbMATH DE number 2192121
• Enumeration of words that contain the pattern 123 exactly once
• Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
• Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three

Cited in

(8)

• The number of permutations containing exactly one increasing subsequence of length three
• Pattern-functions, statistics, and shallow permutations
• Permutations with exactly one copy of a monotone pattern of length \(k\), and a generalization
• Enumeration of words that contain the pattern 123 exactly once
• scientific article; zbMATH DE number 1375582 (Why is no real title available?)
• Enumeration of Dumont permutations avoiding certain four-letter patterns
• scientific article; zbMATH DE number 7106992 (Why is no real title available?)
• Lattice paths, Lefschetz properties, and Almkvist's conjecture in two variables

This page was built for publication: A short proof for the number of permutations containing pattern 321 exactly once

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