Package org.apache.commons.numbers.combinatorics

Class BinomialCoefficient

  • public final class BinomialCoefficient
extends java.lang.Object
    Representation of the binomial coefficient. It is "n choose k", the number of k-element subsets that can be selected from an n-element set.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static int LIMIT_N
      The maximum n that can be computed without overflow of a long for any m.
      private static int MAX_M
      The maximum m that can be computed without overflow of a long.
      private static int SMALL_N
      The maximum n that can be computed without intermediate overflow for any m.

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private BinomialCoefficient()
      Private constructor.

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) static int checkBinomial​(int n, int k)
      Check binomial preconditions.
      static long value​(int n, int k)
      Computes the binomial coefficient.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • MAX_M

        private static final int MAX_M
        The maximum m that can be computed without overflow of a long. C(68, 34) > 2^63.
        See Also:
        Constant Field Values

      • SMALL_N

        private static final int SMALL_N
        The maximum n that can be computed without intermediate overflow for any m. C(61, 30) * 30 < 2^63.
        See Also:
        Constant Field Values

      • LIMIT_N

        private static final int LIMIT_N
        The maximum n that can be computed without overflow of a long for any m. C(66, 33) < 2^63.
        See Also:
        Constant Field Values

    • Constructor Detail

      • BinomialCoefficient

        private BinomialCoefficient()
        Private constructor.

    • Method Detail

      • value

        public static long value​(int n,
                         int k)
        Computes the binomial coefficient.

        The largest value of n for which all coefficients can fit into a long is 66. Larger n may result in an ArithmeticException depending on the value of k.

        Any min(k, n - k) >= 34 cannot fit into a long and will result in an ArithmeticException.

        Parameters:
        n - Size of the set.
        k - Size of the subsets to be counted.
        Returns:
        n choose k.
        Throws:
        java.lang.IllegalArgumentException - if n < 0, k < 0 or k > n.
        java.lang.ArithmeticException - if the result is too large to be represented by a long.

      • checkBinomial

        static int checkBinomial​(int n,
                         int k)
        Check binomial preconditions.

        For convenience in implementations this returns the smaller of k or n - k allowing symmetry to be exploited in computing the binomial coefficient.

        Parameters:
        n - Size of the set.
        k - Size of the subsets to be counted.
        Returns:
        min(k, n - k)
        Throws:
        java.lang.IllegalArgumentException - if n < 0.
        java.lang.IllegalArgumentException - if k > n or k < 0.