Is it a valid to say $$ {n \choose k} = \Theta \left( n^k \right) $$ for any $n$ and $k$? If so, how to prove it?
Note: $k$ is not a function of $n$.
Note: Observed it here (page 5): http://www.cs.berkeley.edu/~sinclair/cs271/n6.pdf
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Only as long as $k$ is a constant which does not depend on $n$ -- otherwise, it could be false. $\endgroup$– Clement C.May 3, 2015 at 23:46
-
$\begingroup$ Thanks. Let's assume that it is fixed. I added to the question. Could you give hints on the proof? $\endgroup$– DanielMay 3, 2015 at 23:47
-
5$\begingroup$ It is quite easy to show that for fixed $k$, we have $\lim_{n\to\infty}\frac{\binom{n}{k}}{n^k}=\frac{1}{k!}$. $\endgroup$– André NicolasMay 3, 2015 at 23:53
-
$\begingroup$ At first I was wondering what the capital omega function was, and then I facepalmed when I realized from the answers that it was "Big Oh" notation from CS. Then I double facepalmed as if coming across Homer's Odyssey in Ελληνική and then discovering "oh, this is a Greek translation of the original English poem." $\endgroup$– SO_fix_the_vote_sorting_bugFeb 13, 2022 at 9:27
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
You have that $$ \binom{n}{k} = \frac{n!}{(n-k)!k!} = \frac{1}{k!}\frac{n!}{(n-k)!} = \frac{1}{k!}\left(n(n-1)(n-2)\dots(n-k+1)\right). $$ As far as the $\Theta(\cdot)$ notation is concerned, $k$ is a constant, so $\frac{1}{k!}=\Theta(1)$, and $$ \left(n(n-1)(n-2)\dots(n-k+1)\right) = n^k\cdot\left(1\left(1-\frac1n\right)\left(1-\frac2n\right)\dots\left(1-\frac kn\right)\right) $$ and as $k$ is fixed,, $$ \left(1\left(1-\frac1n\right)\left(1-\frac2n\right)\dots\left(1-\frac kn\right)\right) \xrightarrow[n\to\infty]{} 1 $$ so that indeed $$ \binom{n}{k} = \Theta(n^k) $$
answered May 3, 2015 at 23:54
-
$\begingroup$ But is $n \choose n/2$ $ \sim n^{n/2} \sim \exp(n/2 \log n)$ polynomial? $\endgroup$ Mar 19 at 17:07
-
1$\begingroup$ @PeterLeopold The approximation only holds for constant $k$, and breaks for $k=k(n)$ (as in your example). For instance, $\binom{n}{n/2} = \Theta(2^{n/2}/\sqrt{n})$. (There are various proofs of this, some using Sitrling's approximation, some others using a probabilistic interpretation.) $\endgroup$ Mar 19 at 20:34
$\begingroup$
$\endgroup$
1
We can even make a stronger statement that $${n \choose k} = O\left (\left( \frac{e \cdot n}{k} \right)^k \right)$$ For the proof, see this.
-
$\begingroup$ I would mention that this is especially true for k > 2. $\endgroup$ Feb 13, 2022 at 9:32