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

パスカルの三角形の和公式、組合せと格子点

※このページの内容は、日本応用数理学会2000年度年会にて「自然数とnCrを繋ぐ公式」と題して発表した内容を元にしている。原稿紛失のため手元資料に考察を加えた。数学史的な背景としては、組合せ理論の中でも三角数と接点を持った分野と言えるだろう。三角数はピタゴラスの時代より研究されており、組合せとの関係は13世紀にペルシャの数学者アル・ファリシによって初めて一般的な指摘を受けたらしい。以下、発表に用いたスライド数枚を掲載する。

日本応用数理学会発表スライド1日本応用数理学会発表スライド2日本応用数理学会発表スライド3

【目次】
【要約】
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の関係性

【要約】

パスカルの三角形は、和の演算により組合せの数(コンビネーション、以下、たんに組合せと呼ぶ)を作成することができる。この組合せの和による導出方法を「パスカルの三角形の和公式」として定式化する。その過程で、組合せは重複組合せの和であることも示される。一方、重複組合せはn次元の距離lにある格子点の数と等しいので、組合せはn次元の距離lまでにある格子点の数と等しいことが分かる。そこで、n次元の距離lまでにある格子点の構造とその対称性をより詳しく考察する。
別ページにて以上の議論を多項定理に拡張した上で、べき(羃)乗や自然数との関係を考察する。さらに、これらの考察を踏まえて、組合せとべき乗の関係式をいくつか紹介し、最後にべき乗の格子点の構造を考察してその計算法を示す。

1.パスカルの三角形の和公式

下図のように、1を左右斜めに並べて順次足していくことで作成される表は「パスカルの三角形」として知られている。

〔図1〕パスカルの三角形
      1
     1 1
    1 2 1
   1 3 3 1
  1 4 6 4 1
 1 5 10 10 5 1
  ・   ・   ・
  ・   ・   ・
  ・   ・   ・

二項定理は、
(x+y)^n=∑[r:0→n]nCr(x^r)(y^(n-r))
・^はべき乗記号とする。
・∑[r:0→n]は、右式のrに0からnまでを代入して、総和を取ることとする。

であり、各項の係数に組合せの数(コンビネーション、以下、たんに組合せと呼ぶ)が出てくるが、パスカルの三角形のn段(n=0段より始める)は、この二項定理の係数と等しくなっている。

別に、パスカルの三角形の一番上の1を原点、左右斜めに並べられた1をxy座標、各数をxy座標の格子点と対応させると、各係数は、原点から各格子点への道順と一致している。

〔図2〕パスカルの三角形とxy座標
 y
 ↑   ・
 1  ・
 | ・
 1ー5      ・
 | |     ・
 1ー4ー10  ・
 | | |
 1ー3ー6ー10     ・
 | | | |    ・  
 1ー2ー3ー4ー5 ・
 | | | | | 
 1ー1ー1ー1ー1ー1→x

格子点(x,y)までの距離をx+y=nとすると、原点から(x,y)に到達するには+1づつx方向またはy方向へn回進むうち、x方向がx回、y方向がy回あることになる。そうするとその道順は、+1進む順番の1番目からn番目までの間に、x方向に進む順番をx回選ぶ組合せに等しいので、nCx又はx+yCxとなる。
この場合、原点への道順は1とし、0!=1とする。したがって、0C0=1、nC0=1である。

以上のように、パスカルの三角形は組合せの数を和の演算によって導出している。そして、それは規則的な手順に基づいている。そこで、この組合せの規則的な和による導出方法を次に定式化しょう。

【命題】パスカルの三角形の和公式
x+yCx=∑[k1:0→x](∑[k2:0→k1](…∑[k(y-1):0→k(y-2)](∑[ky:0→k(y-1)](1))…))
ちなみに、一般的な記法では、
$${}_{x+y} \mathrm{C} _x\,=\,\sum_{k_1=0}^x(\sum_{k_2=0}^{k_1}(\,\cdot\cdot\cdot\sum_{k_{y-1}=0}^{k_{y-2}}(\sum_{k_y=0}^{k_{y-1}}(1))\,\cdot\!\cdot\cdot\,))$$
となる。

