math - 如何有效地找到nPr(排列)？

有没有比使用基本公式n！/（n-r）更好的方法！就像我们对nCr（组合）拥有nCr =（n-1）Cr +（n-1）C（r-1）吗？

最佳答案

怎么样：nPr =（n-1）Pr +（n-1）P（r-1）⋅r

原理：nPr表示从n中选择r个元素，同时注意其顺序而不放回它们的方式。在以上递归中，我区分了两种情况。要么不选择第n个元素，在这种情况下，您将从一组（n-1）中选择所有r个元素。否则，您也将选择第n个元素，在这种情况下，您将从（n-1）个集合中选择其他（r-1）个元素，那么在顺序的哪一点上有r种可能性选择了第n个元素。

除此之外，还请注意，您可以仅考虑差值而乘积来避免两个阶乘：

  n
─┬──┬─       n!
 │  │   i = ──── = (n−r+1)⋅(n−r+2)⋅…⋅(n−1)⋅n = nPr
 │  │        r!
i=n−r+1

这导致了另一个递归公式：nPr =（n-1）P（r-1）⋅n