Skip to main content

stirling2

Function stirling2 

Source
pub fn stirling2<T: Stirling2Output>(n: u32, k: u32) -> T
Expand description

Stirling number of the second kind $S(n,k)$

Stirling numbers of the second kind count the number of ways to partition a set with $n$ elements into $k$ non-empty subsets.

For an unsigned integer return type T, this is a pure rust translation of scipy.special.stirling2(n, k, exact=True).

For T = f64, this corresponds to scipy.special.stirling2(n, k, exact=False), which uses dynamic programming for $n \le 219$ ($n \le 50$ in SciPy), and else the asymptotic approximation of Temme [1] (relative error $\sim 10^{-6}$, worse for $k$ close to $n$).

[1] N. M. Temme, “Asymptotic estimates of Stirling numbers”, Studies in Applied Mathematics, 89(3):233-243, 1993.

§Examples

use xsf::stirling2;

assert_eq!(stirling2::<u64>(10, 3), 9_330);
assert_eq!(stirling2::<u64>(10, 0), 0);
assert_eq!(stirling2::<u64>(9, 3), 3_025);

// won't fit in u64
assert_eq!(stirling2::<u128>(42, 4), 805_932_309_912_663_709_372_025);

// won't fit in u128
assert_eq!(stirling2::<f64>(50, 10), 2.615_471_651_586_288e43);

§Types

  • T (required): unsigned integer or f64 return type

§See also

  • comb: $k$-combinations of $n$ things, $_nC_k$
  • perm: $k$-permutations of $n$ things, $_nP_k$

§Panics

  • For an integer T, this function will panic if the result does not fit in type T.