Counting permutations by their rigid patterns

DOI10.1006/JCTA.2002.3279MaRDI QIDQ696917zbMATH OpenOpenAlexFDO

Authors Amy N. Myers

Publication date 12 September 2002

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/39c6e9e9038e6e44e03187372b3cd2c23f743e8e

zbMATH Keywords

exact enumeration

Mathematics Subject Classification ID

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

Review text

A rigid pattern is a sequence \(\tau= \tau_1\tau_2\cdots\tau_k\) of \(k\) distinct positive integers. An occurrence of \(\tau\) in an \(n\)-permutation \(\sigma= \sigma_1\sigma_2\cdots\sigma_n\) is a subword \(\sigma_{i+1} \sigma_{i+2}\cdots\sigma_{i+k}\) of \(\sigma\) such that for some integer \(c\), \(\sigma_{i+j}= \tau_j\) for \(1\leq j\leq k\). This article finds the number of \(n\)-permutations containing exactly \(m\) occurrences of a given rigid pattern \(\tau\) as a function of \(n\), \(m\) and certain properties of \(\tau\). This result generalizes a solution given in the beginning of the article to a problem posed by Herbert Wilf. The analogous problem for a pattern, where the subword of \(\sigma\) need not consist of numbers in consecutive positions and its \(i\)th number need only be greater than its \(j\)th one iff \(\tau_i> \tau_j\) rather than being related by the same additive constant, is still unsolved in general. The article refers to some special case solutions in the literature.

Recommendations

• scientific article; zbMATH DE number 2192093
• Generalized permutation patterns -- a short survey
• The patterns of permutations
• Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
• Patterns in permutations and words.

Cites work

• Classification of forbidden subsequences of length 4
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• scientific article; zbMATH DE number 3695198 (Why is no real title available?)
• Permutation patterns and continued fractions
• Restricted permutations
• The enumeration of permutations with a prescribed number of ``forbidden patterns
• The On-Line Encyclopedia of Integer Sequences
• The solution of a conjecture of Stanley and Wilf for all layered patterns

Cited in

(14)

• Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations
• From Hertzsprung's problem to pattern-rewriting systems
• New theoretical bounds and constructions of permutation codes under block permutation metric
• A discrete probability problem in card shuffling
• scientific article; zbMATH DE number 2186873 (Why is no real title available?)
• Stacking Blocks and Counting Permutations
• scientific article; zbMATH DE number 5163456 (Why is no real title available?)
• scientific article; zbMATH DE number 3908439 (Why is no real title available?)
• A counting scheme and some algebraic properties of a class of special permutation patterns
• A new metric on symmetric groups and applications to block permutation codes
• A central limit theorem for a card shuffling problem
• Asymptotics of self-overlapping permutations
• Penney's game for permutations
• Where the monotone pattern (mostly) rules

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Counting permutations by their rigid patterns

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