Expected value involving permutation

Question

Let $X_n$ be the number of increasing sequences (IS) in a random permutation of $\{1,2,\ldots, n\}$ and $Y_n$ be the number of decreasing sequences in a permutation of $\{1,2,\ldots, n\}.$ For instance, the number $12453$ has $2$ increasing sequences: namely $1245$ and $3$ and $4$ decreasing sequences, namely $1, 2, 4, 53$. Find the expected value of $X_n$ and $Y_n.$

I know the following recursion for $P(X_n = k) =: p_n(k)$: $$p_n(k) = \dfrac{k}n p_{n-1} (k) + \dfrac{n-(k+1)}n p_{n-1}(k-1).$$ Essentially, to obtain $k$ increasing sequences in a permutation of $\{1,2,\cdots, n\},$ one must have either $k$ or $k-1$ increasing sequences if one removes $n$ from the permutation; adding an element can only increase the number of increasing sequences by $1$ at most as a new element is either at the end of an increasing sequence or strictly between the start and end of an increasing sequence. If there are $k$ ascents when we remove $n$, this can only happen if we have a permutation of $\{1,2,\ldots, n-1\}$ with $k$ ascents AND we add $n$ to this permutation so that the number of IS's doesn't change. The former occurs with probability $p_{n-1}(k)$ while the latter with probability $\dfrac{k}n$ since there are $k$ ends, one for each IS. Similarly, when there are k-1 IS's when we remove $n$, this occurs when we have a permutation of $\{1,2,\ldots, n-1\}$ with $k-1$ IS's and we choose $n$ so that the number of IS's increases by $1$ (there are $n-k+1$ choices of $n$ in this case). This occurs with probability $\dfrac{n-k+1}n p_{n-1}(k).$ Adding the two (disjoint) probabilities yields the recursion.

I think there might be a relationship between $X_n$ and $Y_n,$ but I'm not sure what that is. Also, by the definition of expected value, we get that $$E(X_n) = \sum_{k=1}^n k p_n(k) = \sum_{k=1}^n k \left(\frac{k}n p_{n-1}(k) + \frac{n-k+1}n p_{n-1}(k-1)\right),$$ but I'm not sure how to simplify this into something more useful.

Answer 1

A quicker way

• By symmetry, $E[X_n]=E[Y_n]$
• Each position is either the start of an increasing sequence or of a decreasing sequence as you have defined them, except the first position which is both. So $X_n +Y_n = n+1$
• So $E[X_n]=E[Y_n]=\frac{n+1}{2}$

If you want the probabilities rather than the expectations, this is the Eulerian numbers divided by $n!$