Classification of forbidden subsequences of length 4
type: Item
instance of: scholarly article
title: Classification of forbidden subsequences of length 4
zbMATH Open document ID: 0857.05007
published in: European Journal of Combinatorics
publication date: 1997-03-06T00:00:00Z
review text: This paper deals with the classification of forbidden subsequences of length 4, and here `sequence' (or subsequence of a permutation) refers to a sequence of distinct positive integers \((b_1,b_2,\dots,b_k)\). A permutation \(\pi\) is said to avoid a permutation \(\gamma\) if \(\pi\) has no subsequence of type \(\gamma\). The set of \(\gamma\)-avoiding permutations in \(s_n\) is denoted by \(s_n(\gamma)\), and we call \(\gamma\) a forbidden subsequence of \(s_n(\gamma)\). In order to show that \(|s_n(1,2,3,4)|=|s_n(4,1,2,3)|\) for all \(n\in \mathbb{N}\), specific switching operations on \(s_n(1,2,3)\) are constructed resulting in partitioning its elements into equivalence classes. This together with the fact that the tree \(T(1,2,3)\) can be embedded in \(T(1,2,3,4)\) and \(T(4,1,2,3)\) lead us to prove \(|s_n(1,2,3,4)|=|s_n(4,1,2,3)|\) for all \(n\in\mathbb{N}\).
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 930075
zbMATH Keywords: forbidden subsequences
zbMATH Keywords: permutation
author: Zvezdelina E. Stankova
reviewed by: D. V. Chopra
MaRDI profile type: Publication
full work available at URL: eujc.1996.0044
OpenAlex ID: W2047160913
DOI: 10.1006/EUJC.1996.0044
description: scientific article; zbMATH DE number 930075