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

Question

还有比使用基本公式n！/(N)更好的方法吗？nCr (组合)nCr=(NCr)Cr+ (n-1)C(r-1)？

Answer 1

这个怎么样：nPr = (n−1)Pr + (n−1)P(r−1)⋅r

基本原理: nPr表示从n中选择r元素的方式数，同时注意它们的顺序而不将它们放回。在上面的递归中，我区分了两种情况。或者您不选择n_th元素，在这种情况下，您将从一组(n−1)中选择所有的_r元素。或者您也将选择n_th元素，在这种情况下，您将从一组(n−1)中选择另一个(r−1)元素，并且在选择_n_th元素的顺序上存在_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