Stirling {gmp}R Documentation

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 kk “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)=A(n,k) = the number of permutations of 1,2,...,n with exactly kk ascents (or exactly kk descents).

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

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

Value

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

Eulerian.all(n) is the same as sapply(0:(n-1), Eulerian, n=n) (for n>0n > 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 n172n \ge 172,
Stirling1*(n, *) overflow (to ±\pmInf) for n171n \ge 171, and
Stirling2*(n, *) overflow (to Inf) for n220n \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)
)

[Package gmp version 0.7-4 Index]