java数学中的组合'N选择R'？

Question

Java 库中是否有内置方法可以为任何 N、R 计算“N 选择 R”？

原文由 Aly 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

apache-commons“Math”在 org.apache.commons.math4.util.CombinatoricsUtils 中支持这个

原文由 theomega 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

公式

实际上很容易计算 N choose K 甚至不需要计算阶乘。

我们知道 (N choose K) 的公式是：

     N!
 --------
 (N-K)!K!

因此， (N choose K+1) 的公式为：

        N!                N!                   N!               N!      (N-K)
---------------- = --------------- = -------------------- = -------- x -----
(N-(K+1))!(K+1)!   (N-K-1)! (K+1)!   (N-K)!/(N-K) K!(K+1)   (N-K)!K!   (K+1)

那是：

 (N choose K+1) = (N choose K) * (N-K)/(K+1)

我们也知道 (N choose 0) 是：

  N!
---- = 1
N!0!

So this gives us an easy starting point, and using the formula above, we can find (N choose K) for any K > 0 with K multiplications and K 分裂。

---

简单的帕斯卡三角形

综上所述，我们可以很容易地生成帕斯卡三角形，如下所示：

     for (int n = 0; n < 10; n++) {
        int nCk = 1;
        for (int k = 0; k <= n; k++) {
            System.out.print(nCk + " ");
            nCk = nCk * (n-k) / (k+1);
        }
        System.out.println();
    }

这打印：

 1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

---

BigInteger 版本

应用 BigInteger 的公式很简单：

 static BigInteger binomial(final int N, final int K) {
    BigInteger ret = BigInteger.ONE;
    for (int k = 0; k < K; k++) {
        ret = ret.multiply(BigInteger.valueOf(N-k))
                 .divide(BigInteger.valueOf(k+1));
    }
    return ret;
}

//...
System.out.println(binomial(133, 71));
// prints "555687036928510235891585199545206017600"

根据 Google， 133 选择 71 = 5.55687037 × 10 38 。

---

参考

• 维基百科/二项式系数
• 维基百科/帕斯卡三角形
• 维基百科/组合

原文由 polygenelubricants 发布，翻译遵循 CC BY-SA 2.5 许可协议