Es $f(n) = 2^{\frac{1}{2}(n^2-n)} / n!$ ¿acotado polinomialmente?

Question

El numerador cuenta el número de matrices de adyacencia diferentes. Creo que la aproximación de Sterlings ayuda a responder mi pregunta, pero no consigo derivar la respuesta. Entonces, ¿existe una función polinómica $g(x)$ tal que $$f(x) \leq g(x)$$

Answer 1

No está acotado polinomialmente. Para $n \geqslant 3$ tenemos $\frac12(n^2-n) \geqslant \frac13 n^2$ Así que

$$\frac{2^{\frac12(n^2-n)}}{n!} > \frac{2^{\frac13 n^2}}{n^n} = \left(\frac{2^{n/3}}{n}\right)^n.$$

$2^{n/3}$ tiene un crecimiento exponencial, por lo que en conjunto tenemos un crecimiento superexponencial.