組合せと格子点の多項定理への拡張

【目次】
前ページ：「パスカルの三角形の和公式、組合せと格子点」
【要約】
１．パスカルの三角形の和公式
２．重複組合せと組合せ
３．組合せと格子点
４．格子点の構造
このページ：
５．多項定理と格子点
６．多項係数の分解式
７．べき乗と格子点
８．自然数と格子点
次ページ：「組合せとべき乗の関係式と計算法」
９．格子点を用いた組合せの展開式
１０．格子点を用いたべき乗と組合せの関係式
１１．もう一つ、べき乗と組合せの関係式
１２．べき乗の格子点の構造と計算法
　１２-１．組合せ格子点集合を断面とする計算法
　　　べき乗格子点集合の1／2の対称性
　　　Ｈアルゴリズム
　１２-２．多項定理について
　　　多項定理の効率的な計算法
　１２-３．(ｌ＋1)^nと(ｎ＋1)^lの関係性

前ページの二項定理の議論を、多項定理に拡張した上で、べき（羃）乗や自然数との関係を考察する。さらに、これらの考察を踏まえて、組合せとべき乗の関係式をいくつか紹介し、最後にべき乗の格子点の構造を考察してその計算法を示す。

５．多項定理と格子点

多項定理とは、「１．パスカルの三角形の和公式」で紹介した二項定理、
(ｘ＋ｙ)^ｎ=∑[r:0→n]nＣr(ｘ^r)(ｙ^(n-r))
のｘ＋ｙ部分を多変数に拡張した定理で、
(ｘ1＋ｘ2＋・・・＋ｘn-1＋ｘn)^ｌ＝∑[r1+r2+…rn-1+rn=l]lＴ[r1,r2,…,rn-1,rn](ｘ1^r1)(ｘ2^r2)・・・(ｘn-1^rn-1)(ｘn^rn) ・・・【式８】
ただし、
lＴ[r1,r2,…,rn-1,rn]＝ｌ!／ｒ1!ｒ2!・・・ｒn-1!ｒn!
である。
lＴ[r1,r2,…,rn-1,rn]を多項係数という。

ここで、多項係数lＴ[r1,r2,…,rn-1,rn]は、
ｌ!／ｒ1!ｒ2!・・・ｒn-1!ｒn!＝ｌ!／ｒ1!(ｒ2+・・・+ｒn-1+ｒn)!×(ｒ2+・・・+ｒn-1+ｒn)!／ｒ2!・・・ｒn-1!ｒn!
＝nＣr1×(l-r1)Ｔ[r2,…,rn-1,rn]
つまり、
lＴ[r1,r2,…,rn-1,rn]＝lＣr1×(l-r1)Ｔ[r2,…,rn-1,rn]
と分解できる。
これを多項係数の部分に繰り返すと、
lＴ[r1,r2,…,rn-1,rn]＝lＣr1×(l-r1)Ｃr2×・・・×(l-r1-r2-…-rn-2)Ｃrn-1×(l-r1-r2-…-rn-1)Ｔ[rn]
ここで、(l-r1-r2-…-rn-1)Ｔ[rn]＝rnＴ[rn]＝rn!／rn!＝1なので、
lＴ[r1,r2,…,rn-1,rn]＝lＣr1×(l-r1)Ｃr2×・・・×(l-r1-r2-…-rn-2)Ｃrn-1 ・・・【式９】
となる。
つまり、多項係数は二項係数の積に分解することができる。
r1,r2,…,rn-1,rnの順番を入れ換えても、この操作は同様に行えて、
分解される二項係数の個数はn-1個で一定であることも分かる。

ここで、二項係数n+lＣlは、ｎ次元空間の原点から距離ｌまでにある格子点の数であった、
つまり、
Ｘn,l＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・ｘn-1,ｘn), ０≤∑[i:1→n]ｘi≤ｌ｝
とすると、n(Ｘn,l)＝n+lＣlであるので、【式９】を変形すると、
lＴ[r1,r2,…,rn-1,rn]
＝l-r1+r1Ｃr1×(l-r1-r2)+r2Ｃr2×・・・×(l-r1-r2-…-rn-2-rn-1)+rn-1Ｃrn-1
＝n(Ｘl-r1,r1)×n(Ｘl-r1-r2,r2)×・・・×n(Ｘl-r1-r2-…-rn-2-rn-1,rn-1)
＝n(Ｘl-r1,r1×Ｘl-r1-r2,r2×・・・×Ｘl-r1-r2-…-rn-2-rn-1,rn-1)・・・【式１０】
となる。（注意：n-2やn-1はrの添字）
つまり、多項係数は格子点集合の直積集合の要素数となる。
それは、
｛ｘ｜ｘ＝（ｘ1.1,ｘ1.2,・・・,ｘ1.l-r1
　　　　　　ｘ2.1,ｘ2.2,・・・,ｘ2.l-r1-r2
　　　　　　・
　　　　　　・
　　　　　　ｘn-1.1,ｘn-1.2,・・・,ｘn-1.l-r1-r2-…-rn-2-rn-1）
　　　　　　０≤∑[i:1→l-r1]ｘ1.i≤r1,
　　　　　　０≤∑[i:1→l-r1-r2]ｘ2.i≤r2,
　　　　　　・
　　　　　　・
　　　　　　０≤∑[i:1→l-r1-r2-…-rn-2-rn-1]ｘn-1.i≤rn-1｝
とも書ける。

