Question

Given n numbers (each of which is a random integer, uniformly between 1~n), what is the expected number of increasing subsequences?

Answer 1

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).

Answer 2

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).