Package org.apache.commons.numbers.combinatorics

Class Stirling

  • public final class Stirling
extends java.lang.Object
    Computation of Stirling numbers.
    Since:
    1.2

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private static class  Stirling.StirlingS1Cache
      Precomputed Stirling numbers of the first kind.
      private static class  Stirling.StirlingS2Cache
      Precomputed Stirling numbers of the second kind.

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private Stirling()
      Private constructor.

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      private static void checkArguments​(int n, int k)
      Check 0 <= k <= n.
      private static void checkN​(int n, int k, int threshold, java.lang.String msgFormat)
      Check n <= threshold, or else throw an ArithmeticException.
      private static long productOver4​(long a, long b)
      Return a*b/4 without intermediate overflow.
      static long stirlingS1​(int n, int k)
      Returns the signed Stirling number of the first kind, "s(n,k)".
      static long stirlingS2​(int n, int k)
      Returns the Stirling number of the second kind, "S(n,k)", the number of ways of partitioning an n-element set into k non-empty subsets.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • S1_ERROR_FORMAT

        private static final java.lang.String S1_ERROR_FORMAT
        Stirling S1 error message.
        See Also:
        Constant Field Values

      • S2_ERROR_FORMAT

        private static final java.lang.String S2_ERROR_FORMAT
        Stirling S2 error message.
        See Also:
        Constant Field Values

      • S1_OVERFLOW_K_EQUALS_1

        private static final int S1_OVERFLOW_K_EQUALS_1
        Overflow threshold for n when computing s(n, 1).
        See Also:
        Constant Field Values

      • S1_OVERFLOW_K_EQUALS_NM2

        private static final int S1_OVERFLOW_K_EQUALS_NM2
        Overflow threshold for n when computing s(n, n-2).
        See Also:
        Constant Field Values

      • S1_OVERFLOW_K_EQUALS_NM3

        private static final int S1_OVERFLOW_K_EQUALS_NM3
        Overflow threshold for n when computing s(n, n-3).
        See Also:
        Constant Field Values

      • S2_OVERFLOW_K_EQUALS_NM2

        private static final int S2_OVERFLOW_K_EQUALS_NM2
        Overflow threshold for n when computing S(n, n-2).
        See Also:
        Constant Field Values

      • S2_OVERFLOW_K_EQUALS_NM3

        private static final int S2_OVERFLOW_K_EQUALS_NM3
        Overflow threshold for n when computing S(n, n-3).
        See Also:
        Constant Field Values

    • Constructor Detail

      • Stirling

        private Stirling()
        Private constructor.

    • Method Detail

      • stirlingS1

        public static long stirlingS1​(int n,
                              int k)
        Returns the signed Stirling number of the first kind, "s(n,k)". The number of permutations of n elements which contain exactly k permutation cycles is the nonnegative number: |s(n,k)| = (-1)^(n-k) s(n,k)
        Parameters:
        n - Size of the set
        k - Number of permutation cycles (0 <= k <= n)
        Returns:
        s(n,k)
        Throws:
        java.lang.IllegalArgumentException - if n < 0, k < 0 or k > n.
        java.lang.ArithmeticException - if some overflow happens, typically for n exceeding 20 (s(n,n-1) is handled specifically and does not overflow)

      • stirlingS2

        public static long stirlingS2​(int n,
                              int k)
        Returns the Stirling number of the second kind, "S(n,k)", the number of ways of partitioning an n-element set into k non-empty subsets.
        Parameters:
        n - Size of the set
        k - Number of non-empty subsets (0 <= k <= n)
        Returns:
        S(n,k)
        Throws:
        java.lang.IllegalArgumentException - if n < 0, k < 0 or k > n.
        java.lang.ArithmeticException - if some overflow happens, typically for n exceeding 25 and k between 20 and n-2 (S(n,n-1) is handled specifically and does not overflow)

      • checkArguments

        private static void checkArguments​(int n,
                                   int k)
        Check 0 <= k <= n.
        Parameters:
        n - N
        k - K
        Throws:
        java.lang.IllegalArgumentException - if n < 0, k < 0 or k > n.

      • checkN

        private static void checkN​(int n,
                           int k,
                           int threshold,
                           java.lang.String msgFormat)
        Check n <= threshold, or else throw an ArithmeticException.
        Parameters:
        n - N
        k - K
        threshold - Threshold for n
        msgFormat - Error message format
        Throws:
        java.lang.ArithmeticException - if overflow is expected to happen

      • productOver4

        private static long productOver4​(long a,
                                 long b)
        Return a*b/4 without intermediate overflow. It is assumed that:
        • The coefficients a and b are positive
        • The product (a*b) is an exact multiple of 4
        • The result (a*b/4) is an exact integer that does not overflow a long

        A conditional branch is performed on the odd/even property of b. The branch is predictable if b is typically the same parity.

        Parameters:
        a - Coefficient a
        b - Coefficient b
        Returns:
        a*b/4