Compute Log Stirling Numbers (First Kind, Unsigned)

Computes the logarithm of unsigned Stirling numbers of the first kind \(|s(J,k)|\) for all \(J\) from 0 to J_max and \(k\) from 0 to \(J\). Uses log-space recursion to prevent numerical overflow.

Usage

compute_log_stirling(J_max)

Arguments

J_max

Maximum J value (non-negative integer, at most 500).

Value

A lower triangular matrix of dimension (J_max+1) x (J_max+1). Entry [J+1, k+1] contains \(\log|s(J,k)|\) (using R's 1-based indexing). Invalid entries (k > J or k < 1 when J >= 1) contain -Inf.

Details

The unsigned Stirling numbers of the first kind \(|s(J,k)|\) count the number of permutations of \(J\) elements into exactly \(k\) disjoint cycles.

Uses the log-space recurrence relation: $$L_{J,k} = \text{logsumexp}(L_{J-1,k-1}, \log(J-1) + L_{J-1,k})$$

where \(L_{J,k} = \log|s(J,k)|\).

Boundary conditions:

• \(|s(0,0)| = 1\) \(\rightarrow\) L[1,1] = 0

• \(|s(J,0)| = 0\) for \(J \geq 1\) \(\rightarrow\) L[J+1,1] = -Inf

• \(|s(J,J)| = 1\) for all \(J\) \(\rightarrow\) L[J+1,J+1] = 0

Complexity: O(J_max^2) time and space. The largest table computed in a session is cached internally and reused for all smaller requests. The bounded cache retains at most one matrix.

References

Antoniak, C. E. (1974). Mixtures of Dirichlet Processes with Applications to Bayesian Nonparametric Problems. The Annals of Statistics, 2(6), 1152-1174.

See also

get_log_stirling for safe accessor with bounds checking

Examples

# Compute Stirling numbers up to J=10
logS <- compute_log_stirling(10)

# Access |s(4,2)| = 11
exp(logS[5, 3])
#> [1] 11

# Access |s(5,3)| = 35
exp(logS[6, 4])
#> [1] 35