UVA problem seemingly above the State of the Art

Revision en2, by chubakueno, 2015-10-11 18:43:43

I stumbled upon UVA Summing the Lengths of the Longest Increasing Subsequence of Permutations, that basically asks for the first three digits of the sum of the LIS lengths over all permutations of length n. After trying it or a few days, I gave up and searched for information. It is easy to see that:

Where denotes the expected value. It is easy to manage the logarithm of that number with Stirling's approximation, get the fractional part of the logarithm and exponentiate to get the first digits. Nevertheless the core of the problem lies in computing for a random permutation w of length n. I have been reading about the topic, and this paper gives the estimate

Where c ≈  - 1.77108 as a known estimate. I have also asked the question in MathOverflow, and it seems that that estimate is the best known and that there is no polynomial or logarithmic time algorithm for computing .

Finally, I am right now trying to contact the problemsetter baodog looking for clues, as there seems to be few options now:

  • He has improved the state of the art in computing without knowing so and expects the contestant to do so too.
  • He has not improved the state of the art and expects the contestant to provide a solution.

The problem stats page is quite strange too, since the only accepted solution's are Josh Bao's in the 2007 and someone else 20 days later. Also, the old version of the problem asks for the first 5 digits and has a different output for the same input truncating it to the first 3 digits.

So, can someone provide help to solve this problem and I am not seeing something obvious? Am I right and this problem is impossible with today's knowledge of the matter?

Tags math, combinatorics, statistics

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English chubakueno 2015-10-11 19:08:51 19 Tiny change: 'Josh Bao's in the $2' -
en4 English chubakueno 2015-10-11 18:58:27 178 Tiny change: 'estionable to say the least.\nThe [pr' -> 'estionable.\nThe [pr'
en3 English chubakueno 2015-10-11 18:49:22 149 Tiny change: ' in about $5%$ of the ca' -
en2 English chubakueno 2015-10-11 18:43:43 34 Tiny change: 'equence-of?noredirect=1#comment544177_220595), and it ' -> 'equence-of), and it '
en1 English chubakueno 2015-10-11 18:40:31 2441 Initial revision (published)