lucasの定理の組合せ的証明
はじめに
$\mathrm{lucas}$の定理の組合せ的証明法を思いついたので紹介します。既出、間違いがあるなら教えてほしいです。
$\mathrm{lucas}$の定理の主張
$p$を素数とし、
$n_kn_{k-1}...n_{0}$は$n$の$p$進法表記,$r_kr_{k-1}...r_{0}$は$r$の$p$進法表記とした時
${}_{n}\mathrm{C}_{r}\equiv\displaystyle\prod_{i=0}^{k} {}_{n_i}\mathrm{C}_{r_i}(\mathrm{mod}p)$
が成り立つ
証明
補題1
補題1の主張
数列{$n_i$}が存在していて、$\displaystyle\sum_{i=1}^{m}n_i=N$とする
そこで数列{$r_i$}に対して以下のようにスコア$E$を定める
$$
E=\displaystyle\prod_{i=1}^{m} {} _ {n_i} \mathrm{C} _ {r_i}
$$
以下の条件をすべて満たす数列{$r_i$}すべてにおけるスコア$E$の総和を$S$とした時$S= {} _ {N} \mathrm{C} _ {R}$となる
・$\displaystyle\sum_{i=1}^{m}r_i=R$
・任意の非負整数$i$において$0\leq r_i \leq n_i$
補題1の証明
$N $個の玉から$R$個の玉を取り出す組合せについて考える。これは${}_{N}\mathrm{C}_{R}$通りである。
$N$個の玉を$m $個のグループに分け$\lbrace G_1,G_2,...,G_m\rbrace$とし、グループ$G_t$に含まれている玉の数を$n_t$とする。
この時、$N $個の玉から$R$個の玉を取り出す組合せを、どのグループからいくつの玉を取り出すかで場合分けをして足し合わせることで求めてみる。
グループ$G_t$にある球から取り出す数を$r_t$とすると、スコア$E$はその条件を満たす取り出し方の総数となる。
したがって、考えられるすべての数列{$r_i$}を代入したスコア$E$の総和$S$は、$N $個の玉から$R$個の玉を取り出す組合せに等しい。
補題2
補題2の主張
素数$p$ , $a\leq b\ \ ,\ \ r\lt p\ \ ,\ \ s\lt p \ \ ,\ \ bp+s\leq ap+r$を満たす自然数$a,b$において
${}_{bp+s}\mathrm{C}_{ap+r}\equiv{}_{b}\mathrm{C}_{a}\times{}_{s}\mathrm{C}_{r}(\mathrm{mod}p)$が成り立つ
補題2の証明
補題1より${}_{bp+s}\mathrm{C}_{ap+r}$を以下のようにあらわすことができる。
$E={}_{p}\mathrm{C}_{r_1}\times{}_{p}\mathrm{C}_{r_2}\times...\times{}_{p}\mathrm{C}_{r_b}\times{}_{s}\mathrm{C}_{r_{b+1}}$とした時
以下の条件をすべて満たす数列{$r_i$}をすべて代入した$E$の総和
・$\displaystyle\sum_{i=1}^{m}r_i=ap+r$
・$r_i\leq p \ (1\leq i \leq b)$
・$r_{b+1}\leq s$
ある$i\ (1\leq i \leq b)$において$0 \lt r_i\lt p$ならスコア$E$は$\mathrm{mod}p$で$0$になるため
任意の$(1\leq i \leq b)$を満たす$i$において$r_i=0,p$となるものだけを考える。
これを満たす数列{$r_i$}は${}_{b}\mathrm{C}_{a}$つあり、$r_{b+1}=r$より
$E= {}_{s}\mathrm{C}_{r}$
したがって${}_{bp+s}\mathrm{C}_{ap+r}\equiv{}_{b}\mathrm{C}_{a}\times{}_{s}\mathrm{C}_{r}(\mathrm{mod}p)$
補題2を用いて$\mathrm{lucas}$の定理を証明する
$p$を素数とし、
$n_kn_{k-1}...n_{0}$は$n$の$p$進法表記,$r_kr_{k-1}...r_{0}$は$r$の$p$進法表記とした時
$n=n_kp^k+n_{k-1}p^{k-1}+...+n_1p+n_0$
$r=r_kp^k+r_{k-1}p^{k-1}+...+r_1p+r_0$ と表すことができる
補題2を使うことにより、
${}_{n}\mathrm{C}_{r}={}_{n_kp^k+n_{k-1}p^{k-1}+...+n_1p+n_0}\mathrm{C}_{r_kp^k+r_{k-1}p^{k-1}+...+r_1p+r_0}$
$\ \ \ \ \ \ \equiv {}_{n_kp^{k-1}+n_{k-2}p^{k-1}+...+n_1}\mathrm{C}_{r_kp^{k-1}+r_{k-2}p^{k-1}+...+r_1} \times {}_{n_0}\mathrm{C}_{r_0}$
これを繰り返すことにより$\mathrm{lucas}$の定理を得ることができる
