Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The sequence A000140 is studied http://oeis.org/A000140 (Kendall-Mann numbers: the maximum number of permutations on n letters having the same number of inversions ) and I am looking for a proof that M(n)/M(n-1)=n+1/2 when n= infinity, M(n) - max element in row n. If you have any ideas how to proove or disproove it, even the question is too hard, could you let me know in anyway. Modelling with Pari GP shows for n = 0 to 149 M(n)/M(n-1): 1.00000000, 1.00000000, 2.00000000, 3.00000000, 3.66666667, 4.59090909, 5.67326733, 6.69458988, 7.61939520, 8.57906801, 9.60953383, 10.6235009, 11.5884536, 12.5657349, 13.5817521, 14.5907723, 15.5704306, 16.5558579, 17.5656455, 18.5718445, 19.5585507, 20.5484134, 21.5549876, 22.5594838, 23.5501133, 24.5426559, 25.5473665, 26.5507683, 27.5438066, 28.5380914, 29.5416285, 30.5442887, 31.5389122, 32.5343930, 33.5371446, 34.5392804, 35.5350028, 36.5313400, 37.5335406, 38.5352923, 39.5318079, 40.5287792, 41.5305788, 42.5320411, 43.5291478, 44.5266018, 45.5281005, 46.5293394, 47.5268986, 48.5247283, 49.5259956, 50.5270586, 51.5249718, 52.5230999, 53.5241854, 54.5251073, 55.5233026, 56.5216716, 57.5226117, 58.5234188, 59.5218427, 60.5204088, 61.5212309, 62.5219434, 63.5205550, 64.5192845, 65.5200094, 66.5206430, 67.5194106, 68.5182772, 69.5189212, 70.5194882, 71.5183871, 72.5173696, 73.5179455, 74.5184560, 75.5174660, 76.5165477, 77.5170657, 78.5175276, 79.5166329, 80.5157998, 81.5162682, 82.5166882, 83.5158756, 84.5151165, 85.5155421, 86.5159256, 87.5151843, 88.5144896, 89.5148781, 90.5152297, 91.5145507, 92.5139127, 93.5142686, 94.5145921, 95.5139679, 96.5133798, 97.5137071, 98.5140058, 99.5134299, 100.512886, 101.513188, 102.513465, 103.512932, 104.512428, 105.512707, 106.512964, 107.512470, 108.512001, 109.512260, 110.512499, 111.512039, 112.511602, 113.511843, 114.512067, 115.511637, 116.511229, 117.511454, 118.511663, 119.511261, 120.510879, 121.511090, 122.511285, 123.510909, 124.510550, 125.510748, 126.510932, 127.510578, 128.510241, 129.510426, 130.510599, 131.510267, 132.509949, 133.510123, 134.510286, 135.509973, 136.509673, 137.509838, 138.509992, 139.509696, 140.509412, 141.509568, 142.509713, 143.509434, 144.509165, 145.509312, 146.509450, 147.509185, 148.508930,

n+0.5 for n = infinity gaichenkov@yandex.ru

share|improve this question
    
Suppose you 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? –  Gerry Myerson Nov 19 '10 at 5:49
    
Well, the idea is clear to think about it. Actually, I am looking at the maximum element: $M(n)=T(n, n(n-1)/4)$, here the reccurence $T(n+1,k)=T(n,k)+T(n,k-1)+...+T(n,k-n)$. $T(n,k)$ has the maximum when $k=n(n-1)/4$. Also, I know $T(n,k)$ are the coefficients of $P_n(x)=1(1+x)(1+x+x^2)...(1+x+...+x^{n-1})$. So, the general question is how to estimate the max M(n), i.e the max coeficient in $P_n(x)$ effectively? I guess, if I know that then I'll get the answer at once –  Mikhail Gaichenkov Nov 20 '10 at 11:51
    
This doesn't even start to solve the problem, but it puts a different spin on it. $T(n,k)$ is the rank of the vector space $H^k(GL_n/B)$. The Hard Lefschetz theorem then gives you the fact that the sequence $T(n,k)$ is unimodal (for fixed $n$, as $k$ varies). A reference for this idea is: Richard Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property. SIAM J. Algebraic Discrete Methods 1 (1980), no. 2, 168–184. –  Hugh Thomas Nov 22 '10 at 0:17
    
I come accross to another view. Generating functions of permutations on n letters: $F(q)=\frac{\prod{(1-q^k)}}{(1-q)^n}$ then integrate $F(q)/q^l$ (complex). With $q=exp(2ix)$ get $\frac{1}{\pi}\int cos(mx) \prod \frac{sin(kx)}{sin(x)}dx$ where m calculated via l and n. Depending from n/4, m will be 0 or 1 (will the switches result in the 1/2?). Also, should note the area of the integral $|x|<\pi / n$ to see n! Then some futher estimations should go. Will anybody join it to investigate it futher. If we get a proof, then the "different spin" will be more clear to proof in a way. –  Mikhail Gaichenkov Nov 24 '10 at 17:47
    
One mathematician got an answere $M(n)=C\frac{n!}{\sqrt{n(n+1)(2n+1)}}(1+O(1/n)).$ –  Mikhail Gaichenkov Nov 25 '10 at 7:32

1 Answer 1

up vote 8 down vote accepted

It is known that $$ \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}}, $$ where $\Phi(x)$ denotes the standard normal distribution. From this it is immediate that $M(n+1)/M(n)=n-\frac 12+o(1)$. For some references, see http://arxiv.org/PS_cache/math/pdf/0508/0508242v2.pdf.

share|improve this answer
    
Good point to think too. Stein’s method is applied to show that W (inversions of a permutation) satisfies a central limit theorem with error rate $n^{-1/2}$. On the other hand, the basic complex analysis and classical analysis with Euler Product representation of Sin function should present an error rate for the particular case too, and the M(n) with O(1). The error is being investigated. Any comments at this side are highly welcomed. –  Mikhail Gaichenkov Nov 27 '10 at 15:43
    
$M(n)=n!(1+O (n^{-1+\epsilon}))/ \sqrt{A\pi}$. $ A = n(n-1)(2n+5)/36$ –  Mikhail Gaichenkov Dec 3 '10 at 19:26
    
error from n=2 to 18: 0,595769122 0,250044867 0,084111637 0,066041844 0,068568453 0,054024687 0,037563243 0,032785381 0,032782518 0,028992661 0,023807067 0,021830376 0,021573067 0,019891303 0,017496158 0,016414384 0,016145111 –  Mikhail Gaichenkov Dec 3 '10 at 19:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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