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

-
You should mention that you've already asked this question: mathoverflow.net/questions/87890/… – Ben Derrett Feb 8 '12 at 15:00
As currently stated, the questions seems to asks about a random sequence that is allowed to repeat elements (since the default assumption in problems of this kind is that the various numbers in the sequence are independent). However, it looks suspicious that the upper limit for the numbers should be exactly $n$. Could you please state explicitly whether or not the sequence can contain repetitions of the same number? – Henning Makholm Feb 8 '12 at 16:20

To get this question off the Unanswered list:

On Mathoverflow Emil Jeřábek has derived the probability $$\sum_{k=0}^n\binom nk^2n^{-k}=\frac1{n^n}\sum_{k=0}^n\binom{n}k^2n^k\;.$$

The sequence $$\left\langle\sum_{k=0}^n\binom{n}k^2n^k:n\in\omega\right\rangle$$

is OEIS A187021, where the alternative description is given:

\begin{align*} \sum_{k=0}^n\binom{n}k^2n^k&=[x^n]\Big(1+(n+1)x+nx^2\Big)^n\\ &=[x^n]\Big((1+x)(1+nx)\Big)^n\;, \end{align*}

the coefficient of $x^n$ in $\Big((1+x)(1+nx)\Big)^n$. The desired probability could therefore also be written $$[x^n]\left((1+x)\left(\frac1n+x\right)\right)^n\;,$$ if one so desired.

-