# 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?

-

## closed as too localized by Bill Johnson, Emil Jeřábek, Did, Yemon Choi, Bruce WestburyFeb 8 '12 at 19:07

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

Hint: linearity of expections. – Boris Bukh Feb 8 '12 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 '12 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 '12 at 16:39

## 2 Answers

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 '12 at 14:51
But any one to judge whether this is correct? First, this is rude. Second, the answer might be: yourself. – Did Feb 8 '12 at 15:06
flyusa2010: heaven helps those who help themselves – Yemon Choi Feb 8 '12 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 '12 at 14:36
Thanks very much! – flyusa2010 Feb 8 '12 at 14:39
@Emil Your right, I misread the question. – Pablo Lessa Feb 8 '12 at 15:49