# A combinatorial proof for the property of KM numbers?

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.

• 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? Commented Aug 29, 2011 at 22:58
• 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])$. Commented Aug 30, 2011 at 8:15

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.$$