Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
You should mention that you've already asked this question:… – 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.