8
$\begingroup$

Kendell-Mann numbers $M(n)$ ( see the sequence A000140 http://oeis.org/A000140 ) have the simple property: $M(n+1) \approx (n-1/2)M(n)$.

The property can be proved by different methods. For eg. The property of Kendall-Mann numbers

What I am looking for is to find out if a combinatorial proof exists?

For eg. Let us start: Suppose we look at all the permutations of $n-1$ in the maximal grouping, then at all the permutation of $n$ in that maximal grouping; is there any simple way in which each permutation in the first set gives rise to $n$ permutations in the second? Better yet, a simple way in which about half the $n-1$-permutations give rise to $n$ $n$-permutations each, and the other half give rise to $n+1$ $n$-permutations each?

Any hints are higly welcomed. I hope that the combinatorial proof will makes the reason for the simple property more transparent.

$\endgroup$
  • 1
    $\begingroup$ Do you agree that the description at OEIS, namely "Kendall-Mann numbers: the maximal number of inversions in a permutation on n letters is floor(n(n-1)/4); a(n) = number of permutations with this many inversions" is wrong? It should refer to the maximum number of permutations having the same number of inversions, right? $\endgroup$ – Brendan McKay Aug 29 '11 at 22:58
  • $\begingroup$ Well, let $I_n(k)$ - the number of permutations of $n$ objects with precisely $k$ inversions. We should study the property of the numbers $M(n)=I_n([n(n-1)/4])$. $\endgroup$ – Mikhail Gaichenkov Aug 30 '11 at 8:15
8
+100
$\begingroup$

Here is a quick and dirty probabilistic analysis which gets the right answer. For a permutation $w \in S_n$, define $$I(w) = \sum_{1 \leq i < j \leq n} \begin{cases} -1 & w(i) < w(j) \\ 1 & w(i) >w(j) \\ \end{cases}.$$ So $I(w) = 2 \# (\mbox{number of inversions of $w$}) - \binom{n}{2}$. If $w$ is chosen uniformly at random, then the expected value of $I(w)$ is $0$.

Now, let's think about the expected value of $I(w)^2$. Squaring the sum, we get terms indexed by $(i_1, j_1, i_2, j_2)$ with $i_1<j_1$ and $i_2< j_2$. If $i_1$, $i_2$, $j_1$ and $j_2$ are all distinct, then the expected value is $0$. If $\{ i_1, j_1 \} \cap \{ i_2, j_2 \}$ is a singleton, we get nonzero contributions. For example, if $i_1 = i_2$, then $2/3$ of the terms are positive one, coming from the cases where $w(i_1)=w(i_2)$ is either the minimium or maximum of $\{ w(i_1), w(i_2), w(j_1), w(j_2))\}$; the other $1/3$ of the terms are negative one. There are $2 \binom{n}{3}$ pairs $((i_1, j_1), (i_2, j_2))$ with $i_1=i_2 < j_1, j_2$. Going through all cases, I get $4 \binom{n}{3}$ cases with expectation $1/3$ and $2 \binom{n}{3}$ with expectation $-1/3$, so expectation $\sim n^3/9$ as a whole. The case where $\{ i_1, j_1 \} \cap \{ i_2, j_2 \}$ has two elements only contributes $O(n^2)$.

So $I(w)$ has expected value $0$ and standard deviation $n^{3/2}/3$. Without further data, I would expect the probability of it assuming its modal value to be $c/n^{3/2}$. So I expect $M(n) \approx c n!/n^{3/2}$ and $$\frac{M(n+1)}{M(n)} \approx \frac{(n+1)(n+1)^{-3/2}}{n^{-3/2}} = n (1+1/n)^{-1/2} \approx n-1/2.$$

$\endgroup$
  • $\begingroup$ Thank you for a new view on it. It's clear. Could you have a look On mixing of diffusing particles (arxiv.org/abs/1010.2563) where the similar pairs appear please? What would be the special situation for the systems of particles to get the same property? In other words If it's possible to build the two physical systems which yield n-1/2 from the chaos of permutations ? $\endgroup$ – Mikhail Gaichenkov Apr 6 '18 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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