What is the expected number of increasing subsequence?

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

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.