complexity of $\ {n \choose n/3}$

Question

I know that the complexity of this combination $\ {n \choose n/3}$ is of $\theta(n^{n/3})$ , but I'm in need of help proving it.

Answer 1

I assume that by "complexity" you mean the value.

In

Show that $r_k^n/n \le \binom{kn}{n} < r_k^n$ where $r_k = \dfrac{k^k}{(k-1)^{k-1}}$

I showed that for $n \ge 2$, $$\dfrac{r_k^n}{n+1} \le \binom{kn}{n} < r_k^n \text{ where } r_k = \frac{k^k}{(k-1)^{k-1}} $$ and, if you use Stirling's formula, you get $$\binom{kn}{n} \approx \sqrt{\dfrac{k}{2\pi n(k-1)}}r_k^{n} $$

Putting $k=3$ and $n = n/3$, this becomes for $n \ge 2$,

$\dfrac{r_3^{n/3}}{n/3+1} \le \binom{n}{n/3} < r_3^{n/3}$ where $r_3 = \frac{3^3}{2^2} = \frac{27}{4} $

and $\binom{n}{n/3} \approx \sqrt{\dfrac{9}{4\pi n}}r_3^{n/3} $.