Length[Union[RandomInteger[{1, k}, n]]] = ?

[Гост]

Въпрос, на който попаднах тези дни, блъскайки си главата с нещо съвсем различно...

Нека [tex]n[/tex] пъти изберем случайно цяло число в интервала [tex][1, k][/tex]. От така получените [tex]n[/tex] числа премахваме всички повторения. Какво е очакването за броя на оставащите числа?

До момента съм забелязал, че при [tex]n = k[/tex] резултатът се колебае около [tex]0.621 * n[/tex]:
https://goo.gl/tQJMVW

Логиката подсказва и че при фиксирано [tex]k[/tex], и [tex]n \rightarrow infinity[/tex], резултатът ще е [tex]k[/tex].
Също, при фиксирано [tex]n[/tex], и [tex]k \rightarrow infinity[/tex], резултатът ще е [tex]n[/tex].
Само че като 'попитам' WolframAlpha какво става когато някое измежду [tex]n[/tex] и [tex]k[/tex] клони към безкрайност, отговорът е [tex]2[/tex]... което просто не е вярно : )

Някакви идеи?

П.П. Ще сменя заглавието на темата, ако не е подходящо

[pal702004]

Ако означим с $a_n$ средният брой на различните числа след $n$ опита, то $n+1$ -ото число с вероятност $\frac{a_n}{k}$ няма да е ново и с вероятност $\frac{k-a_n}{k}$ ще е ново, или

$a_{n+1}=\frac{a_n}{k}\cdot a_n+\frac{k-a_n}{k}\cdot (a_n+1)$

$a_{n+1}=1+a_n-\frac{a_n}{k},\;\;a_1=1$

$a_n=k\left[1-\left(1-\frac 1 k\right)^n\right]$

При големи $n,k$

$ a_n\approx k(1-e^{-\frac n k})$

[Гост]

Много добре, благодаря : )

Току-що проверих формулата с няколко големи стойности на [tex]n[/tex] и [tex]k[/tex] и произволно генерирани за тях числа - резултатите отговарят.