Counting permutations by their rigid patterns
type: Item
instance of: scholarly article
title: Counting permutations by their rigid patterns
zbMATH Open document ID: 1006.05008
published in: Journal of Combinatorial Theory. Series A
publication date: 2002-09-12T00:00:00Z
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.
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 1800281
zbMATH Keywords: exact enumeration
author: Amy N. Myers
reviewed by: Timothy R. S. Walsh
describes a project that uses: OEIS
MaRDI profile type: Publication
OpenAlex ID: W2102040169
cites work: Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
cites work: The solution of a conjecture of Stanley and Wilf for all layered patterns
cites work: Q3889060
cites work: The enumeration of permutations with a prescribed number of ``forbidden'' patterns
cites work: Restricted permutations
cites work: The On-Line Encyclopedia of Integer Sequences
cites work: Classification of forbidden subsequences of length 4
cites work: Permutation patterns and continued fractions
DOI: 10.1006/JCTA.2002.3279
description: scientific article; zbMATH DE number 1800281