【証明】
パスカルの三角形は、
nCr=n-1Cr+n-1Cr-1
を繰り返し適用することで作成される。
これをx+yCxに繰り返し適用すればよい。
x+yCx=(x+y)!/x!y!=(x+y-1)!/(x-1)!y!+(x+y-1)!/x!(y-1)!
(x+y-1)!/(x-1)!y!=(x+y-2)!/(x-2)!y!+(x+y-2)!/(x-1)!(y-1)!
(x+y-2)!/(x-2)!y!=(x+y-3)!/(x-3)!y!+(x+y-3)!/(x-2)!(y-1)!
  ・
  ・
  ・
(x+y-(x-2))!/(x-(x-2))!y!=(x+y-(x-1))!/(x-(x-1))!y!+(x+y-(x-1))!/(x-(x-2))!(y-1)!
(x+y-(x-1))!/(x-(x-1))!y!=(x+y-x)!/(x-x)!y!+(x+y-x)!/(x-(x-1))!(y-1)! ・・・ 【式1】
ここで、【式1】を整理すると、
(1+y))!/1!y!=y!/0!y!+y!/1!(y-1)!
さらに、
y!/0!y!=(y-1)!/0!(y-1)!
なので、各式を代入していくと、
x+yCx=∑[k:0→x](k+y-1)!/k!(y-1)!=∑[k:0→x]k+y-1Ck ・・・ 【式2】

次に、【式2】を観察すると、k+y-1Ckに対して【式2】を繰り返し適用することができるので、
kに数字を添えて、
x+yCx=∑[k1:0→x]k1+y-1Ck1
k1+y-1Ck1=∑[k2:0→k1]k2+y-2Ck2
k2+y-2Ck2=∑[k3:0→k2]k3+y-3Ck3
  ・
  ・
  ・
k[y-2]+y-(y-2)Ck[y-2]=∑[k[y-1]:0→k[y-2]]k[y-1]+y-(y-1)Ck[y-1]
k[y-1]+y-(y-1)Ck[y-1]=∑[k[y]:0→k[y-1]]k[y]+y-yCk[y] ・・・ 【式3】
ここで、【式3】を整理すると、
k[y-1]+1Ck[y-1]=∑[k[y]:0→k[y-1]]k[y]Ck[y]=∑[k[y]:0→k[y-1]]1
∵ k[y]Ck[y]=1
・k[y-2]は、kの添字がy-2であることとする。例えばk1とk[1]は同じ。
各式を代入していくと、
x+yCx=∑[k1:0→x](∑[k2:0→k1](…∑[k(y-1):0→k(y-2)](∑[ky:0→k(y-1)](1))…))   □

パスカルの三角形の和公式によって、パスカルの三角形において組合せを計算した手順は、
1の和を規則正しく積み重ねていく手順であることが確認できる。
さらに、それがどのような意味を持っているのか考察していく。

2.重複組合せと組合せ

組合せとは、異なるn個のものからr個を選ぶ操作のことであり、
重複組合せとは、異なるn種類のものから重複を許してr個を選ぶ操作のことである。
重複組合せは、例えば、6種類の目のある普通のサイコロを2回投げる場合の数は、
11,12,13,14,15,16,22,23,24,25,26,33,34,35,36,44,45,46,55,56,66
(12と21は同じと考えるところが、順列と異なり、組合せなのである。)
以上、21通りである。
重複組合せの数をnHrと書き、
nHr=n+r-1Crである。
なぜならば、
異なるn種類のものから重複を許してr個を選ぶ操作は、r個のものをn種類に分ける操作と同じであり、
○○○・・・○○○  ←r個
|||・・・|||  ←n−1個
r個のものをn−1個の仕切りで分け、
同じ仕切り場所に入ったものは、同じ種類、
異なる仕切り場所に入ったものは、異なる種類、
と考えれば、この操作でr個のものをn種類に分けることができる。
したがって、この○と|の並び順を求めれば良いから、
n+r-1Crとなる。

