Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
5  
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
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.