Lucas Correspondence Theorem と Sierpinski Triangle

この記事のコメントで、kikx さんに教わった Lucas Correspondence Theorem (以下 LCT) と Seirpinski Triangle の関係について、せっかく勉強したのでまとめておく。
LCT は、ここにあるとおり、2 つの数 r と k を素数 p 進数で表したとき、

r = rm*p^m + ... r1*p + r0
k = km*p^m + ... k1*p + k0

以下の関係が成り立つというもの。

r C k ≡ Π(i=0〜m) ri C ki   mod p
     r C k は、r 個から k 個を抽出する組み合わせの数。2 項係数。
     Π は総積

例を見てみよう。7 進数で、10 C 2 と 10 C 4 を見てみる。

10 C 2 = 10*9/2*1         =  45 ≡ 3 mod 7
10 C 4 = 10*9*8*7/4*3*2*1 = 210 ≡ 0 mod 7

これが、LCT の左辺。右辺は、10、2、4 は 7 進数でそれぞれ、13、02、04 なので、

(1 C 0) * (3 C 2) = 1 * 3*2/2*1 = 1 * 3 = 3 ≡ 3 mod 7
(1 C 0) * (3 C 4) = 1 * 0               = 0 ≡ 0 mod 7

となり、左辺と一致した。ここで、私のような数学不慣れな者に関して、ちょっと注意。

n C m は、m > n の時は 0
n C 0 は、1              # これは、高校数学とかでも習ったと思う
0 C 0 は、1              # n C 0 の特別な場合

1 番目、3 番目は今までお目にかかったことが無いが、2 項係数の自然な拡張ということのようだ。意味的にも、3 個の物から、4 個の物を選ぶ組み合わせの数は、確かに無い( 0 )な。
さて、Sierpinski Triangle との関係を見るときには、p として 2、つまり、2 進数の世界を考える。ある 2 つの 2 進数、r と k を考える。r と k の各桁は、当然、1 か 0 だ。そうすると、LCT の右辺は、どんな場合も、以下の 4 つの数値のどれかの積となる。

r   k
0 C 0 = 1
0 C 1 = 0
1 C 0 = 1
1 C 1 = 1

LCT の右辺は積なので、結局、0 が入れば 0 になり、入らなければ、1 になる。0 は、0 C 1 の時だけなので、r C k の r のある桁が 0 で、対応する k の桁が 1 である場合限りに、LCT の右辺が 0 になるということだ。ここで、r の 2 の補数 ~r を考えると、~r C k は、

~r   k
 1 C 0 = 1
 1 C 1 = 0
 0 C 0 = 1
 0 C 1 = 1

となり、つまり、~r と k のある桁がともに 1 の時、LCT の右辺は 0 になる。これは、右辺の値を反転してやれば、まさに、bitwise AND だ。つまり、まとめると、LCT の右辺は、mod 2 で考えるとき、

r C k ≡ ! (~r & k) mod 2

となる。
以上より、LCT を介して、n C k mod 2 つまり、Pascal Triangle の偶数/奇数をそれぞれ、0/1 にしたもの、つまり、Sierpinski Triangle は、AND(NOT(n),k) で表せることが分かる。