Function stirling_numbers::stirling2_ratio_table

pub fn stirling2_ratio_table<T: Num + Clone + MulAssign + From<u32>>(
    n_max: usize
) -> Vec<Vec<T>>

Compute a table of “Stirling ratios”, Stirling numbers divided by the asympotic approximation k^n / k!, which is useful because the ratios are numerically better behaved than the Stirling numbers themselves.
 

Motivation. The utility of these ratios is that their numerical behavior is better than the Stirling numbers themselves: the table can be computed up to much larger n without turning to junk. The ratios also work more naturally with some applications e.g. in p_at_most_m_distinct_in_sample_of_x_from_n.

We don’t have a reference for this material.

Method. The ratio SR(n,k) := S(n,k) / ( k^n / k! ) with the special case definition SR(0,0) = 1 satisfies the recurrence relation:

SR(n,0) = delta(0,n)
SR(n,n) = n! / n^n
SR(n,k) = SR(n-1,k) + SR(n-1,k-1) * ((k-1)/k))^(n-1)
          if 1 ≤ k < n.

Computational complexity. O(n_max^2) assuming that T is a fixed-size type like f64.

Testing and accuracy. Tested using f64. For n_max = 722, the values are accurate to 12 digits; this fails for 723.