haar_lib/math/
bell_number_table.rs

1//! ベル数$B(0, 0), \dots, B(n, n)$
2//!
3//! # References
4//! - <https://manabitimes.jp/math/892>
5#![allow(clippy::needless_range_loop)]
6
7use crate::num::ff::*;
8
9/// ベル数$B(0, 0), \dots, B(n, n)$を求める。
10pub fn bell_number_table<Modulo: FF>(n: usize, modulo: Modulo) -> Vec<Vec<Modulo::Element>>
11where
12    Modulo::Element: FFElem + Copy,
13{
14    let mut ret = vec![vec![modulo.from_u64(0); n + 1]; n + 1];
15    ret[0][0] = modulo.from_u64(1);
16
17    for i in 1..=n {
18        ret[i][1] = modulo.from_u64(1);
19        ret[i][i] = modulo.from_u64(1);
20    }
21
22    for i in 3..=n {
23        for j in 2..i {
24            ret[i][j] = ret[i - 1][j - 1] + modulo.from_u64(j as u64) * ret[i - 1][j];
25        }
26    }
27
28    for i in 0..=n {
29        for j in 1..=n {
30            let t = ret[i][j - 1];
31            ret[i][j] += t;
32        }
33    }
34
35    ret
36}