A combinatorial proof for the property of KM numbers?

Question

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.

Answer 1

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