As n -> n+1 , the only change in k(n) occurs for P = (n+1, ..., 2, 1) , when k increases by 1 ; so k(n) = k(n-1) + 1/n! = \sum_{m <= n} 1/m! , whence incidentally k -> e as n -> oo . WFL On 12/28/18, David Wilson <davidwwilson@comcast.net> wrote:

Let P be a permutation of {1, 2, ..., n}.

Let the longest initial decreasing prefix of P have k elements.

For example, let n = 5 and P = (5, 3, 2, 4, 1)

Then the longest decreasing prefix of P is (5, 3, 2), so k = 3 and P_k = 2.

In terms of n, what is the expected value of k? of P_k?

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun