自然数/整数 - 関数 - 二項係数 (パスカルの三角形)

\(\def\binom#1#2{\left(\begin{array}{c}#1\\#2\end{array}\right)}\)

概要

パスカルの三角形を用いて \(1 \leq n \leq N, 0 \leq k \leq n\) の範囲全ての \(\binom{n}{k}\) を \(O(N^2)\) で求める.

境界条件

\[\binom{n}{1} = \binom{0}{k} = 1 \text{ for all } n, k\]

漸化式

\[\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \quad (1 \leq k \lt n)\]

から計算する.

実装

二次元配列 binom を返し, \(\left(\begin{array}{c}n\\k\end{array}\right)\) が binom[n][k] に入ってる. 範囲外にはゼロが入ってる.

/// Number - Binomial Coefficient - Pascal's Triangle
use crate::algebra::ring::*;
pub fn pascal_triagle<R: Ring + Copy>(n: usize) -> Vec<Vec<R>> {
    let mut binom = vec![vec![R::zero(); n + 1]; n + 1];
    for i in 1..n + 1 {
        for j in 0..i + 1 {
            binom[i][j] = {
                if i == 1 || j == 0 {
                    R::one()
                } else if j + j > i {
                    binom[i][i - j]
                } else {
                    binom[i - 1][j] + binom[i - 1][j - 1]
                }
            };
        }
    }
    binom
}

#[cfg(test)]
mod test_binom_pascal {
    use crate::num::binom_pascal::*;

    #[test]
    fn test_i64() {
        let pascal = pascal_triagle::<i64>(5);
        assert_eq!(pascal[5][0], 1);
        assert_eq!(pascal[5][1], 5);
        assert_eq!(pascal[5][2], 10);
        assert_eq!(pascal[5][3], 10);
        assert_eq!(pascal[5][4], 5);
        assert_eq!(pascal[5][5], 1);
    }

    #[test]
    fn test_modint() {
        use crate::algebra::modint::*;
        use crate::mint;
        let pascal = pascal_triagle::<ModInt>(5);
        assert_eq!(pascal[5][0], mint!(1));
        assert_eq!(pascal[5][1], mint!(5));
        assert_eq!(pascal[5][2], mint!(10));
        assert_eq!(pascal[5][3], mint!(10));
        assert_eq!(pascal[5][4], mint!(5));
        assert_eq!(pascal[5][5], mint!(1));
    }
}