1
$\begingroup$

Let $P(x)$ be the length of the longest decreasing subsequence in a permutation $x$ such that the first element of $x$ is a part of that subsequence. What is the average value of $P(x)$ for all the permutations of $1234567$?

Here's the current sketch of my solution Let $N$ be the sum of all $P(x)$ over permutations of $1234567$

The digit $7$ can only add $1$ to our count of $N$ if it is the first number in the list. The number of times $7$ is first in the list is $6!$

The digit $6$ can only add $1$ to our count of $N$ if it is the first or second number in the list. The number of times $6$ is first in the list is $6!$. When 6 is second in the list 7 must be first in the list if we want it to add to our count so the total count for 6 is $6!+5!$.

The digit $5$ can only add to our count if its in position 1,2,3(with some restrictions). The number of ways this can happen is $6!+2*5!+4!$

The digit $4$ can only add to our count if its in position 1,2,3,4. The number of ways this can happen is $6!+3*5!+3*4!+3!$ (looking a lot like pascals) But this method is still much slower than I would like to be so anyone have any ideas on how to solve this problem more efficiently.

$\endgroup$
  • $\begingroup$ I'm just posing an interesting math puzzle, not "outsourcing my homework" my title does need work not sure what to put but I am open to some suggestions. $\endgroup$ – Anirudh Jul 1 '17 at 1:14
  • $\begingroup$ math.stackexchange.com/tour $\endgroup$ – Anirudh Jul 1 '17 at 1:18
  • $\begingroup$ Says you can ask for mathematical puzzles, I don't know the answer to the puzzle and haven't made much progress yet because I don't know where to start $\endgroup$ – Anirudh Jul 1 '17 at 1:18
1
$\begingroup$

Hint: A permutation either starts with the largest element or not. If it does, the length is one more than the function on the rest. If not, the length is the same as if the largest element is not there. This should suggest a recurrence.

Added: If we want to evaluate $P(x)$, we have $x!$ permutations. In $(x-1)!$ of those the largest element comes first, adding $1$ to the length of the permutation of the rest which follows. In the rest, the largest element comes somewhere later and is not part of the longest decreasing subsequence, so we can ignore it. This gives $P(x)=\frac {(x-1)!}{x!}(1+P(x-1))+\left(1-\frac {(x-1)!}{x!}\right)P(x-1)=\frac 1x(P(x-1)+1)+\frac{x-1}xP(x-1)=P(x-1)+\frac 1x$ Given $P(1)=1$ we have that $P(x)=\sum_{i=1}^x\frac 1i=H_x$ the $x^{\text{th}}$ harmonic number.

$\endgroup$
  • $\begingroup$ Still stuck with your hint it seems like a good way to approach the problem im still not sure what to do if the permutation does not start with its largest element. $\endgroup$ – Anirudh Jul 1 '17 at 2:04
  • $\begingroup$ Then the largest element is not part of the decreasing subsequence, so you can just ignore it. $\endgroup$ – Ross Millikan Jul 1 '17 at 2:17
  • $\begingroup$ I made some progress with your hint, but got stuck again. I would appreciate some additional help, I wrote up my current idea in a edited question statement. $\endgroup$ – Anirudh Jul 1 '17 at 2:19
  • $\begingroup$ You missed the point of the recurrence. See my edit. $\endgroup$ – Ross Millikan Jul 1 '17 at 2:23
  • $\begingroup$ Wow great elegant solution thank you! $\endgroup$ – Anirudh Jul 1 '17 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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