Enumerating pairs of permutations with the same up-down form
type: Item
instance of: scholarly article
title: Enumerating pairs of permutations with the same up-down form
zbMATH Open document ID: 0566.05004
DOI: 10.1016/0012-365X(85)90114-1
published in: Discrete Mathematics
publication date: 1985-01-01T00:00:00Z
review text: Consider the set of all permutations of \(P=\{1,2,...,n\}\). The signature of a given permutation \(\sigma =(\sigma_ 1,...,\sigma_ n)\) is given by the array \(g(\sigma)=(q_ 1,...,q_{n-1})\) with \(q_ i\doteq sgn(\sigma_{i+1}-\sigma_ i)\in \{+,-\}\). The author studies the probability \(p_ n\) that two permutations chosen at random from \({\mathcal S}_ n\) will have the same signature. If \(N_ n(q)\) is the number of all permutations with given signature q, then \(p_ n=\sum_{q}(N_ n(q)/n!)^ 2\). It is shown that \(p_ n\sim 2c\alpha^ n\) as \(n\to \infty\) with \(c\approx 0.82064180\), \(\alpha\) \(\approx 0.55240601\). Here \(\alpha =(1/2)\theta_ 1\) with \(\theta_ 1\) being the smallest zero for 1-\(\sum^{\infty}_{k=0}(E_{2k+1}/(2k+1)!)^ 2\theta^{2k+1}\), E's being the tangent numbers. This asymptotics is obtained by eigenexpansion from the formula \(p_ n=\int^{1}_{0}\int^{1}_{0}(K^{n- 1}1)(x,y)dx dy\) where \(K^{n-1}\) is the iterated integral operator K, \(K\phi (x,y)=\int^{1}_{0}\int^{1}_{0}K(x,y;x',y')\phi (x',y')dx'dy'\) with K(x,y;x',y') being 1 if (x-x')(y-y')\(>0\) and 0 otherwise. Based on numerical experiments some conjectures are made on asymptotic behaviour of the random variable \(Z(q)=2^{n-1}N_ n(q)/n!\).
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 3902657
zbMATH Keywords: signature of a permutation
zbMATH Keywords: permutations with the same signature
author: Colin L. Mallows
author: Larry Shepp
reviewed by: U. Kaljulaid
MaRDI profile type: Publication
cites work: Q5558293
cites work: Some Aspects of the Random Sequence
cites work: Permutations with Prescribed Pattern. II. Applications
cites work: Q5603208
cites work: Enumeration of permutations with prescribed up-down and inversion sequences
full work available at URL: 0012-365x(85)90114-1
OpenAlex ID: W2024636731
description: scientific article; zbMATH DE number 3902657