haar_lib/math/factorial/
bell.rs

1//! ベル数
2//!
3//! # References
4//! - <https://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E6%95%B0>
5//! - <https://manabitimes.jp/math/892>
6
7use crate::math::factorial::FactorialTable;
8use crate::num::ff::*;
9use std::cmp::min;
10
11/// ベル数
12pub trait BellNumber {
13    /// 計算結果の型
14    type Output;
15    /// ベル数$B(n, k)$を計算する。
16    fn bell_number(&self, n: usize, k: usize) -> Self::Output;
17}
18
19impl<Modulo: FF> BellNumber for FactorialTable<Modulo>
20where
21    Modulo::Element: FFElem + Copy,
22{
23    type Output = Modulo::Element;
24
25    fn bell_number(&self, n: usize, k: usize) -> Self::Output {
26        match n {
27            0 => self.modulo.from_u64(1),
28            _ => {
29                let k = min(n, k);
30                let mut t = vec![self.modulo.from_u64(1); k];
31
32                for i in 1..k {
33                    t[i] = match i % 2 {
34                        0 => t[i - 1] + self.inv_facto(i),
35                        _ => t[i - 1] - self.inv_facto(i),
36                    }
37                }
38
39                (1..=k)
40                    .map(|i| {
41                        t[k - i] * self.modulo.from_u64(i as u64).pow(n as u64) * self.inv_facto(i)
42                    })
43                    .fold(self.modulo.from_u64(0), std::ops::Add::add)
44            }
45        }
46    }
47}
haar_lib/math/factorial/bell.rs

haar_lib/math/factorial/
bell.rs
