L&M個別オンライン教室~論理と数学とプログラミングのオンライン授業~L&M個別オンライン教室~論理と数学とプログラミングのオンライン授業~L&M個別オンライン教室~論理と数学とプログラミングのオンライン授業~

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

【目次】
前ページ:「パスカルの三角形の和公式、組合せと格子点」
【要約】
1.パスカルの三角形の和公式
2.重複組合せと組合せ
3.組合せと格子点
4.格子点の構造
このページ:
5.多項定理と格子点
6.多項係数の分解式
7.べき乗と格子点
8.自然数と格子点
次ページ:「組合せとべき乗の関係式と計算法」
9.格子点を用いた組合せの展開式
10.格子点を用いたべき乗と組合せの関係式
11.もう一つ、べき乗と組合せの関係式
12.べき乗の格子点の構造と計算法
 12-1.組合せ格子点集合を断面とする計算法
   べき乗格子点集合の1/2の対称性
   Hアルゴリズム
 12-2.多項定理について
   多項定理の効率的な計算法
 12-3.(l+1)^nと(n+1)^lの関係性

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

5.多項定理と格子点

多項定理とは、「1.パスカルの三角形の和公式」で紹介した二項定理、
(x+y)^n=∑[r:0→n]nCr(x^r)(y^(n-r))
のx+y部分を多変数に拡張した定理で、
(x1+x2+・・・+xn-1+xn)^l=∑[r1+r2+…rn-1+rn=l]lT[r1,r2,…,rn-1,rn](x1^r1)(x2^r2)・・・(xn-1^rn-1)(xn^rn) ・・・【式8】
ただし、
lT[r1,r2,…,rn-1,rn]=l!/r1!r2!・・・rn-1!rn!
である。
lT[r1,r2,…,rn-1,rn]を多項係数という。

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

ここで、二項係数n+lClは、n次元空間の原点から距離lまでにある格子点の数であった、
つまり、
Xn,l={x|x=(x1,x2,・・・xn-1,xn), 0≤∑[i:1→n]xi≤l}
とすると、n(Xn,l)=n+lClであるので、【式9】を変形すると、
lT[r1,r2,…,rn-1,rn]
=l-r1+r1Cr1×(l-r1-r2)+r2Cr2×・・・×(l-r1-r2-…-rn-2-rn-1)+rn-1Crn-1
=n(Xl-r1,r1)×n(Xl-r1-r2,r2)×・・・×n(Xl-r1-r2-…-rn-2-rn-1,rn-1)
=n(Xl-r1,r1×Xl-r1-r2,r2×・・・×Xl-r1-r2-…-rn-2-rn-1,rn-1)・・・【式10】
となる。(注意:n-2やn-1はrの添字)
つまり、多項係数は格子点集合の直積集合の要素数となる。
それは、
{x|x=(x1.1,x1.2,・・・,x1.l-r1
      x2.1,x2.2,・・・,x2.l-r1-r2
      ・
      ・
      xn-1.1,xn-1.2,・・・,xn-1.l-r1-r2-…-rn-2-rn-1)
      0≤∑[i:1→l-r1]x1.i≤r1,
      0≤∑[i:1→l-r1-r2]x2.i≤r2,
      ・
      ・
      0≤∑[i:1→l-r1-r2-…-rn-2-rn-1]xn-1.i≤rn-1}
とも書ける。

6.多項係数の分解式

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

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

7.べき乗と格子点

【式8】のx1,〜,xnに1を代入すれば、
n^l=∑[r1+r2+…rn-1+rn=l]lT[r1,r2,…,rn-1,rn]
となり、【式9】によって、
n^l=∑[r1+r2+…rn-1+rn=l]lCr1×(l-r1)Cr2×・・・×(l-r1-r2-…-rn-2)Crn-1
さらに、【式10】より、
n^l=∑[r1+r2+…rn-1+rn=l]n(Xl-r1,r1×Xl-r1-r2,r2×・・・×Xl-r1-r2-…-rn-2-rn-1,rn-1) ・・・【式12】
である。

8.自然数と格子点

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

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

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