Consider a $\omega \in S_n$. Let us define a sequence $\omega(i_1,)<\omega(i_2)<\dots<\omega(i_k)$ where $1\leq i_1\leq\dots\leq i_k\leq n$. This is an ascending subsequence of a permutation. Define $N(\omega)$ to be the number of ascending subsequence of the permutation $\omega$.
I need to prove that $\mathbb{E}[N]=\sum_{k=1}^n\frac{1}{k!}\binom{n}{k}$.
My approach: Now, I would love to give you an elaborate approach of mine, sadly, discrete math is not my strong suit. I know that $\mathbb{E}[X]=\sum_{k\geq 0}k\mathbb{P}(X=k)$ where $\mathbb P$ is the probability function. I have verified this formula for $n=3$, however, this didn't give me any significant idea of how to approach this problem.
I would greatly appreciate your help!
For each subsequence $\sigma$ of $\omega$ let $X_\sigma$ be a random variable that is $1$ if the subsequence is increasing and $0$ otherwise. Then
$$\Bbb E(N)=\sum_\sigma\Bbb E(X_\sigma)\,.$$
There are $k!$ possible orders of the $k$ integers in a $k$-term subsequence of $\omega$, exactly one of which is an ascending sequence. Thus, the probability that any given $k$-term subsequence is ascending is $\frac1{k!}$. Finally, there are $\binom{n}k$ $k$-term subsequences of $\omega$, so
$$\Bbb E(N)=\sum_\sigma\Bbb E(X_\sigma)=\sum_{k=1}^n\binom{n}k\frac1{k!}\,.$$