Class Stirling
java.lang.Object
org.apache.commons.numbers.combinatorics.Stirling
Computation of Stirling numbers.
- Since:
- 1.2
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static final class
Precomputed Stirling numbers of the first kind.private static final class
Precomputed Stirling numbers of the second kind. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final String
Stirling S1 error message.private static final int
Overflow threshold for n when computing s(n, 1).private static final int
Overflow threshold for n when computing s(n, n-2).private static final int
Overflow threshold for n when computing s(n, n-3).private static final String
Stirling S2 error message.private static final int
Overflow threshold for n when computing S(n, n-2).private static final int
Overflow threshold for n when computing S(n, n-3). -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate static void
checkArguments
(int n, int k) Check0 <= k <= n
.private static void
Checkn <= threshold
, or else throw anArithmeticException
.private static long
productOver4
(long a, long b) Returna*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 ann
-element set intok
non-empty subsets.
-
Field Details
-
S1_ERROR_FORMAT
Stirling S1 error message.- See Also:
-
S2_ERROR_FORMAT
Stirling S2 error message.- See Also:
-
S1_OVERFLOW_K_EQUALS_1
private static final int S1_OVERFLOW_K_EQUALS_1Overflow threshold for n when computing s(n, 1).- See Also:
-
S1_OVERFLOW_K_EQUALS_NM2
private static final int S1_OVERFLOW_K_EQUALS_NM2Overflow threshold for n when computing s(n, n-2).- See Also:
-
S1_OVERFLOW_K_EQUALS_NM3
private static final int S1_OVERFLOW_K_EQUALS_NM3Overflow threshold for n when computing s(n, n-3).- See Also:
-
S2_OVERFLOW_K_EQUALS_NM2
private static final int S2_OVERFLOW_K_EQUALS_NM2Overflow threshold for n when computing S(n, n-2).- See Also:
-
S2_OVERFLOW_K_EQUALS_NM3
private static final int S2_OVERFLOW_K_EQUALS_NM3Overflow 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 ofn
elements which contain exactlyk
permutation cycles is the nonnegative number:|s(n,k)| = (-1)^(n-k) s(n,k)
- Parameters:
n
- Size of the setk
- Number of permutation cycles (0 <= k <= n
)- Returns:
s(n,k)
- Throws:
IllegalArgumentException
- ifn < 0
,k < 0
ork > 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 ann
-element set intok
non-empty subsets.- Parameters:
n
- Size of the setk
- Number of non-empty subsets (0 <= k <= n
)- Returns:
S(n,k)
- Throws:
IllegalArgumentException
- ifn < 0
,k < 0
ork > 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) Check0 <= k <= n
.- Parameters:
n
- Nk
- K- Throws:
IllegalArgumentException
- ifn < 0
,k < 0
ork > n
.
-
checkN
Checkn <= threshold
, or else throw anArithmeticException
.- Parameters:
n
- Nk
- Kthreshold
- Threshold forn
msgFormat
- Error message format- Throws:
ArithmeticException
- if overflow is expected to happen
-
productOver4
private static long productOver4(long a, long b) Returna*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 ifb
is typically the same parity.- Parameters:
a
- Coefficient ab
- Coefficient b- Returns:
a*b/4
-