$\frac{n!}{\frac{n}{2}!(n-\frac{n}{2})!} \in O(n^{34})$?

Question

$\frac{n!}{\frac{n}{2}!(n-\frac{n}{2})!} \in O(n^{34})$?

In Mathematica I have:

((x!) / ((x/2)!*(x-(x/2))! ) ) / (x^34) 

x -> inf

Mathematica return:

$lim_{x->infinity} \frac{x!}{((\frac{x}{2}! (x-\frac{x}{2})!) x^{34} )} = 0$

This is true?

Answer 1

Assume $n$ is even (to avoid annoying considering about the factorial of a non-inter), you have $$\binom{n}{\frac{n}{2}} = \frac{n!}{\frac{n}{2}!^2} \operatorname*{\sim}_{n\to\infty} \sqrt{\frac{2}{\pi}}\frac{2^n}{\sqrt{n}} $$ which you can obtain via Stirling's approximation (applied to the three factorials).

In particular, this means $$\binom{n}{\frac{n}{2}} = \frac{n!}{\frac{n}{2}!^2} = 2^{n-o(1)} $$ so no, this is not $O(n^{34})$. (It grows faster than any fixed polynomial in $n$.)

Answer 2

Stirling's approximation says that for large $n$, $n!$ behaves like $(n/e)^n$. As a result ${2n \choose n}$ behaves like $(2n/e)^{2n}/(n/e)^{2n}=2^{2n}$ which is exponential and in particular superpolynomial.

Answer 3

Here's a direct argument for superpolynomial growth without using anything like Stirling. Your expression (in the case $n = 2k$ is even) is just

$$\frac{(2k)!}{(k!)^2} = \frac{2k \cdot (2k - 1) \cdot(2k - 2) \cdots (k + 1) }{k \cdot (k - 1) \cdot (k - 2) \cdots 1}$$

Match each term in the numerator with its corresponding term in the denominator. The term in the numerator is at least twice as large as the term in the denominator, so the $k$ terms now give us

$$\frac{(2k)!}{(k!)^2} \ge 2^k.$$