Evaluación de un límite con coeficientes binomiales.

Question

Si $N_c=\lfloor \frac{1}{2}n\log n+cn\rfloor$ para algún número entero $n$ y la constante real $c$ Entonces, ¿cómo se puede demostrar la siguiente identidad en la que $k$ es un número entero fijo:

$$\lim_{n\rightarrow \infty} \binom{n}{k}\frac{\binom{\binom{n-k}{2}}{N_c}}{\binom{\binom{n}{2}}{N_c}}=\frac{e^{-2kc}}{k!}.$$

Me parece que usar la aproximación de Stirling ayudaría, pero no consigo averiguar cómo...

Hago esta pregunta porque actualmente estoy tratando de entender el artículo en el que Erdos inició el estudio de la evolución de los grafos aleatorios

P. Erdos y A. Rényi, En los gráficos aleatorios I Publicationes Mathematicae Debrecen 6 (1959), pp.290-297, Enlace al Proyecto Erdos .

donde entender esta cantidad es un paso clave para calcular la probabilidad de que un gráfico en $n$ vértices con $N_c$ aristas elegidas al azar está completamente conectada.

Answer 1

Todavía hay que justificar las aproximaciones, pero ésta es la estrategia básica. Se empieza multiplicando por $k!$ , para conseguir

$$ \begin{eqnarray*}{k!{n\choose k}}{{{n-k\choose 2}\choose N_c}\over{{n\choose 2}\choose N_c}} &=&n^k \prod_{i=0}^{k-1}\left(1-{i\over n}\right) \prod_{j={n-k\choose 2}+1}^{n\choose 2} \left(1-{N_c\over j}\right)\\ &\approx&n^k \prod_{j={n-k\choose 2}+1}^{n\choose 2} \left(1-{N_c\over j}\right).\end{eqnarray*} $$

Tomando el logaritmo se obtiene $$k\log(n)+\sum_{j={n-k\choose 2}+1}^{n\choose 2} \log\left(1-{N_c\over j}\right) \approx k\log(n)-N_c\sum_{j={n-k\choose 2}+1}^{n\choose 2} {1\over j}. \tag 1$$ Tenga en cuenta que $\lim_{n\to\infty}N_c/j=0$ . Para $0\leq x\leq 1/2$ tenemos $0\leq -\log(1-x)-x\leq x^2$ Así pues, para los grandes $n$ $$ \left|\sum_{j={n-k\choose 2}+1}^{n\choose 2} \log\left(1-{N_c\over j}\right)+ N_c\sum_{j={n-k\choose 2}+1}^{n\choose 2} {1\over j}\right| \leq N_c^2\sum_{j={n-k\choose 2}+1}^{n\choose 2}{1\over j^2} \leq N_c^2{{n\choose 2}-{n-k\choose 2}\over{{n-k\choose 2}^2}}$$ cuyo lado derecho va a cero como $n\to\infty$ . Esto justifica (1).

Una vez que te convenzas de que $\sum_{j={n-k\choose 2}+1}^{n\choose 2}{1\over j}\approx 2k/n$ , y sustituir la expresión de $N_c$ El $k\log(n)$ los términos de la derecha de (1) se cancelan y queda con $-2ck$ . Así se obtiene el resultado deseado.