2

Part of 1989 Poland - Second Round

Problems(1)

expected value of random variable X is \sum_{k=1}^n \frac{1}{k!}

Source: Polish MO Recond Round 1989 p2

For a randomly selected permutation

\mathbf{f} = (f_1,..., f_n)

\{1,\ldots, n\}

let us denote by

X(\mathbf{f})

the largest number

k \leq n

f_i < f_{ i+1}

for all numbers

i < k

. Prove that the expected value of the random variable

X

\sum_{k=1}^n \frac{1}{k!}

probabilitycombinatoricspermutation