Lucasの定理

　Lucasの定理というものを知った。大きな数の重複なし組み合わせの値を素数を法として求めるときに使える。

非負整数m, n, および素数pについて以下が成り立つ。

 

ただし、m_i, n_iはそれぞれ以下を満たす。

証明はここが分かりやすい。

この定理を見て思ったのは、ほとんどゼロになるのでは？ということだった。
例えば、p=2の場合を考える。m_i < n_i となるようなiが存在すると右辺が0になってしまう。ということは、すべてのiについてm_i ≥ n_iである場合のみ右辺は非零となる。この確率は10桁の二進数だと、pow(3/4, 10) ~ 0.0563程度である。

本当か？ということで試してみた。

#include <iostream>

using namespace std;

int comb[1024][1024];

int main(int argc, char **argv) {
    
    comb[0][0] = 1;
    for (int i = 1; i < 1024; i++) {
        comb[i][0] = comb[i][i] = 1;
        for (int j = 1; j < i; j++) {
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % 2;
        }
    }

    int total = 0;
    int nonzero = 0;

    for (int i = 0; i < 1024; i++) {
        for (int j = 0; j < 1024; j++) {
            ++total;
            nonzero += comb[i][j];
        }
    }

    cout << 1.*nonzero/total << endl;

    return 0;
}

上のプログラムを実行すると、確かに0.0563と出る。

同様に計算すると、一般にp進数d桁に収まる非負整数m, nでcomb(m, n) % pを計算すると、非零になる割合はpow(1/2 + 1/(2p), d)程度だと考えられる。