algorithm - 如何证明二项式系数是2的n次方的渐近大theta？

Question

我被困在这个问题上了。我认为这相当于证明 2m 选择 m 是 4 的 n 次方的大 theta，但仍然很难证明。

感谢@LutzL 的建议。之前想到了斯特林近似。

Answer 1

O 部分应该很简单。从 n 中选择恰好 n/2 个元素是从 n 元素中选择任意组合的特例，即决定为每个 n em>n个元素是否选择。

Ω 部分更难。事实上，plotting 4ⁿ / binomial(2 n, n) for moderately large n我没有看到任何迹象表明这会变平以保持在某个常数以下。从直觉上讲，n 越大，当您从 n 个元素中随机选择并恰好恰好选择了 n/2 个。随着 n 的增加，该概率应趋于零，这意味着 2ⁿ 的增长速度应始终快于 n 选择 < em>n/2。您确定您正确理解了这部分任务吗？