如何证明二项式系数是2的n次方的渐近大theta？
How to prove binomial coefficient is asymptotic big theta of two to the power n?
我被这个问题困住了。我认为这相当于显示 2m 选择 m 是 4 的 n 次方的大 theta，但仍然很难证明它。
感谢@LutzL 的建议。之前想到了斯特林近似。
您可以使用 Stirlings 公式计算阶乘。
n! = sqrt(2*pi*(n+theta)) * (n/e)^n
其中 theta 介于 0 和 1 之间，并且趋向于 0。
O 部分应该很简单。从 n 中选择 n/2 个元素是从 n 中选择任意组合的特例元素，即为每个 n 个元素决定是否选择它。
Ω部分更难。事实上，plotting 4n / binomial(2 n, n) for moderately large n 我没有看到任何迹象表明这会变平以保持在某个常数以下。直觉上来说，n越大，越特别的是当你从n个元素中随机挑选，恰好恰好选择了n/2 个。随着 n 的增加，该概率应该趋于零，这意味着 2n 应该总是比 n选择n/2。您确定您正确理解了这部分任务吗？
不是——它是 Theta(2^n/sqrt(n))，实际上是 choose(n, n/2) ~ 2^n/sqrt(pi * (n/2)) 作为 n->无穷大)。参见 https://en.wikipedia.org/wiki/Central_binomial_coefficient
我被这个问题困住了。我认为这相当于显示 2m 选择 m 是 4 的 n 次方的大 theta，但仍然很难证明它。
感谢@LutzL 的建议。之前想到了斯特林近似。
您可以使用 Stirlings 公式计算阶乘。
n! = sqrt(2*pi*(n+theta)) * (n/e)^n
其中 theta 介于 0 和 1 之间，并且趋向于 0。
O 部分应该很简单。从 n 中选择 n/2 个元素是从 n 中选择任意组合的特例元素，即为每个 n 个元素决定是否选择它。
Ω部分更难。事实上，plotting 4n / binomial(2 n, n) for moderately large n 我没有看到任何迹象表明这会变平以保持在某个常数以下。直觉上来说，n越大，越特别的是当你从n个元素中随机挑选，恰好恰好选择了n/2 个。随着 n 的增加，该概率应该趋于零，这意味着 2n 应该总是比 n选择n/2。您确定您正确理解了这部分任务吗？
不是——它是 Theta(2^n/sqrt(n))，实际上是 choose(n, n/2) ~ 2^n/sqrt(pi * (n/2)) 作为 n->无穷大)。参见 https://en.wikipedia.org/wiki/Central_binomial_coefficient