## What is the expected number of increasing subsequence? [closed]

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

-
Hint: linearity of expections. – Boris Bukh Feb 8 2012 at 14:29
This question is much better suited to math.stackexchange.com, where it is likely to receive a warmer welcome and attract a very quick answer. – cardinal Feb 8 2012 at 14:34
If it is asked at math.stackexchange.com, and it is homework, it should be clearly marked as such – Yemon Choi Feb 8 2012 at 16:39

## closed as too localized by Bill Johnson, Emil Jeřábek, Didier Piau, Yemon Choi, Bruce WestburyFeb 8 2012 at 19:07

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

-
Thanks! But any one to judge whether this is correct? – flyusa2010 Feb 8 2012 at 14:51
But any one to judge whether this is correct? First, this is rude. Second, the answer might be: yourself. – Didier Piau Feb 8 2012 at 15:06
flyusa2010: heaven helps those who help themselves – Yemon Choi Feb 8 2012 at 16:38

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

-
The OP’s experiment does not give permutations. – Emil Jeřábek Feb 8 2012 at 14:36
Thanks very much! – flyusa2010 Feb 8 2012 at 14:39
@Emil Your right, I misread the question. – Pablo Lessa Feb 8 2012 at 15:49