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]

Improve this question
$\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$
    – Gerry Myerson
    Commented 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$
    – Mikhail Gaichenkov
    Commented 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$
    – Hugh Thomas
    Commented 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$
    – Mikhail Gaichenkov
    Commented 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$
    – Mikhail Gaichenkov
    Commented Nov 25, 2010 at 7:32

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Mikhail Gaichenkov
    Commented 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$
    – Mikhail Gaichenkov
    Commented 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$
    – Mikhail Gaichenkov
    Commented Dec 3, 2010 at 19:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .