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

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

【目次】
【要約】
１．パスカルの三角形の和公式
２．重複組合せと組合せ
３．組合せと格子点
４．格子点の構造

次ページ：組合せと格子点の多項定理への拡張
５．多項定理と格子点
６．多項係数の分解式
７．べき乗と格子点
８．自然数と格子点
次々ページ：組合せとべき乗の関係式と計算法
９．格子点を用いた組合せの展開式
１０．格子点を用いたべき乗と組合せの関係式
１１．もう一つ、べき乗と組合せの関係式
１２．べき乗の格子点の構造と計算法
　１２-１．組合せ格子点集合を断面とする計算法
　　　べき乗格子点集合の1／2の対称性
　　　Ｈアルゴリズム
　１２-２．多項定理について
　　　多項定理の効率的な計算法
　１２-３．(ｌ＋1)^nと(ｎ＋1)^lの関係性

【要約】

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

１．パスカルの三角形の和公式

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

〔図１〕パスカルの三角形
　　　　　　１
　　　　　１　１
　　　　１　２　１
　　　１　３　３　１
　　１　４　６　４　１
　１　５　10　10　５　１
　　・　　　・　　　・
　　・　　　・　　　・
　　・　　　・　　　・

二項定理は、
(ｘ＋ｙ)^ｎ=∑[r:0→n]nＣr(ｘ^r)(ｙ^(n-r))
・^はべき乗記号とする。
・∑[r:0→n]は、右式のrに0からnまでを代入して、総和を取ることとする。
であり、各項の係数に組合せの数（コンビネーション、以下、たんに組合せと呼ぶ）が出てくるが、パスカルの三角形のｎ段（ｎ＝0段より始める）は、この二項定理の係数と等しくなっている。

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

〔図２〕パスカルの三角形とｘｙ座標
　ｙ
　↑　　　・
　１　　・
　｜　・
　１ー５　　　　　　・
　｜　｜　　　　　・
　１ー４ー10　　・
　｜　｜　｜
　１ー３ー６ー10　　　　　・
　｜　｜　｜　｜　　　　・　　
　１ー２ー３ー４ー５　・
　｜　｜　｜　｜　｜　
　１ー１ー１ー１ー１ー１→ｘ

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

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

【命題】パスカルの三角形の和公式
x+yＣx＝∑[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\,))$$
となる。

【証明】
パスカルの三角形は、
nＣr＝n-1Ｃr＋n-1Ｃr-1
を繰り返し適用することで作成される。
これをx+yＣxに繰り返し適用すればよい。
x+yＣx＝(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+y))!／1!y!＝y!／0!y!＋y!／1!(y-1)!
さらに、
y!／0!y!＝(y-1)!／0!(y-1)!
なので、各式を代入していくと、
x+yＣx＝∑[k:0→x](k+y-1)!／k!(y-1)!＝∑[k:0→x]k+y-1Ｃk ・・・ 【式２】

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

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

２．重複組合せと組合せ

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

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

３．組合せと格子点

ｎ次元空間の格子点の数について考える。
格子点とは、(ｘ1,ｘ2,・・・ｘn-1,ｘn)において、任意のｘi(1≤ｉ≤n)が整数である点のことである。
以下、ｘi≥０とする。
また、原点からの格子点の距離ｌとは、
ｌ＝∑[i:1→n]ｘi
のこととする。

まず、ｎ次元空間（ｎ≥１）の原点から距離ｌ（ｌ≥０）にある格子点の数を考えると、
進む数ｌ個をｎ種類に分ける操作と同じであるから、前述の重複組合せであることが分かり、
nＨl＝n+l-1Ｃl
である。
そうすると、【式４】から、
∑[k:0→l]nＨk＝l+nＣl＝n+lＣl ・・・ 【式５】
であることが分かり、
左辺は、ｎ次元空間の原点から距離ｌまでにある格子点の数なので、
組合せn+lＣlは、ｎ次元空間の原点から距離ｌまでにある格子点の数であることが分かった。

４．格子点の構造

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

格子点集合の定義

改めて、格子点を集合として定義する。
格子点集合とは、
Ｌn＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・ｘn-1,ｘn),ｘi≥０(1≤ｉ≤n)の整数｝
の部分集合とする。
格子点集合が等しいとは、格子点集合が集合として等しいこととする。

格子点集合の対称性

格子点集合Ｌnのべき集合、つまり格子点集合の全体を℘(Ｌn)とする。
ｎ次対称群をＳnとする。
σ∈Ｓnによる格子点集合Ｘ∈℘(Ｌn)の置換を、
σ(Ｘ)＝｛ｘ’｜ｘ’＝σ(ｘ),ｘ∈Ｘ｝
とする。
℘(Ｌn)に、対称関係を以下のように定義する。
Ｘ,Ｙ∈℘(Ｌn)について、
Ｘ∼Ｙ ⇔ ∃σ∈Ｓn, σ(Ｘ)＝Ｙ
すると、対称関係は同値関係である。

