What is the expected number of increasing subsequence? Given n numbers (each of which is a random integer, uniformly between 1~n), what is the expected number of increasing subsequences?
 A: This is not a research-level question and should be closed, but since someone already gave a wrong answer, I’ll write the correct one.
Given independently uniformly random $x_1,\dots,x_k\in\{1,\dots,n\}$, the probability that the $x_i$’s are pairwise distinct is $n(n-1)\cdots(n-k+1)n^{-k}$, hence the probability that $x_1< x_2<\dots< x_k$ is $\binom nkn^{-k}$. By linearity of expectation, the expected number of increasing subsequences in a randomly chosen sequence $(x_1,\dots,x_n)$ is thus
$$\sum_{k=0}^n\binom nk^2n^{-k}.$$
Note that this includes the empty sequence (which is vacuously increasing).
A: According to:
MR0626437 (84e:05012) 
Lifschitz, V.; Pittelʹ, B.
"The number of increasing subsequences of the random permutation. "
The answer for permutations on $n$ elements is:
$\sum_{k = 1}^n C_{n,k}/k!$
where $C_{n,k}$ is the number of subsets with $k$ elements.
The reason is that for each subset $I$ of $k$ indices from $1$ to $n$ there is a $1/k!$ chance that a random permutation will be increasing when restricted to $I$ (for each set of values only $1$ out of the $k!$ yields an increasing sequence).