６．多項係数の分解式

先に二項係数は、２次元空間上の原点から各格子点への道順と一致していることを説明した。
同様に考えると、多項係数はｎ次元空間上の原点から各格子点への道順と一致していることが分かる。
さらに、二項係数の関係式、
nＣr＝n-1Ｃr＋n-1Ｃr-1
は、ｎ＝ｘ＋ｙ,ｒ＝ｘとすると、
x+yＣx＝x+y-1Ｃx＋x+y-1Ｃx-1＝x+(y-1)Ｃy-1＋(x-1)+yＣx-1
となるので、
(ｘ,ｙ）への道順は、(ｘｰ1,ｙ）と(ｘ,ｙｰ1）への道順の和であることを表している。
ｎ次元においても同様に、
(ｘ1,ｘ2,・・・,ｘn-1,ｘn)への道順は、
(ｘ1ー１,ｘ2,・・・,ｘn-1,ｘn)への道順
(ｘ1,ｘ2ー１,・・・,ｘn-1,ｘn)への道順
　　　　　　・
　　　　　　・
(ｘ1,ｘ2,・・・,ｘn-1ー１,ｘn)への道順
(ｘ1,ｘ2,・・・,ｘn-1,ｘnー１)への道順
の和なので、
lＴ[x1,x2,…,xn-1,xn]＝
l-1Ｔ[x1ー１,x2,…,xn-1,xn]＋
l-1Ｔ[x1,x2ー１,…,xn-1,xn]＋
　　　　　　・
　　　　　　・
l-1Ｔ[x1,x2,…,xn-1ー１,xn]＋
l-1Ｔ[x1,x2,…,xn-1,xnー１] ・・・【式１１】
となる。
これは、パスカルの三角形の作成方法の多次元への拡張となっている。

さらに、【式１１】を各多項係数が１になるまで繰り返し適用すると、多項係数をパスカルの三角形の和公式のように１の和にまで分解することができる。
多項係数を【式９】で二項係数の積に分解してから、パスカルの三角形の和公式を適用しても同様に分解できる。

７．べき乗と格子点

【式８】のｘ1,〜,ｘnに１を代入すれば、
ｎ^ｌ＝∑[r1+r2+…rn-1+rn=l]lＴ[r1,r2,…,rn-1,rn]
となり、【式９】によって、
ｎ^ｌ＝∑[r1+r2+…rn-1+rn=l]lＣr1×(l-r1)Ｃr2×・・・×(l-r1-r2-…-rn-2)Ｃrn-1
さらに、【式１０】より、
ｎ^ｌ＝∑[r1+r2+…rn-1+rn=l]n(Ｘl-r1,r1×Ｘl-r1-r2,r2×・・・×Ｘl-r1-r2-…-rn-2-rn-1,rn-1) ・・・【式１２】
である。

８．自然数と格子点

自然数は一意に素因数分解される。つまり、自然数ｎとすると、
ｎ＝ｐ1^s1×ｐ2^s2×・・・×ｐm-1^sm-1×ｐm^sm
ただし、ｐi(1≤i≤m)は素数。
したがって、【式１２】より、
ｎ＝∏[i:1→m](∑[r1+r2+…rpi-1+rpi=si]n(Ｘsi-r1,r1×Ｘsi-r1-r2,r2×・・・×Ｘsi-r1-r2-…-rpi-2-rpi-1,rpi-1))
となる。（注意：pi-2やpi-1はrの添字）

次ページで、これらの考察を踏まえて、組合せとべき乗の関係式をいくつか紹介する。
「組合せとべき乗の関係式と計算法」

公開日：2017/7/24
最終修正日：2017/7/24