how can prove $\binom{n}{n/2} = \Omega (\frac{2^{n}}{n})$ ? it s for algorithms coures .
sorry for bad english :D
how can prove $\binom{n}{n/2} = \Omega (\frac{2^{n}}{n})$ ? it s for algorithms coures .
sorry for bad english :D
Hint: What is the sum of $\binom{n}{k}$ for all $k$? And which is the greatest of these?
An alternative is to use Stirling's formula to get $\binom{n}{n/2} = \Theta\left(\frac{2^n}{\sqrt{n}}\right).$
You can also get the same result from the Central Limit Theorem, since $\frac{\binom{n}{n/2}}{2^n} = \mathrm{Pr}[\mathrm{Bin(n,\frac{1}{2})}=\frac{n}{2}].$
Regard all the binomial coefficients $\binom n0, \binom n1, \dots, \binom nn$.
How many are there?
What is their sum?
What is the maximal element in this list?
What is the minimal size of a maximal element in a list with A elements and sum S?