Enumerating pairs of permutations with the same up-down form (Q1059077): Difference between revisions
From MaRDI portal
Removed claims |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Colin L. Mallows / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Lawrence A. Shepp / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Uno Kaljulaid / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5558293 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some Aspects of the Random Sequence / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Permutations with Prescribed Pattern. II. Applications / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5603208 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Enumeration of permutations with prescribed up-down and inversion sequences / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(85)90114-1 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2024636731 / rank | |||
Normal rank |
Latest revision as of 11:52, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Enumerating pairs of permutations with the same up-down form |
scientific article |
Statements
Enumerating pairs of permutations with the same up-down form (English)
0 references
1985
0 references
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!\).
0 references
signature of a permutation
0 references
permutations with the same signature
0 references