Given n numbers (each of which is a random integer, uniformly between 1~n), what is the expected number of increasing subsequences?
closed as too localized by Bill Johnson, Emil Jeřábek, Did, Yemon Choi, Bruce Westbury Feb 8 '12 at 19:07This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question. 


This is not a researchlevel 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(n1)\cdots(nk+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). 


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

