×

On the application of the theory of probability to two combinatorial problems involving permutations. (English) Zbl 0619.60013

Probability theory, Proc. 7th Conf., Braşov/Rom. 1982, 137-147 (1984).
[For the entire collection see Zbl 0584.00020.]
The number of permutations of \(S=\{1,2,...,n\}\) with exactly k falls \((\sigma(j) > \sigma (j+1))\) is equal to \(A(n,k),\) the Eulerian numbers. It is also known that \(A(n,k)\) and the peak numbers \(M(n,k),\) \((\sigma(j)>\sigma (j-1)\) and \(\sigma(j) > \sigma(j+1))\), are approximately normally distributed. The author gives a simple proof of this property and obtains the improved asymptotic expression: \[ \frac{M(n,k)}{n!}=\sqrt{\frac{45}{4\pi (n+1)}}e^{-x^ 2/2}(1- \frac{1}{126}\sqrt{\frac{45}{2(n+1)}}(x^ 3-3x))+O(\frac{1}{n\sqrt{n}}) \] uniformly for all x, if \(k=(n+1)/3+x\sqrt{\frac{2}{45}(n+1)}.\) An asymptotic expression of the distribution of the Eulerian numbers for non central values of k is also given. Finally a process of runs is examined in closed connection with \(A(n,k)\) and \(M(n,k).\)
Reviewer: G.Philippou

MSC:

60C05 Combinatorial probability

Citations:

Zbl 0584.00020