そこで、対称関係によるＸの同値類をＲxとする。
ここで、Ｈx＝｛σ∈Ｓn｜Ｘ＝σ(Ｘ)｝とすると、
ＨxはＳnの部分群である。
他方、写像φを、
φ：Ｓn → Ｒx
　　σ　→ σ(Ｘ)
と定義して、
左剰余類σＨx∈Ｓn／Ｈxの任意のσ1,σ2∈σＨxを取ると、
σ1¯¹σ2＝ｈをみたすｈ∈Ｈxがあるので、σ2＝σ1ｈであり、
φ(σ2)＝σ2(Ｘ)＝σ1ｈ(Ｘ)＝σ1(Ｘ)＝φ(σ1)となる。
したがって、写像φを、
φ：Ｓn／Ｈx → Ｒx
　　σＨx　→ σ(Ｘ)
と再定義することができる。
Ｙ,Ｚ∈Ｒx,Ｙ＝Ｚ,Ｙ＝φ(σ1Ｈx),Ｚ＝φ(σ2Ｈx)のとき、
σ1(Ｘ)＝σ2(Ｘ),Ｘ＝σ1¯¹σ2(Ｘ)なので、
σ1¯¹σ2∈Ｈxより、σ1Ｈx＝σ2Ｈxになり、φは単射である。
任意のＹ∈Ｒxについて、Ｙ＝σ(Ｘ)＝φ(σＨx)があるので、φは全射である。
したがって、φは双射である。

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

組合せと格子点集合

それでは、組合せと格子点の話に戻ろう。
ｎ次元空間の原点から距離ｌまでにある格子点集合Ｘn,lは、
Ｘn,l＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・ｘn-1,ｘn), ０≤∑[i:1→n]ｘi≤ｌ｝
と表せる。
その部分集合Ｘn,[k]（０≤ｋ≤ｌ）、
Ｘn,[k]＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・ｘn-1,ｘn), ∑[i:1→n]ｘi＝ｋ｝
（ただし、[k]はkを固定していることを表すとする。）
をとる。
さらに、Ｘn,[k]のｘnを、０≤ｍ≤ｋなるｍで固定すると、
Ｘn,[k],[m]＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・ｘn-1,ｘn), ∑[i:1→n]ｘi＝ｋ, ｘn＝ｍ｝
となり、
Ｘn,[k]＝∪[m:0→k]Ｘn,[k],[m]
のようにＸn,[k]はＸn,[k],[m]で分割される。
ここで、格子点集合上の写像ｆを、
ｆ：(ｘ1,ｘ2,・・・ｘn-1,ｘn) → (ｘ1,ｘ2,・・・ｘn-1)
とすると、
fはＸn,[k],[m]からＸn-1,[k-m]において双射となる。
そこで、℘(Ｌn)上の写像Ｆを、
Ｆ：Ｘ → ｛ｘ’｜ｘ’＝f(ｘ),ｘ∈Ｘ｝
とすると、ｆは双射なので、
Ｘn,[k]＝∪[m:0→k]Ｘn,[k],[m]＝∪[m:0→k]Ｆ¯¹(Ｘn-1,[k-m])＝Ｆ¯¹(∪[m:0→k]Ｘn-1,[k-m])
＝Ｆ¯¹(Ｘn-1,k) ・・・ 【式６】
ここで、
Ｘn,l＝∪[k:0→l]Ｘn,[k]より、
Ｘn,l＝∪[k:0→l]Ｆ¯¹(Ｘn-1,k)＝Ｆ¯¹(∪[k:0→l]Ｘn-1,k) ・・・ 【式７】
である。
これは、要素数を取れば【式５】を表している。つまり、
n(Ｘn,l)＝∑[k:0→l]n(Ｘn-1,k)
n+lＣl＝∑[k:0→l]n-1+kＣk
となる。

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

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

最後に、もう少し格子点集合Ｘn,lの構造について考えてみる。
Ｘn,lのｘrを、０≤ｋ≤ｌなるｌ-ｋで固定して、
Ｘn,[r,l-k]＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・ｘn-1,ｘn), ０≤∑[i:1→n]ｘi≤ｌ, ｘr＝ｌ-ｋ｝
として、
Ｘn,lのｘsを、０≤ｋ≤ｌなるｌ-ｋで固定して、
Ｘn,[s,l-k]＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・ｘn-1,ｘn), ０≤∑[i:1→n]ｘi≤ｌ, ｘs＝ｌ-ｋ｝
とすると、
ｘrをｘsと交換する置換σ[r→s]について、
σ[r→s](Ｘn,[r,l-k])＝Ｘn,[s,l-k]
が成り立つ。
さらに、
Ｘn,[k]＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・ｘn-1,ｘn), ∑[i:1→n]ｘi＝ｋ｝
を考えると、【式６】より、
Ｘn,[k]＝Ｆ¯¹(Ｘn-1,k)
であり、
格子点集合上の写像ｆrを、
ｆr：(ｘ1,ｘ2,・・,ｘr-1,ｘr,ｘr+1,・・ｘn-1,ｘn) → (ｘ1,ｘ2,・・ｘr-1,ｘr+1・・ｘn-1,ｘn)
とすると、
frはＸn,[r,l-k]からＸn-1,kにおいて双射となる。
そこで、℘(Ｌn)上の写像Ｆrを、
Ｆr：Ｘ → ｛ｘ’｜ｘ’＝fr(ｘ),ｘ∈Ｘ｝
とすると、
Ｘn,[k]＝Ｆ¯¹(Ｘn-1,k)＝Ｆ¯¹(Ｆr(Ｘn,[r,l-k]))
となる。
これはつまり、とくにｋ＝ｌを考えると、
幾何的にＸn,lを対応させるのに最も自然な図形は、正単体であり、
原点と各頂点を入れ替えても内部構造までまったく同じ、という対称性を示している。

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

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