ここで、【証明1】の【式2】をみると、
x+yCx=∑[k:0→x](k+y-1)!/k!(y-1)!=∑[k:0→x]k+y-1Ck=∑[k:0→x]y+k-1Ck
右辺は重複組合せとなっている。したがって、
組合せは、重複組合せの和として、
x+yCx=∑[k:0→x]yHk ・・・ 【式4】
と書ける。
ちなみに、一般的な記法では、
$${}_{x+y} \mathrm{C} _x\,=\,\sum_{k=0}^x{}_{y} \mathrm{H} _k$$
となる。

3.組合せと格子点

n次元空間の格子点の数について考える。
格子点とは、(x1,x2,・・・xn-1,xn)において、任意のxi(1≤i≤n)が整数である点のことである。
以下、xi≥0とする。
また、原点からの格子点の距離lとは、
l=∑[i:1→n]xi
のこととする。

まず、n次元空間(n≥1)の原点から距離l(l≥0)にある格子点の数を考えると、
進む数l個をn種類に分ける操作と同じであるから、前述の重複組合せであることが分かり、
nHl=n+l-1Cl
である。
そうすると、【式4】から、
∑[k:0→l]nHk=l+nCl=n+lCl ・・・ 【式5】
であることが分かり、
左辺は、n次元空間の原点から距離lまでにある格子点の数なので、
組合せn+lClは、n次元空間の原点から距離lまでにある格子点の数であることが分かった。

4.格子点の構造

以上のように、組合せと格子点には密接な関係がある。
そこで、格子点の構造を知るために、まず一般論として格子点を集合として考えよう。

格子点集合の定義

改めて、格子点を集合として定義する。
格子点集合とは、
Ln={x|x=(x1,x2,・・・xn-1,xn),xi≥0(1≤i≤n)の整数}
の部分集合とする。
格子点集合が等しいとは、格子点集合が集合として等しいこととする。

格子点集合の対称性

格子点集合Lnのべき集合、つまり格子点集合の全体を℘(Ln)とする。
n次対称群をSnとする。
σ∈Snによる格子点集合X∈℘(Ln)の置換を、
σ(X)={x’|x’=σ(x),x∈X}
とする。
℘(Ln)に、対称関係を以下のように定義する。
X,Y∈℘(Ln)について、
X∼Y ⇔ ∃σ∈Sn, σ(X)=Y
すると、対称関係は同値関係である。

そこで、対称関係によるXの同値類をRxとする。
ここで、Hx={σ∈Sn|X=σ(X)}とすると、
HxはSnの部分群である。
他方、写像φを、
φ:Sn → Rx
  σ → σ(X)
と定義して、
左剰余類σHx∈Sn/Hxの任意のσ1,σ2∈σHxを取ると、
σ1¯¹σ2=hをみたすh∈Hxがあるので、σ2=σ1hであり、
φ(σ2)=σ2(X)=σ1h(X)=σ1(X)=φ(σ1)となる。
したがって、写像φを、
φ:Sn/Hx → Rx
  σHx → σ(X)
と再定義することができる。
Y,Z∈Rx,Y=Z,Y=φ(σ1Hx),Z=φ(σ2Hx)のとき、
σ1(X)=σ2(X),X=σ1¯¹σ2(X)なので、
σ1¯¹σ2∈Hxより、σ1Hx=σ2Hxになり、φは単射である。
任意のY∈Rxについて、Y=σ(X)=φ(σHx)があるので、φは全射である。
したがって、φは双射である。

φが双射であることから、
n(Rx)=n(Sn/Hx)=n(Sn)/n(Hx)であり、
n(Sn)=n!なので、n!=n(Rx)n(Hx)と分かる。
つまり、格子点集合の対称性には、置換によって格子点集合が変化しない対称性と、
変化する対称性があり、その数は反比例する。

組合せと格子点集合

