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

I saw this in Wegener(2003), Methods for the Analysis of Evolutionary Algorithms as a upper bound on the probability.

After applying Stirling approximation to $(\frac{n}{3})!$ I still keep getting something like $O(n^{-n+ \epsilon})$. The paper does not offer any additional derivation details, so I wonder if some1 could help me out with this.

-
Well, it is true that the left hand side is both $n^{-O(n)}$ and $n^{-\Omega(n)}$, if that is your confusion. – Srivatsan Sep 20 '11 at 3:42

We can, of course, use Stirling's approximation, but given that the claim is quite loose, we can get away with an even more elementary bound; namely, $k! \geq k^{k/2}$. Using this, $$\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),$$ for $n \geq 9$. We get the claim by taking reciprocals.
yeah right I forgot this good old $n=e^{\log n}$ transformation, otherwise it's all quite clear. – sigma.z.1980 Sep 20 '11 at 3:58