math - 如何有效地找到 nPr（排列）？

Question

有比使用基本公式 n!/(nr)! 更好的方法吗？就像我们对 nCr(combinations) nCr = (nl)Cr + (n-1)C(r-1) 一样？

Answer 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