Compute Stirling numbers of the second kind

This function computes Stirling numbers of the second kind, $S(n, k)$, which count the number of ways of partitioning n distinct objects in to k non-empty sets.

Stirling2(n, k, exact = FALSE)

S2(n, k, exact = FALSE)

Arguments

n: A vector of one or more non-negative integers
k: A vector of one or more non-negative integers
exact: if TRUE the exact results are returned as big integers of class bigz from the gmp package.

Value

A vector of Stirling numbers of the second kind. They are always computed exactly. By default they are returned as doubles, so they are exact up to $2^{53}$ and correct to about 15 significant digits beyond that. If exact is TRUE they are exact bigz values.

Details

The implementation on this function is a simple recurrence relation which defines $$S(n, k) = kS(n - 1, k), + S(n - 1, k - 1)$$ for $k > 0$ with the inital conditions $S(0, 0) = 1$ and $S(n, 0) = S(0, n) = 0$. If n and k have different lengths then expand.grid is used to construct a vector of (n, k) pairs

References

https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Recurrence_relation

Author

James Curran

Examples


## returns S(6, 3)
Stirling2(6, 3)
#> [1] 90

## returns S(6,1), S(6,2), ..., S(6,6)
S2(6, 1:6)
#> [1]  1 31 90 65 15  1

## returns S(6,1), S(5, 2), S(4, 3)
S2(6:4, 1:3)
#> [1]  1 15  6

## exact = TRUE gives exact values, even when they are very large
S2(100, 50)
#> [1] 4.309832e+101
S2(100, 50, exact = TRUE)
#> Big Integer ('bigz') :
#> [1] 430983237009366340421514301547258695943520289614340613912441741131280319058853783145598261659992013900