それでは、組合せと格子点の話に戻ろう。
n次元空間の原点から距離lまでにある格子点集合Xn,lは、
Xn,l={x|x=(x1,x2,・・・xn-1,xn), 0≤∑[i:1→n]xi≤l}
と表せる。
その部分集合Xn,[k](0≤k≤l)、
Xn,[k]={x|x=(x1,x2,・・・xn-1,xn), ∑[i:1→n]xi=k}
(ただし、[k]はkを固定していることを表すとする。)
をとる。
さらに、Xn,[k]のxnを、0≤m≤kなるmで固定すると、
Xn,[k],[m]={x|x=(x1,x2,・・・xn-1,xn), ∑[i:1→n]xi=k, xn=m}
となり、
Xn,[k]=∪[m:0→k]Xn,[k],[m]
のようにXn,[k]はXn,[k],[m]で分割される。
ここで、格子点集合上の写像fを、
f:(x1,x2,・・・xn-1,xn) → (x1,x2,・・・xn-1)
とすると、
fはXn,[k],[m]からXn-1,[k-m]において双射となる。
そこで、℘(Ln)上の写像Fを、
F:X → {x’|x’=f(x),x∈X}
とすると、fは双射なので、
Xn,[k]=∪[m:0→k]Xn,[k],[m]=∪[m:0→k]F¯¹(Xn-1,[k-m])=F¯¹(∪[m:0→k]Xn-1,[k-m])
=F¯¹(Xn-1,k) ・・・ 【式6】
ここで、
Xn,l=∪[k:0→l]Xn,[k]より、
Xn,l=∪[k:0→l]F¯¹(Xn-1,k)=F¯¹(∪[k:0→l]Xn-1,k) ・・・ 【式7】
である。
これは、要素数を取れば【式5】を表している。つまり、
n(Xn,l)=∑[k:0→l]n(Xn-1,k)
n+lCl=∑[k:0→l]n-1+kCk
となる。

【式7】を言葉で説明すると、
n次元空間の原点から距離lまでの格子点は、距離k(0≤k≤l)で分割すると、
nー1次元空間の原点から距離kまでの格子点となり、これが帰納的に1次元まで続くということであり、
直観的には思いつかないような、格子点のとても美しい構造を示している。
パスカルの三角形の和公式は、n次元空間の原点から距離lまでの格子点を、
逆に1次元から一つづつ数え上げる操作だったことが分かる。

以上のように、格子点集合の構造を考えることで、
組合せについての関係式を得ることができるので、いくつかの関係式を追って別ページで紹介する。

最後に、もう少し格子点集合Xn,lの構造について考えてみる。
Xn,lのxrを、0≤k≤lなるl-kで固定して、
Xn,[r,l-k]={x|x=(x1,x2,・・・xn-1,xn), 0≤∑[i:1→n]xi≤l, xr=l-k}
として、
Xn,lのxsを、0≤k≤lなるl-kで固定して、
Xn,[s,l-k]={x|x=(x1,x2,・・・xn-1,xn), 0≤∑[i:1→n]xi≤l, xs=l-k}
とすると、
xrをxsと交換する置換σ[r→s]について、
σ[r→s](Xn,[r,l-k])=Xn,[s,l-k]
が成り立つ。
さらに、
Xn,[k]={x|x=(x1,x2,・・・xn-1,xn), ∑[i:1→n]xi=k}
を考えると、【式6】より、
Xn,[k]=F¯¹(Xn-1,k)
であり、
格子点集合上の写像frを、
fr:(x1,x2,・・,xr-1,xr,xr+1,・・xn-1,xn) → (x1,x2,・・xr-1,xr+1・・xn-1,xn)
とすると、
frはXn,[r,l-k]からXn-1,kにおいて双射となる。
そこで、℘(Ln)上の写像Frを、
Fr:X → {x’|x’=fr(x),x∈X}
とすると、
Xn,[k]=F¯¹(Xn-1,k)=F¯¹(Fr(Xn,[r,l-k]))
となる。
これはつまり、とくにk=lを考えると、
幾何的にXn,lを対応させるのに最も自然な図形は、正単体であり、
原点と各頂点を入れ替えても内部構造までまったく同じ、という対称性を示している。

組合せと格子点の多項定理への拡張
組合せとべき乗の関係式と計算法

公開日:2017/7/24
修正日:2022/7/24 冒頭の『日本応用数理学会2000年度年会にて「自然数とnCrを繋ぐ公式」と題して発表した』注釈を追記
最終修正日:2022/7/24