Module combinatorics

Expand description

Combinatorics: Stirling numbers, multinomial coefficients, partition counting. Combinatorial functions: binomial and multinomial coefficients, Stirling, Bell and Catalan numbers, derangements, and integer partitions (counting and enumeration).

Unified API — every function accepts arbitrary-precision integers via impl Into<BigInt>. Returns Option<BigInt> where None means the input doesn’t fit in a machine-sized integer (and thus the computation cannot proceed). For inputs that do fit, the function always returns the exact result — there are no artificial resource limits.

At the CAS expression layer, None causes the node to remain in unevaluated symbolic form (e.g. the user sees stirling2(n, k)), which is the mathematically honest response when computation isn’t feasible.

§Examples

use symplex::combinatorics::{stirling2, stirling1, multinomial, partition_count};
use num_bigint::BigInt;

// Stirling number of the second kind: S(4, 2) = 7
assert_eq!(stirling2(4, 2), Some(BigInt::from(7)));

// Stirling number of the first kind (signed): s(4, 1) = -6
assert_eq!(stirling1(4, 1), Some(BigInt::from(-6)));

// Multinomial coefficient: 6! / (2! * 3! * 1!) = 60
assert_eq!(multinomial(6, &[2, 3, 1]), Some(BigInt::from(60)));

// Number of integer partitions: p(5) = 7
assert_eq!(partition_count(5), Some(BigInt::from(7)));

Structs§

PartitionIter: Lazy iterator over the integer partitions of n in reverse lexicographic order (each partition is a non-increasing Vec<u64>).

Functions§

bell: Bell number Bₙ: the number of set partitions of an n-element set (1, 1, 2, 5, 15, 52, 203, …).
binomial: Binomial coefficient C(n, k) for integer n (any sign) and k ≥ 0.
catalan: Catalan number Cₙ = (2n)! / ((n+1)! n!) (1, 1, 2, 5, 14, 42, …).
derangements: Number of derangements !n (permutations with no fixed point): 1, 0, 1, 2, 9, 44, 265, ….
multinomial: Multinomial coefficient n! / (k₁! · k₂! · … · kₘ!).
npartitions: Alias for partition_count: the number of integer partitions p(n).
partition_count: Number of integer partitions of n.
partitions: All integer partitions of n, lazily, in reverse lexicographic order ([n] first, [1, 1, …, 1] last).
stirling1: Signed Stirling number of the first kind s(n, k).
stirling2: Stirling number of the second kind S(n, k).