Class Stirling

java.lang.Object
org.apache.commons.numbers.combinatorics.Stirling
public final class Stirling extends Object
Computation of Stirling numbers.
Since:
1.2

  • Field Details

    • S1_ERROR_FORMAT

      private static final String S1_ERROR_FORMAT
      Stirling S1 error message.
      See Also:

    • S2_ERROR_FORMAT

      private static final String S2_ERROR_FORMAT
      Stirling S2 error message.
      See Also:

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

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

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

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

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

  • Constructor Details

    • Stirling

      private Stirling()
      Private constructor.

  • Method Details

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

    • checkN

      private static void checkN(int n, int k, int threshold, String msgFormat)
      Check n <= threshold, or else throw an ArithmeticException.
      Parameters:
      n - N
      k - K
      threshold - Threshold for n
      msgFormat - Error message format
      Throws:
      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