I am studying probability model of random permetuation Let $b(n; k)$ denote the number of permutations of {1,...,n} with precisely k inversions ($inv(\pi)$). The analytic approach was considered by L.Clark in article 'An Asymptotic Expansion for the Number of Permutations with a Certain Number of Inversions'. $b(n; k)$ is represented via Bernoulli numbers and Hermite polynomials http://www.combinatorics.org/ojs/index.php/eljc/article/view/v7i1r50/pdf, Research Paper 50, 11 pp. 1

Looking at probabilistic model it is known that

(1) $\left| P\left( \frac{\mathrm{inv}(\pi)-\frac 12{n\choose 2}}{\sqrt{n(n-1)(2n+5)/72}}\leq x\right)-\Phi(x)\right| \leq \frac{C}{\sqrt{n}}$ http://arxiv.org/PS_cache/math/pdf/0508/0508242v2.pdf

My next step was to have more advanced model. So I took into account asymptotic expansions in the central limit theorem (for more details see V. V. Petrov, Sums of independent random variables.):

(2) $F_N (x)=Φ(x)+\frac{3}{50\sqrt{2π}} e^{-x^2/2} (x^3-3x) \frac {6N^3+21N^2+31N+31} {N(2N+5)^2 (N-1)}+O(\frac{1}{N^2} )$ Generally speaking it is possible to calculate the next terms if needed ( also the series convergence - it is possible to prove it).

Actually I am trying to find any explanations about the advantages and disadvantages of the probabilistic model with comparing to the asymptotic expansion via Bernoulli numbers and Hermite polynomials?

Any help is highly welcomed. Thank you in advance.

up vote 1 down vote accepted

Which formula to prefer depends mainly on what you want to do with it. Do you need high precision, or do you have to do complicated things with the approximation? The expansion in Hermite-polynomials easily gives you good error terms, however, the $S_{2q}(n)$-terms are so complicated that I would rather not work with them. However, you could try to do whatever computations you want to do without expanding them, hoping that in the end at least some of them cancel, or some simple estimates give you what you need. The central limit theorem gives the same error only with a lot of work, but the expressions you obtain are rather simple. Note that in your expression the rational function $\frac{6N^3+21N^2+31N+31}{N(2N+5)^2(N−1)}$ equals $\frac{3}{2N}+O(\frac{1}{N^2})$, so you actually do get some neat formula. Of course you could take the expansion into Hermite polynomials, and compute a central limit type expansion in $N$. This might be easier then doing the computations for the central limit theorem anew.

  • One thing is to study Mixing of diffusing particles when it is possible to take into account the number of diffusing particles - Please see Ben Naim work: Mixing of diffusing particles. Would it be possible? arxiv.org/pdf/1010.2563.pdf – Mikhail Gaichenkov Feb 12 '14 at 4:08

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.