Sorted and/or sortable permutations
type: Item
instance of: scholarly article
title: Sorted and/or sortable permutations
zbMATH Open document ID: 0961.05001
DOI: 10.1016/S0012-365X(00)00146-1
author: Mireille Bousquet-Mélou
published in: Discrete Mathematics
publication date: 2001-05-21T00:00:00Z
review text: This paper studies a procedure \(\Pi\) which partly sorts permutations, which can be defined recursively as follows: If \(\sigma\) is a permutation in which the largest letter is \(n\) we write it as \(\sigma=\sigma_1 n\sigma_2\) where \(\sigma_1\) and \(\sigma_2\) are subwords of \(\sigma\) and then define \(\Pi(\sigma_1 n\sigma_2)=\Pi(\sigma_1)\Pi(\sigma_2)n\). The main objects studied in this paper are the permutations which can be fully sorted by either one or two applications of \(\Pi\), and the permutations which are in the image of \(\Pi\). Characterisations and recognition algorithms for these permutations are found, as are functional equations for their generating functions. In some cases these equations are solved explicitly, in others \(q\)-analogues are found which count the number of inversions in the permutations. The paper is accessible and well written and includes a number of nice connections between permutations and labelled binary trees.
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1546489
zbMATH Keywords: permutation
zbMATH Keywords: binary tree
zbMATH Keywords: generating functions
zbMATH Keywords: number of inversions
reviewed by: Ian M. Wanless
MaRDI profile type: Publication
full work available at URL: s0012-365x(00)00146-1
OpenAlex ID: W1980065683
description: scientific article; zbMATH DE number 1546489