En la página 23 de [ Erdős+Rényi 1960, "Sobre la evolución de los grafos aleatorios" ], se afirma la siguiente fórmula asintótica sin necesidad de prueba: $$ \binom{n}{k} \sim \frac{n^k \mathrm e^{-\frac{k^2}{2n} - \frac{k^3}{6n^2}}}{k!} $$ válido para $k \in o(n^{\text{[some illegible fraction]}})$ . Es decir, tenemos $$ \frac{n!}{(n-k)!} \;=\; n^k \exp\left(-\tfrac{k^2}{2n} - \tfrac{k^3}{6n^2}\right) \cdot \Bigl[1 \pm o(1)\Bigr].$$ Tenía curiosidad por saber cuáles son las limitaciones del límite superior ilegible de $k$ eran para esta aproximación, y esperaba poder utilizar al menos algunos escala útil para $k \in \Theta(n^{2/3})$ Así que traté de volver a vivirlo. Sin embargo, utilizando La aproximación de Stirling para el factorial, $$ n! = n^{n+\frac{1}{2}} \mathrm e^{-n}\cdot \Bigl[\sqrt{2\pi} + o(1)\Bigr], $$ lo mejor que pude rederivar fue lo siguiente: $$\begin{align} \frac{n!}{(n-k)!} \;&=\; \frac{n^{n-k+\frac{1}{2}} n^k \mathrm e^{n-k}}{(n-k)^{n - k + \frac{1}{2}} \mathrm e^n} \cdot \Bigl[1 \pm o(1)\Bigr] \\&=\; n^k \left(1 - \frac{k}{n}\right)^{-n+k-\frac{1}{2}} \mathrm{e}^{-k} \cdot \Bigl[1 \pm o(1)\Bigr]\end{align}$$ que parece que debería escalar como $$ \frac{n!}{(n-k)!} \;\;\stackrel{\;?\,}\sim\;\; n^k \exp\Bigl( - \tfrac{k^2}{n} + \tfrac{k}{2n} \Bigr),$$ para todos $k \in o(n)$ . Esto está cerca, pero no es un puro. ¿Hay algo que me falte?
Respuesta
¿Demasiados anuncios?
Como usted dice, si $n$ se aproxima al infinito para que $k/n\to 0$ por la aproximación de Stirling $$ k! n^{-k} \binom{n}{k} = (1 + o(1)) (1-\frac{k}{n})^{-(n-k)} e^{-k}. \qquad\ \ \ (*) $$ Entonces, tomando logaritmos y expandiendo en una serie de Taylor con resto se obtiene \begin {eqnarray*} \log\left ((1- \frac kn)^{-(n-k)} e^{-k} \right )&=&-k-(n-k) \log (1- \frac kn) \\ &=& -k + (n-k) \left ( \sum_ {1 \le i \le j} \frac 1i ( \frac kn)^i + O(( \frac kn)^{j+1}) \right ) \\ &=& - \sum_ {1 \le i \le j-1} \frac 1 {i(i+1)} \frac {k^{i+1}}{n^i}+ O( \frac {k^{j+1}}{n^j}) \end {eqnarray*} para cualquier $j\ge 1$ . Exponiendo y sustituyendo esto de nuevo en $(*)$ da, como $n\to\infty$ , $$ \binom{n}{k} = (1 + o(1)) \frac{n^k}{k!} \exp\left(-\sum_{1\le i\le j-1}\frac{1}{i(i+1)} \frac{k^{i+1}}{n^i} \right),\ \ \ \text{where } k=o(n^{j/(j+1)}). $$ La fórmula del trabajo de Erdős-Rényi se obtiene estableciendo $j:=3$ . El exponente ilegible debe ser entonces $3/4$ .
