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

Question

有没有比使用基本公式 n!/(n-r)! 更好的方法？就像我们对 nCr(组合) nCr = (n-l)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 元素/em>.或者您也将选择第 n 个元素，在这种情况下，您将从一组 中选择其他 (r−1) 元素(n−1)，并且在您选择第 n 个元素的顺序中的哪个点有 r 种可能性。

除此之外，还请注意，您可以通过仅取差值的乘积来避免两个阶乘:

  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