ただの更新数稼ぎ。

http://d.hatena.ne.jp/plusletool/20130612/p1
ここの(*C)の証明をてきとーに考えてやってみた。
途中までしか書いてないし説明不足のとこあるかもしれないけど気にしなーい。
とりあえず書いた。
続きのが長いのはきっと気のせいですよ?


$r_1>n$または$r_2>n$の場合は両辺ともに0で成立。
$r_1=0$または$r_2=0$の場合も成立することは明らか。
それ以外の場合について考える。

$\Omega=\{a_1,a_2,\cdots,a_n\}$とする。
$\mathfrak{C}_{r_1}(\Omega)\mathfrak{C}_{r_2}(\Omega)$を展開すると$a_{i_1}\cdots a_{i_k}$の項が出てくるが、これについて考える。
$a_{i_1}\cdots a_{i_k} (1\le i_1<\cdots<i_k\le n)$の係数についてだが、$a_{i_1},\cdots,a_{i_k}$はそれぞれ$\mathfrak{C}_{r_1}(\Omega)$か$\mathfrak{C}_{r_2}(\Omega)$、あるいはその両方からくる場合の3通り。
よって、係数は$max\{r_1,r_2\}\le k\le r_1+r_2$の時、
$$\frac{k!}{(k-r_1)!(k-r_2)!(r_1+r_2-k)!}\;\;\;\;\cdots(*)$$となる。
$k$がそれ以外の場合は0なので考えないでよい。
あとはこれが偶数か奇数かを調べ、これが奇数となる条件が$k=r_1\cup r_2$であることを示せばよい。


分子側の$k,\cdots,1$と分母側の$(k-r_1),\cdots,1,(k-r_2),\cdots,1,(r_1+r_2-k),\cdots,1$のそれぞれ$k$個の整数の中にある$2^m$の倍数の数について考える。
$\forall m\in\{1,2,\cdots\}$に対し、必ず分母側の$2^m$の倍数の数が分子側の$2^m$の倍数の数より多くなることはない。
よって、$(*)$が奇数になる条件は、$\forall m\in\{1,2,\cdots\}$に対し分母側分子側ともに$2^m$の倍数の数が同じになること。
すなわち、$\forall m\in\{1,2,\cdots\}$に対し
$$\big[\frac{k-r_1}{2^m}\big]+\big[\frac{k-r_2}{2^m}\big]+\big[\frac{r_1+r_2-k}{2^m}\big]=\big[\frac{k}{2^m}\big]$$となること。
$k_m$、${r_1}_m$、${r_2}_m$をそれぞれ$k$、$r_1$、$r_2$の下位$m$bitとすると、この式は
$$\big[\frac{k_m-{r_1}_m}{2^m}\big]+\big[\frac{k_m-{r_2}_m}{2^m}\big]+\big[\frac{{r_1}_m+{r_2}_m-k_m}{2^m}\big]=0$$と書ける。
$0\le k_m,{r_1}_m,{r_2}_m<2^m$であるので、
$$(\big[\frac{k_m-{r_1}_m}{2^m}\big],\big[\frac{k_m-{r_2}_m}{2^m}\big],\big[\frac{{r_1}_m+{r_2}_m-k_m}{2^m}\big])=(-1,0,1),(0,-1,1),(0,0,0)$$となる。
このうち、$(-1,0,1)$については$k_m<{r_1}_m$、$k_m\ge{r_2}_m$、${r_1}_m+{r_2}_m\ge 2^m+k_m$が必要となるが、${r_1}_m<2^m$よりこれを満たす組$(k_m,{r_1}_m,{r_2}_m)$は存在しない。
$(0,-1,1)$についても同様。
よって、条件は$\forall m\in\{1,2,\cdots\}$に対し
$$\big[\frac{k_m-{r_1}_m}{2^m}\big]=\big[\frac{k_m-{r_2}_m}{2^m}\big]=\big[\frac{{r_1}_m+{r_2}_m-k_m}{2^m}\big]=0\\\iff
\left\{\begin{array}{l}
k_m\ge{r_1}_m\\k_m\ge{r_2}_m\\{r_1}_m+{r_2}_m\ge k_m
\end{array}\right.
\;\;\;\;\cdots(**)$$を満たすこと、となる。

この時、$\forall m\in\{1,2,\cdots\}$に対し$k_m={r_1}_m\cup{r_2}_m$となることを$m$に関する帰納法で示す。
・$m=1$の時、
$k_1$、${r_1}_1$、${r_2}_1$はどれも$0$か$1$のいずれかなので、
$$(**)\iff(k_1,{r_1}_1,{r_2}_1)=(0,0,0),(1,0,1),(1,1,0),(1,1,1)$$となる。
よって、$k_1={r_1}_1\cup{r_2}_1$が成立。
・$m=l\;(l={1,2,\cdots})$の時成立したと仮定する。
$m=l+1$の時、
$$(**)\iff\left\{\begin{array}{l}k_{l+1}\ge{r_1}_{(l+1)}\\k_{l+1}\ge{r_2}_{(l+1)}\\{r_1}_{(l+1)}+{r_2}_{(l+1)}\ge k_{l+1}\end{array}\right.$$であるので、$k_{l+1}$、${r_1}_{(l+1)}$、${r_2}_{(l+1)}$の最上位bitの組として考えられるのは$(0,0,0),(1,0,0),(1,0,1),(1,1,0),(1,1,1)$の5つ。
そのうち(1,0,0)は、仮定より$k_l={r_1}_l\cup{r_2}_l$であることから$k_l\ge{r_1}_l$なので、
$${r_1}_{(l+1)}+{r_2}_{(l+1)}={r_1}_l+{r_2}_l< k_l+2^l=k_{l+1}$$となり不適。
残りの場合全てで$k_{l+1}={r_1}_{(l+1)}\cup{r_2}_{(l+1)}$が成立するので、$m=l+1$の時も成立する。
よって、帰納法により示された。

以上から、$k_m={r_1}_m\cup{r_2}_m$が$\forall m\in\{1,2,\cdots\}$で成立するので、$k,r_1,r_2(<\infty)$で$k=r_1\cup r_2$が成立することが示された。 (Q.E.D.)


面倒なのでここまで。
手元では証明はした。

そんな感じです。
もっといいやり方あるかも。

ついでにMathJax使えるかのテストでしたとさ。
気が向いたら続きも書く、かもしれない。