¿Lo que ' s el límite asintótico de la suma de $\frac 3 2 + \sum_{k=3}^{n} \frac{n!}{k(n-k)!n^k}$?

Question

La suma es:

$$S = 1 + 1/2 + \frac {(n-1)(n-2)} {3n^2} + \frac {(n-1)(n-2)(n-3)} {4n^3} + \ldots + \frac {(n-1)!} {n \times n^{n-1}}$$ $$= \frac 3 2 + \sum_{k=3}^{n} \frac{n!}{k(n-k)!n^k}$$

Podemos tener una asintótica límite inferior de $S$?

Supongo que es $\Omega(\frac 1 2 \log n)$, pero no estoy seguro de cómo conseguirlo. $k$ comienza a partir de 3 porque estoy contando la expectativa de los ciclos en un gráfico. Y menos de 3 nodos podría formar un ciclo. Pero, ya que lo que necesito es un asintótica límite inferior, supongo que donde $k$ comienza en realidad no importa.

Answer 1

Para una completa asintótica a a $o(1)$ I get $$S(n) = \frac{1}{2} \log n + \frac{\gamma + \log 2}{2} + o(1).$$

Su suma $S(n)$ está muy cerca de la suma de $Q(n) = 1 + \frac{n-1}{n} + \frac{(n-1)(n-2)}{n^2} + \cdots = \sum_{k \geq 1} \frac{n^{\underline{k}}}{n^k}$ considera que en el Problema 9.56 en Concreto de las Matemáticas y en otras partes de Knuth del trabajo, así que me he adaptado algunos de los argumentos que allí se encuentran.

Vamos a considerar la suma de $S'(n) = \sum_{k \geq 1} \frac{n^{\underline{k}}}{k n^k} = S(n) - \frac{1}{2n} = S(n) + o(1).$ En la respuesta al Problema 9.56 en Concreto de las Matemáticas , los autores indican que a Stirling aproximación puede ser utilizado para mostrar que si $k \leq n^{1/2+\epsilon}$

$$\frac{n^{\underline{k}}}{k n^k} = e^{-k^2/2n} \left(\frac{1}{k} + \frac{1}{2n} - \frac{2}{3} \frac{k^2}{(2n)^2} + O(n^{-1+4 \epsilon})\right).$$ Entonces, Knuth y Pittel, en "Una Recurrencia Relacionados a los Árboles" (Actas de la AMS 105, apartado 2, 1989, pp 335-349) indicar esto significa que $\frac{n^{\underline{k}}}{k \, n^k}$ es exponencialmente más pequeño al $k \geq n^{1/2+\epsilon}$, por lo que pueden ser reemplazados por otros de manera exponencial pequeño términos $$S'(n) = T_{2n}(-1) + \left(\frac{1}{2n} + O(n^{-1 + 4 \epsilon})\right) T_{2n}(0) - \frac{1}{6n^2} T_{2n}(2),$$ donde $T_n(x) = \sum_{k \geq 1} k^x e^{-k^2/n}$.

Lema 1 en la Knuth y Pittel de papel, a continuación, afirma que si $x > -1$ $$T_n(x) = \frac{1}{2} \Gamma\left(\frac{x+1}{2}\right) n^{(x+1)/2} + O(1).$$ They also mention that a derivation of $$T_n(-1) = \frac{1}{2} \log n + \frac{\gamma}{2} + O(n^{-1})$$ es en Knuth del Arte de la Programación informática, Vol. 3, Ejercicio 5.2.2-4, como parte del análisis de bubblesort.

Poniendo todo esto junto nos da $S(n) = \frac{1}{2} \log (2n) + \frac{\gamma}{2} + o(1) = \frac{1}{2} \log n + \frac{\gamma + \log 2}{2} + o(1).$

Para más información sobre el $Q(n)$ y relacionados con las funciones y sus asymptotics, ver el Arte de La Programación informática, Vol. 1 (3ª ed.), Sección 1.2.11.3.

Answer 2

Cumple con el término $a_k(n) = \frac{1}{k} \prod_{j=1}^{k-1} (1 - j/n)$ $a_k(n) < 1/k$, que $S(n) < 3/2 + \sum_{k=3}^n 1/k \approx \ln(n)$. Por otra parte, tomar cualquier $p$ $0 < p < 1/2$. $k < n^p$ Tenemos $\prod_{j=1}^{k-1} (1 - j/n) > (1 - n^{p-1})^{n^{p}}$, que tiene límite de 1 $n \to \infty$. Así que para cualquier $\epsilon > 0$, si $n$ es suficientemente grande tenemos $$S(n) > \sum_{k=3}^{n^{p}} \frac{1-\epsilon}{k} \approx (1-\epsilon) \ln(n^p) = (1-\epsilon) p \ln(n)