Por medio de enriquecimiento aquí es la complejidad de uso de los números de Stirling
del segundo tipo. Usando la notación de este MSE
enlace tenemos $n$
los cupones, y preguntar sobre el tiempo de espera hasta que un conjunto múltiple que contiene
las instancias de $j$ diferentes cupones ha sido dibujado.
Primero vamos a comprobar que de verdad tienen una distribución de probabilidad
aquí. Tenemos para el número de $T$ de los cupones de ser $m$ sorteos que
$$P[T=m] = \frac{1}{n^m} \times
{n\elegir j-1} \times {m-1\llave j-1} \times (j-1)!
\times (n+1-j).$$
Lo que sucede aquí es que para una carrera de $m$ de muestras para producir un
conjunto múltiple que contiene las instancias de $j$ diferentes cupones de descuento para la primera
tiempo en el último ejemplo tenemos dos partes, un prefijo de longitud $m-1$
y un terminal de la muestra, que completa el conjunto. Por lo tanto debemos elegir
el $j-1$ valores excluyendo el que se produce la última para el prefijo
de la $n$ posibilidades que da el primer coeficiente binomial.
A continuación tenemos la partición de la primera $m-1$ ranuras en las $j-1$ no vacía de conjuntos en
un conjunto ordenado de la partición. (Stirling número y factorial). El
menor valor elegido se pone las ranuras que aparecen en la primera, el siguiente
uno de esos en el segundo set, etc. Finalmente llegamos $n-(j-1)$
posibilidades ($j-1$ valores del prefijo ya han sido utilizados)
para el terminal de la muestra que se completa la selección. Se combinan con
$n^m$ opciones posibles.
Recordar la OGF de los números de Stirling del segundo tipo que dice
que
$${n\brace k} = [z^n] \prod_{q=1}^k \frac{z}{1-qz}.$$
Esto da por la suma de las probabilidades
$$\sum_{m\ge 1} P[T=m]
= {n\elegir j-1} (j-1)! (n+1-j)
\frac{1}{n} \sum_{m\ge 1} \frac{1}{n^{m-1}} {m-1\llave j-1}.$$
Centrándose en la suma obtenemos
$$\sum_{m\ge 1} \frac{1}{n^{m-1}}
[z^{m-1}] \prod_{q=1}^{j-1} \frac{z}{1-qz}
= \prod_{q=1}^{j-1} \frac{1/n}{1-p/n}
\\ = \prod_{q=1}^{j-1} \frac{1}{n-q}
= \frac{(n-j)!}{(n-1)!}.$$
La combinación de este con el exterior factor obtenemos
$${n\elegir j-1} (j-1)! (n+1-j)
\frac{1}{n} \frac{(n-j)!}{(n-1)!}
\\ = {n\elegir j-1} (j-1)! \frac{(n+1-j)!}{n!} = 1$$
Esto confirma que es una distribución de probabilidad.
A continuación, obtener por la expectativa de que
$$\sum_{m\ge 1} m\times P[T=m]
\\ = {n\elegir j-1} (j-1)! (n+1-j)
\frac{1}{n} \sum_{m\ge 1} \frac{m}{n^{m-1}} {m-1\llave j-1}.$$
Que una vez más se centran en la suma para obtener
$$\sum_{m\ge 1} \frac{m}{n^{m-1}}
[z^{m-1}] \prod_{q=1}^{j-1} \frac{z}{1-qz}
= \sum_{m\ge 1} \frac{m}{n^{m-1}}
[z^{m}] z \prod_{q=1}^{j-1} \frac{z}{1-qz}
\\ = \left.\a la izquierda( \prod_{q=0}^{j-1}
\frac{z}{1-qz} \right)'\right|_{z=1/n}
\\ = \left.\a la izquierda( \prod_{q=0}^{j-1}
\frac{z}{1-qz} \sum_{p=0}^{j-1} \frac{1-pz}{z}
\frac{1}{(1-pz)^2}
\right)\right|_{z=1/n}
\\ = \left.\a la izquierda( \prod_{q=0}^{j-1}
\frac{z}{1-qz} \sum_{p=0}^{j-1} \frac{1}{z}
\frac{1}{1-pz}
\right)\right|_{z=1/n}
\\ = \prod_{q=0}^{j-1} \frac{1/n}{1-p/n}
\sum_{p=0}^{j-1} \frac{1}{1/n}
\frac{1}{1-p/n}
\\ = \prod_{q=0}^{j-1} \frac{1}{n-q}
\sum_{p=0}^{j-1}
\frac{n^2}{n-p}
= n \prod_{q=1}^{j-1} \frac{1}{n-q}
\sum_{p=0}^{j-1}
\frac{1}{n-p}.$$
Recuperar el exterior, factor que hemos
$${n\elegir j-1} (j-1)! (n+1-j)
\frac{1}{n} \frac{(n-j)!}{(n-1)!} \n
\sum_{p=0}^{j-1} \frac{1}{n-p}.$$
El delantero se simplifica a uno como antes y nos quedamos con
$$n\sum_{p=0}^{j-1} \frac{1}{n-p}
= n \left(\sum_{p=0}^{n-1} \frac{1}{n-p}
- \sum_{p=j}^{n-1} \frac{1}{n-p}\right).$$
Este es
$$\bbox[5px,border:2px solid #00A000]{\Large
n \times \left( H_n - H_{n-j} \right)}$$
Este rendimientos $n H_n$ al $j = n$ $1$ al $j=1$ que son
correcto. El uso de $H_n \sim \log n + \gamma$ obtenemos $j = n/2$ el
expectativa $n\log 2.$
