# What is the average value of P(x) for all the permutations of 1234567?

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.

• 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. – Anirudh Jul 1 '17 at 1:14
• math.stackexchange.com/tour – Anirudh Jul 1 '17 at 1:18
• 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 – Anirudh Jul 1 '17 at 1:18

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.