Prueba $\frac{1}{(\frac{n}{3})!}=2^{-\Omega(n \log n)}$

Question

Esto lo vi en Wegener(2003), Métodos para el análisis de algoritmos evolutivos como límite superior de la probabilidad.

Tras aplicar la aproximación de Stirling a $(\frac{n}{3})!$ Sigo recibiendo algo como $O(n^{-n+ \epsilon})$ . El documento no ofrece ningún detalle de derivación adicional, así que me pregunto si alguien1 podría ayudarme con esto.

Answer 1

Podemos, por supuesto, utilizar la aproximación de Stirling, pero dado que la afirmación es bastante floja, podemos salirnos con un límite aún más elemental; a saber, $k! \geq k^{k/2}$ . Usando esto, $$ \Big(\frac{n}{3} \Big)! \geq \Big(\frac{n}{3} \Big)^{n/6} = n^{n/12} \Big(\frac{n}{9} \Big)^{n/12} \geq n^{n/12} = \exp\left(\frac{1}{12} n \log n \right), $$ para $n \geq 9$ . Obtenemos la afirmación tomando recíprocos.