Let n ≥ 2 be an integer and let a1, a2, . . . , an be a permutation of the set {1, 2, . . . , n}. Define a0 = 0 and an+1 = 0, and consider the sequence a0, a1, a2, a3, . . . , an, an+1. A position i with 1 ≤ i ≤ n is called awesome, if ai > ai−1 and ai > ai+1. In words, i is awesome if the value at position i is larger than both its neighboring values. For example, if n = 6 and the permutation is 2, 5, 4, 3, 1, 6, we get the sequence
| Value |
0 |
2 |
5 |
4 |
3 |
1 |
6 |
0 |
| Position |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Consider a uniformly random permutation of the set {1, 2, . . . , n} and define the random variable X to be the number of awesome positions. Determine the expected value E(X) of the random variable X.In this case, the positions 2 and 6 are awesome, whereas the positions 1, 3, 4, and 5 are not awesome.
Hint: Use indicator random variables.