Class BinomialCoefficient

java.lang.Object
org.apache.commons.numbers.combinatorics.BinomialCoefficient
public final class BinomialCoefficient extends 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 final int
    LIMIT_N
    The maximum n that can be computed without overflow of a long for any m.
    private static final int
    MAX_M
    The maximum m that can be computed without overflow of a long.
    private static final 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

    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 Object

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

  • Field Details

    • 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:

    • 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:

    • 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:

  • Constructor Details

    • BinomialCoefficient

      private BinomialCoefficient()
      Private constructor.

  • Method Details

    • 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:
      IllegalArgumentException - if n < 0, k < 0 or k > n.
      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:
      IllegalArgumentException - if n < 0.
      IllegalArgumentException - if k > n or k < 0.