Enumerating pairs of permutations with the same up-down form
Consider the set of all permutations of \(P=\{1,2,\ldots,n\}\). The signature of a given permutation \(\sigma = (\sigma_1,\ldots,\sigma_n)\) is given by the array \(g(\sigma)=(q_1,\ldots,q_{n-1})\) with \(q_i\doteq \mathrm{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 eigen expansion 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 the asymptotic behaviour of the random variable \(Z(q)=2^{n-1}N_n(q)/n!\).
- Enumeration of permutations with prescribed up-down and inversion sequences
- scientific article; zbMATH DE number 3273551 (Why is no real title available?)
- scientific article; zbMATH DE number 3322983 (Why is no real title available?)
- Permutations with Prescribed Pattern. II. Applications
- Some Aspects of the Random Sequence
This page was built for publication: Enumerating pairs of permutations with the same up-down form
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1059077)