4
$\begingroup$

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 [email protected]

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$ Nov 19, 2010 at 5:49
  • $\begingroup$ 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 $\endgroup$ Nov 20, 2010 at 11:51
  • $\begingroup$ 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. $\endgroup$ Nov 22, 2010 at 0:17
  • $\begingroup$ 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. $\endgroup$ Nov 24, 2010 at 17:47
  • $\begingroup$ One mathematician got an answere $M(n)=C\frac{n!}{\sqrt{n(n+1)(2n+1)}}(1+O(1/n)).$ $\endgroup$ Nov 25, 2010 at 7:32

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Nov 27, 2010 at 15:43
  • $\begingroup$ $M(n)=n!(1+O (n^{-1+\epsilon}))/ \sqrt{A\pi}$. $ A = n(n-1)(2n+5)/36$ $\endgroup$ Dec 3, 2010 at 19:26
  • $\begingroup$ 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 $\endgroup$ Dec 3, 2010 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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