Enumerating pairs of permutations with the same up-down form
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!\).
scientific article; zbMATH DE number 3902657