4

lucasの定理の組合せ的証明

297
0

はじめに

lucasの定理の組合せ的証明法を思いついたので紹介します。既出、間違いがあるなら教えてほしいです。

lucasの定理の主張

pを素数とし、
nknk1...n0np進法表記,rkrk1...r0rp進法表記とした時

nCri=0kniCri(modp)

が成り立つ

証明

補題1

補題1の主張

数列{ni}が存在していて、i=1mni=Nとする
そこで数列{ri}に対して以下のようにスコアEを定める
E=i=1mniCri
以下の条件をすべて満たす数列{ri}すべてにおけるスコアEの総和をSとした時S=NCRとなる
i=1mri=R
・任意の非負整数iにおいて0rini

補題1の証明

N個の玉からR個の玉を取り出す組合せについて考える。これはNCR通りである。

N個の玉をm個のグループに分け{G1,G2,...,Gm}とし、グループGtに含まれている玉の数をntとする。

この時、N個の玉からR個の玉を取り出す組合せを、どのグループからいくつの玉を取り出すかで場合分けをして足し合わせることで求めてみる。
グループGtにある球から取り出す数をrtとすると、スコアEはその条件を満たす取り出し方の総数となる。

したがって、考えられるすべての数列{ri}を代入したスコアEの総和Sは、N個の玉からR個の玉を取り出す組合せに等しい。

補題2

補題2の主張

素数p , ab  ,  r<p  ,  s<p  ,  bp+sap+rを満たす自然数a,bにおいて

bp+sCap+rbCa×sCr(modp)が成り立つ

補題2の証明

補題1よりbp+sCap+rを以下のようにあらわすことができる。

E=pCr1×pCr2×...×pCrb×sCrb+1とした時
以下の条件をすべて満たす数列{ri}をすべて代入したEの総和
i=1mri=ap+r
rip (1ib)
rb+1s

あるi (1ib)において0<ri<pならスコアEmodp0になるため
任意の(1ib)を満たすiにおいてri=0,pとなるものだけを考える。
これを満たす数列{ri}はbCaつあり、rb+1=rより
E=sCr

したがってbp+sCap+rbCa×sCr(modp)

補題2を用いてlucasの定理を証明する

pを素数とし、
nknk1...n0np進法表記,rkrk1...r0rp進法表記とした時
n=nkpk+nk1pk1+...+n1p+n0
r=rkpk+rk1pk1+...+r1p+r0 と表すことができる

補題2を使うことにより、

nCr=nkpk+nk1pk1+...+n1p+n0Crkpk+rk1pk1+...+r1p+r0
      nkpk1+nk2pk1+...+n1Crkpk1+rk2pk1+...+r1×n0Cr0
これを繰り返すことによりlucasの定理を得ることができる

参考文献

https://manabitimes.jp/math/1324

投稿日:20241231
更新日:130
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

OMC水 ScienceTokyo工学院志望

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. lucasの定理の主張
  3. 証明
  4. 補題1
  5. 補題2
  6. 補題2を用いてlucasの定理を証明する
  7. 参考文献