[(m + n)^m] / m! 能够作为 O([n / m]^m) 的松散上界吗？

Question

在将 [(m + n)^m] / m! 的上限写为 O([n / m]^m) 时，我考虑了 m! = O(m^m)。

- ssarmah

---

我建议关闭此问题，因为它与编程无关，请尝试访问http://cs.stackexchange.com。 - kaya3

虽然我认为这个话题在计算机科学方面是相关的，但它不应该在这里成为离题的内容。 - user202729

Answer 1

正如你所说，m！ 是 o(m^m)。因此，你无法将其替换为 A = (m+n)^m / m！ 以获得上限！相反，你可以使用斯特林公式来获得适当的上限。正如我们所知（参见这里）：

m! = \sqrt{2\pi m} (m/e)^m (1 + O(1/m))

您可以通过将m!替换为(m/e)^m来得到A的上限。因此:

A < (n+m)^m / (m/e)^m = (e*(n+m)/m)^m = (e * (n/m + 1))^m

如果 n > m，我们就知道 (n/m + 1)^m = Theta((n/m)^m)。因此，A \in O(e^m (n/m)^m)

- OmG

Answer 2

它不是。

---

原因： 在表达式((m + n)^m) / m!中，值“m！”是分母。

对于分数，增加分母会使数值变小。例如：数字4大于3。所以，当放在分母中时，1/4比1/3^*小。

对于分数值，为了得到一个宽松的上限，你可以做两件事：

1. 增加分子；和/或者
2. 减少分母。

由于在你的近似中：

• 你让分母变得宽松；因此，
• 实际上你正在增加分母；因此，
• 你正在达到一个更小的分数值；

给你提供一个更紧密的上限，而不是一个更宽松的上限。

---

* 这里是小学数学：将披萨平均分成四份并拿到一片，与将披萨平均分成三份并拿到一大片相比，当只有三个人分享时，你会得到更多的披萨。

- displayName