Stirling: Eulerian and Stirling Numbers of First and Second Kind

In gmp: Multiple Precision Arithmetic

Eulerian and Stirling Numbers of First and Second Kind

Description

Compute Eulerian numbers and Stirling numbers of the first and second kind, possibly vectorized for all k “at once”.

Usage

Stirling1(n, k)
Stirling2(n, k, method = c("lookup.or.store", "direct"))
Eulerian (n, k, method = c("lookup.or.store", "direct"))

Stirling1.all(n)
Stirling2.all(n)
Eulerian.all (n)

Arguments

n	positive integer (0 is allowed for Eulerian()).
k	integer in 0:n.
method	for Eulerian() and Stirling2(), string specifying the method to be used. "direct" uses the explicit formula (which may suffer from some cancelation for “large” n).

Details

Eulerian numbers:
A(n,k) = the number of permutations of 1,2,...,n with exactly k ascents (or exactly k descents).

Stirling numbers of the first kind:
s(n,k) = (-1)^{n-k} times the number of permutations of 1,2,...,n with exactly k cycles.

Stirling numbers of the second kind:
S^{(k)}_n is the number of ways of partitioning a set of n elements into k non-empty subsets.

Value

A(n,k), s(n,k) or S(n,k) = S^{(k)}_n, respectively.

Eulerian.all(n) is the same as sapply(0:(n-1), Eulerian, n=n) (for n > 0),
Stirling1.all(n) is the same as sapply(1:n, Stirling1, n=n), and
Stirling2.all(n) is the same as sapply(1:n, Stirling2, n=n), but more efficient.

Note

For typical double precision arithmetic,
Eulerian*(n, *) overflow (to Inf) for n \ge 172,
Stirling1*(n, *) overflow (to \pmInf) for n \ge 171, and
Stirling2*(n, *) overflow (to Inf) for n \ge 220.

Author(s)

Martin Maechler ("direct": May 1992)

References

Eulerians:

NIST Digital Library of Mathematical Functions, 26.14: https://dlmf.nist.gov/26.14

Stirling numbers:

Abramowitz and Stegun 24,1,4 (p. 824-5 ; Table 24.4, p.835); Closed Form : p.824 "C."

NIST Digital Library of Mathematical Functions, 26.8: https://dlmf.nist.gov/26.8

See Also

chooseZ for the binomial coefficients.

Examples

Stirling1(7,2)
Stirling2(7,3)

stopifnot(
 Stirling1.all(9) == c(40320, -109584, 118124, -67284, 22449, -4536, 546, -36, 1)
 ,
 Stirling2.all(9) == c(1, 255, 3025, 7770, 6951, 2646, 462, 36, 1)
 ,
 Eulerian.all(7) == c(1, 120, 1191, 2416, 1191, 120, 1)
)

gmp documentation built on Sept. 11, 2024, 7:37 p.m.