Sierpinski triangleワンライナーその２

Sierpinski triangleワンライナー - すぎゃーんメモの続き。
アルゴリズムの意味を自分なりに汲み取って書き換えてみた。

$ perl -le 'print map { ~$n & $_ ? "." : "#" } 0..($n = $_ - 1) for 1..2**pop' 6
#
##
#.#
####
#...#
##..##
#.#.#.#
########
#.......#
##......##
#.#.....#.#
####....####
#...#...#...#
##..##..##..##
#.#.#.#.#.#.#.#
################
#...............#
##..............##
#.#.............#.#
####............####
#...#...........#...#
##..##..........##..##
#.#.#.#.........#.#.#.#
########........########
#.......#.......#.......#
##......##......##......##
#.#.....#.#.....#.#.....#.#
####....####....####....####
#...#...#...#...#...#...#...#
##..##..##..##..##..##..##..##
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
################################
#...............................#
##..............................##
#.#.............................#.#
####............................####
#...#...........................#...#
##..##..........................##..##
#.#.#.#.........................#.#.#.#
########........................########
#.......#.......................#.......#
##......##......................##......##
#.#.....#.#.....................#.#.....#.#
####....####....................####....####
#...#...#...#...................#...#...#...#
##..##..##..##..................##..##..##..##
#.#.#.#.#.#.#.#.................#.#.#.#.#.#.#.#
################................################
#...............#...............#...............#
##..............##..............##..............##
#.#.............#.#.............#.#.............#.#
####............####............####............####
#...#...........#...#...........#...#...........#...#
##..##..........##..##..........##..##..........##..##
#.#.#.#.........#.#.#.#.........#.#.#.#.........#.#.#.#
########........########........########........########
#.......#.......#.......#.......#.......#.......#.......#
##......##......##......##......##......##......##......##
#.#.....#.#.....#.#.....#.#.....#.#.....#.#.....#.#.....#.#
####....####....####....####....####....####....####....####
#...#...#...#...#...#...#...#...#...#...#...#...#...#...#...#
##..##..##..##..##..##..##..##..##..##..##..##..##..##..##..##
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
################################################################

つまり、n段目(一番上の段を0段目とする)において、0..$nのそれぞれの数が"~$n"($nの、ビット反転)と論理積をとったときに真になるか否かで塗り分けをすることでこの図形を得られる。

シェルピンスキーのギャスケットは、パスカルの三角形の奇数or偶数を塗りつぶすことで出現する、という話は知っていた。
パスカルの三角形 - Wikipedia
パスカルの三角形は通常、上の段から見ていって、隣り合う数字の合計が下の段の数字になる、という方法で作られていく。
でもn段目の数というのは組み合わせ(Combination)から算出することもできる。
組合せ (数学) - Wikipedia
n段目の数はCombination(n, m)で計算される。
これが偶数or奇数になる条件を求めることができれば、このアルゴリズムの答えがでるような気がする。

Combination(n, m) % 2 == 0

と

~n & m

が常に等しい、という証明ができればいいのかな？

ていうか組合せ (数学) - Wikipediaの「性質」にそれっぽいことが書いてあった。
$n=2^{p(1)}+2^{p(2)}+...$
$m=2^{q(1)}+2^{q(2)}+...$
というように、 $n$ と $m$ を二進展開したとき、
$\{p(1), p(2), ...\} \supset \{q(1), q(2), ...\}$ であることが ${}_n\mathrm{C}_m$ が奇数であることの必要十分条件になっている。