gmp (version 0.7-5)

Stirling: 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)

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.

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).

Author

Martin Maechler ("direct": May 1992)

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.

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)
)