Become an expert in R — Interactive courses, Cheat Sheets, certificates and more!
Get Started for Free

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)

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(n,k) 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), 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 ≥ 172,
Stirling1*(n, *) overflow (to +/-Inf) for n ≥ 171, and
Stirling2*(n, *) overflow (to Inf) for n ≥ 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

Multiple Precision Arithmetic

v0.6-2
GPL (>= 2)
Authors
Antoine Lucas, Immanuel Scholz, Rainer Boehme <rb-gmp@reflex-studio.de>, Sylvain Jasson <Sylvain.Jasson@inrae.fr>, Martin Maechler <maechler@stat.math.ethz.ch>
Initial release
2021-01-07

We don't support your browser anymore

Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.