組合せとべき乗の関係式と計算法

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

これまで、組合せと格子点の関係、その多項定理への拡張などを考察してきた。
これらの考察を踏まえて、格子点の構造を観察することで組合せやべき乗の関係式を導出することができる。
いくつかの関係式を紹介して、最後にべき乗の格子点の構造とその計算法を示す。

９．格子点を用いた組合せの展開式

「パスカルの三角形の和公式、組合せと格子点」の議論から、
ｎ次元空間の原点から距離ｌまでにある格子点集合Ｘn,lは、
Ｘn,l＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・ｘn-1,ｘn), ０≤∑[i:1→n]ｘi≤ｌ｝
であり、
n(Ｘn,l)＝n+lＣl
であった。
ここでは、
n+lＣl＝∑[j:0→m]nＣj×lＣj
ただし、ｍ＝min(ｎ,ｌ)
を証明する。
ちなみに、一般的な記法では、
$${}_{n+l} \mathrm{C} _l\,=\,\sum_{j=0}^m{}_{n} \mathrm{C} _j\times{}_{l} \mathrm{C} _j$$
となる。

【証明】
Ｘn,lを観察すると、任意のｘiは0又は1以上であることが分かる。
そこで、1以上であるｘiの個数j(0≤j≤min(ｎ,ｌ))によってＸn,lを分解する。
つまり、写像ｈを、
ｈ:ｘ → 「1以上であるｘiの個数」
として、
Ｘn,l,j＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・ｘn-1,ｘn), ０≤∑[i:1→n]ｘi≤ｌ, ｈ(ｘ)＝j｝
とすると、
Ｘn,l＝∪[j:0→m]Ｘn,l,j
である。
さらに、Ｘn,l,jについて観察すると、
ｘにおいて、1以上であるｘiの並び順は、nＣj個あり、
その一つの並びにおいて、1以上であるｘiに残りのl-jを並べた格子点集合Ｙn,l,jと、
j次元空間の原点から距離l-jまでにある格子点集合Ｘj,l-jには、双射写像を定義できる。
そこで、
n(Ｙn,l,j)＝n(Ｘj,l-j)＝j+(l-j)Ｃj＝lＣj
となり、したがって、
n(Ｘn,l,j)＝nＣj×n(Ｙn,l,j)＝nＣj×lＣj
であり、
n+lＣl＝n(Ｘn,l)＝n(∪[j:0→m]Ｘn,l,j)＝∑[j:0→m]n(Ｘn,l,j)＝∑[j:0→m]nＣj×lＣj　　　□

１０．格子点を用いたべき乗と組合せの関係式

ｌ^n＝∑[i:0→n]nＣi(ｌ-1)^i, (ｌ≥1)
ただし、0^0＝1とする。
ちなみに、一般的な記法では、
$$l^n\,=\,\sum_{i=0}^n{}_n \mathrm{C} _i(l-1)^i{,}\quad(l\geqq1)$$
となる。

【証明】
Ｐn,l＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・ｘn-1,ｘn), ０≤ｘi≤ｌ(1≤i≤n）｝とする。
つまりｌ≥0において、n(Ｐn,l)＝(ｌ＋1)^nである。
先程と同様に写像ｈを、
ｈ:ｘ → 「1以上であるｘiの個数」
とする。
Ｐn,l,j＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・ｘn-1,ｘn), ０≤ｘi≤ｌ(1≤i≤n）, ｈ(ｘ)＝j｝とすると、
n(Ｐn,l,j)＝nＣj×ｌ^jであり、
Ｐn,l＝∪[j:0→n]Ｐn,l,jなので、
(ｌ＋1)^n＝n(Ｐn,l)＝∑[j:0→n]n(Ｐn,l,j)＝∑[j:0→n]nＣj×ｌ^j
ここで、ｌ＋1＝ｌ’と置き直せばよい。　　　□

この式の係数は二項係数であり、ｌ＝2の場合は二項展開と同じである。

１１．もう一つ、べき乗と組合せの関係式

これは格子点集合を題材にして求めた関係式ではなく、ただ式変形によって導いた関係式だが紹介しておく。
ｌ^n＝∑[i:1→n](ｉ!×l-1Ｃi-1×ｌ^(n-i))＋ｎ!×l-1Ｃn
ただし、q＞pならば、pＣq＝0とする。
ちなみに、一般的な記法では、
$$l^n\,=\,\sum_{i=1}^n(i!\times{}_{l-1} \mathrm{C} _{i-1}\times l^{n-i})+n!\times{}_{l-1} \mathrm{C} _n$$
となる。

【証明】
ｌ^n＝(ｌ-1)ｌ^(n-1)＋ｌ^(n-1)＝(ｌ-1)ｌ^(n-1)＋1!×l-1Ｃ0×ｌ^(n-1)
(ｌ-1)ｌ^(n-1)＝(ｌ-1)(ｌ-2)ｌ^(n-2)＋2(ｌ-1)ｌ^(n-2)＝(ｌ-1)(ｌ-2)ｌ^(n-2)＋2!×l-1Ｃ1×ｌ^(n-2)
(ｌ-1)(ｌ-2)ｌ^(n-2)＝(ｌ-1)(ｌ-2)(ｌ-3)ｌ^(n-3)＋3(ｌ-1)(ｌ-2)ｌ^(n-3)＝(ｌ-1)(ｌ-2)(ｌ-3)ｌ^(n-3)＋3!×l-1Ｃ2×ｌ^(n-3)
　　・
　　・
　　・
(ｌ-1)(ｌ-2)…(ｌ-(n-2))(ｌ-(n-1))ｌ^(n-1)＝(ｌ-1)(ｌ-2)…(ｌ-(n-1))(ｌ-n)ｌ^(n-n)＋n(ｌ-1)(ｌ-2)…(ｌ-(n-1))ｌ^(n-n)＝ｎ!×l-1Ｃn＋ｎ!×l-1Ｃn-1
であり、先頭の式に次式以降を次々に代入していけばよい。　　　□

１２．べき乗の格子点の構造と計算法

べき乗の展開式として、多項定理を用いた展開法の他には何かないだろうか。
以下、その工夫を述べる。

１２-１．組合せ格子点集合を断面とする計算法

べき乗の格子点集合Ｅn,lを、
Ｅn,l＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・,ｘn-1,ｘn), ０≤ｘi≤ｌ｝
と考える。つまり、n(Ｅn,l)＝(ｌ＋1)^nである。(n≥1,l≥0）
組合せの格子点集合Ｘn,lは、
Ｘn,l＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・,ｘn-1,ｘn), ０≤∑[i:1→n]ｘi≤ｌ｝
であった。つまり、n(Ｘn,l)＝n+lＣlが成り立つ。

そこで、Ｅn,lをＸn,lで分解できれば、べき乗の組合せによる展開式ができる。
しかし、それはなかなか難しく、逆にＥn,l⊂Ｘn,nlであることは容易に分かる。
かといって、Ｘn,nlをＥn,lで分解することも難しそうだ。
ここでは、Ｘn,nlを、
Ｘn,[k]＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・,ｘn-1,ｘn), ∑[i:1→n]ｘi＝ｋ｝
（ただし、[k]はkを固定していることを表すとする。）
として、
Ｘn,nl＝∪[k:0→nl]Ｘn,[k]
のように分解したことを思い出し、
ＥＸn,[k]＝Ｅn,l∩Ｘn,[k]＝｛ｘ｜ｘ＝(ｘ1,ｘ2,・・・,ｘn-1,ｘn), ０≤ｘi≤ｌ, ∑[i:1→n]ｘi＝ｋ｝
として、
Ｅn,l＝∪[k:0→nl]ＥＸn,[k]
と分解しょう。

べき乗格子点集合の1／2の対称性

まず初めに分かることは、写像fを、
f:ＥＸn,[k] → ＥＸn,[nl-k]
　(ｘ1,ｘ2,・・・,ｘn-1,ｘn) → (l−ｘ1,l−ｘ2,・・・,l−ｘn-1,l−ｘn)
とすれば、
たしかに、
∑[i:1→n](l−ｘi)＝nl−ｋより、
f(ｘ)∈ＥＸn,[nl-k]なので、fは写像として定義できる。
ｘ,ｙ∈ＥＸn,[k]で、f(ｘ)＝f(ｙ)ならば、
l−ｘi＝l−ｙiなので、ｘi＝ｙiであり、fは単射。
任意のｙ∈Ｘn,[nl-k]について、f(ｙ)∈ＥＸn,[k]でf(f(ｙ))＝ｙなので、全射。
したがって、fは双射であり、n(ＥＸn,[k])＝n(ＥＸn,[nl-k])である。
そこで、kは0から、nlが奇数ならば(nl-1)/2まで、nlが偶数ならばnl/2までを調べればよい。

Ｈアルゴリズム

「４．格子点の構造」の「格子点集合の対称性」では、格子点集合に置換を定義したが、
ここでは、格子点に対するｎ次対称群Ｓnによる置換を考えて、
Ｅn,lに、対称関係を以下のように定義する。
ｘ,ｙ∈Ｅn,lについて、
ｘ∼ｙ ⇔ ∃σ∈Ｓn, σ(ｘ)＝ｙ

次に、ＥＸn,[k]のＳnによる各同値類の代表元ｘを、
成分について左昇順の元、つまり、
1≤i,j≤ｎ,i≤j ⇒ ｘi≥ｘj
を満たす元とする。
ちなみに、互換を繰り返せば、左昇順の元があることは明らか。

ＥＸn,[k]の各同値類のすべての代表元の集合をＤn,[k]⊂ＥＸn,[k]とし、
ｘ,ｙ∈Ｄn,[k]、Ｉ＝｛i｜1≤i≤ｎ, ｘi＞ｙi又はｘi＜ｙi｝として、
Ｉの最小元ｍ＝min(Ｉ)について、ｘm＞ｙm ⇒ ｘ＞ｙ
（つまり、より左にある成分の大きさを優先順位が高いものとして考える。）
という順序をＤn,[k]に定める。これは全順序である。
さらに、ｘ≥ｙかつｘ≤ｙであれば、
ｘ≥ｙより、ある1≤i≤ｎがあって、1≤j＜iついてｘj＝ｙjであり、ｘi≥ｙiである。
仮に、ｘi＞ｙiとすると、1≤j＜iついてｘj＝ｙjなので、ｘ＞ｙであり、ｘ≤ｙに反する。
したがって、ｘi＝ｙiである。
任意の1≤i≤ｎについて、これは成り立つので、ｘ＝ｙである。
対偶をとり、ｘ≠ｙ ⇒ ｘ＜ｙ又はｘ＞ｙ である。
したがって、Ｄn,[k]の元はこの順序によって一列に並べることができる。
つまり、あるｘ∋Ｄn,[k]より小さな元で最大の元（下限）は、ただ一つあるか、一つもないかのどちらかである。
そのため、Ｄn,[k]の最大元から初めて、その元よりも小さな元の最大元（下限）を探して、最小元まで列挙していけば、
Ｄn,[k]のすべての元を列挙したことになる。

次に、その方法、Ｄn,[k]の元を昇順に計算する方法を示す。
以下の計算方法をＨアルゴリズムと呼ぶことにする。

1.開始点をｘ1として総和kについて基準lで割って最大化を行う。
最大化とは、総和を基準で割って、開始点より商の分だけ基準量を並べた後に余りを置くこと。
「2」にいく。

2.右端からｘi≥2なるｘiを探す。
左端まで対象のｘiがなければ終了する。
対象のｘiがあれば、「3」にいく。

3.ｘiから1を引き、ｘi+1を開始点とし、ｘi+1以降の成分の和に1を足した数を総和とし、1を引いたｘiの値を基準にして、最大化を行う。（つまり、ｘiからｘi+1に1を移して、最大化を行う。）
ただし、最大化で並べる成分がnを超えた場合には、操作を取り消して、ｘi-1より「2」の探索を再開する。
そうでなければ、最大化後に「2」に戻る。

【証明】
「1」により計算される元がＤn,[k]の最大元であることは明らか。
任意の元ｘ∈Ｄn,[k]について、ｘ＞ｙ,ｚとし、
ｘとｙの順序を決める成分をmy、ｘとｚの順序を決める成分をmzとすれば、
my＜mzであれば、1≥i≥my,ｚi＝ｘiであり、ｚmy＝ｘmy＞ｙmyなので、ｚ＞ｙである。
したがって、ｘ＞ｚを満たす最大元ｚは、ｘとｚの順序を決める成分mzが1≤mz≤ｎで最大の必要がある。
次に、最大元ｚはmzにおいて、ｘmz＞ｚmzなので、ｘi≥2でなければならない。
さもなければ、ｚmy＝0であるのにｚmy+1以降の総和が1以上であり、Ｄn,[k]の元が左昇順であることに矛盾する。
さらに、ｘmz＝ｚmz＋１でなければならない。なぜなら、ｘmz＝ｚmz＋２以下を満たす元があるとすると、
少なくともｚmy+1以降の総和は2以上であり、そのいくつかをｚmzに移動してｘmz＝ｚmz＋１とすることができ、
ｘmz＝ｚmz＋１を満たす元は、ｘmz＝ｚmz＋２以下を満たす元よりも大きい。
そして、ｚmy+1以降はｚmyを基準に最大化されている必要がある。
一方、ｚmy+1以降がｚmyを基準に最大化した元が成分の制限ｎに入りきらなければ、それより小さなｘmz＝ｚmz＋１を満たす元はすべて制限ｎを超えるので存在しない。そのため、最大化された元の有無を調べるので足りる。
したがって、これらの条件を満たす1≤mz≤ｎで最大の成分mzを右端からさがせば良い。　　　□

例：n=6,l=4,k=10
(4,4,2,0,0,0)
(4,4,1,1,0,0)
(4,3,3,0,0,0)
(4,3,2,1,0,0)
(4,3,1,1,1,0)
(4,2,2,2,0,0)
(4,2,2,1,1,0)
(4,2,1,1,1,1)
(3,3,3,1,0,0)
(3,3,2,2,0,0)
(3,3,2,1,1,0)
(3,3,1,1,1,1)
(3,2,2,2,1,0)
(3,2,2,1,1,1)
(2,2,2,2,2,0)
(2,2,2,2,1,1)

Ｈアルゴリズムにより、Ｄn,[k]を計算できたので、
あとは、ＥＸn,[k]の各同値類の要素数を求めればよい。

「４．格子点の構造」の「格子点集合の定義」の議論と同様に、
Ｈx＝｛σ∈Ｓn｜ｘ＝σ(ｘ)｝とすると、
ＨxはＳnの部分群であり、ｘの同値類をＲxとすると、
ｎ!＝n(Ｒx)n(Ｈx)である。
したがって、n(Ｒx)＝ｎ!／n(Ｈx)であり、
n(Ｈx)は、ｘの同じ成分の階乗のかけ算で計算できる。

例：n=6,l=4,k=10
(4,4,2,0,0,0) 6!／2!1!3!
(4,4,1,1,0,0) 6!／2!2!2!
(4,3,3,0,0,0) 6!／1!2!3!
(4,3,2,1,0,0) 6!／1!1!1!1!2!
(4,3,1,1,1,0) 6!／1!1!3!1!
(4,2,2,2,0,0) 6!／1!3!2!
(4,2,2,1,1,0) 6!／1!2!2!1!
(4,2,1,1,1,1) 6!／1!1!4!
(3,3,3,1,0,0) 6!／3!1!2!
(3,3,2,2,0,0) 6!／2!2!2!
(3,3,2,1,1,0) 6!／2!1!2!1!
(3,3,1,1,1,1) 6!／2!4!
(3,2,2,2,1,0) 6!／1!3!1!1!
(3,2,2,1,1,1) 6!／1!2!3!
(2,2,2,2,2,0) 6!／5!1!
(2,2,2,2,1,1) 6!／4!2!

以上より、
nlが奇数ならば、k=0から(nl-1)/2まで調べてそれを2倍する、
nlが偶数ならば、k=0からnl/2まで調べて、nl/2-1までを2倍し、nl/2と足す。
これによってべき乗の計算ができる。

例：n=3,l=4
(4+1)^3=125
nl=12、偶数
0≤k≤6を調べて、0≤k≤5を2倍し、k=6を足す。

k=0
(0,0,0) 3!/3!=1
k=1
(1,0,0) 3!/1!2!=3
k=2
(2,0,0) 3!/1!2!=3
(1,1,0) 3!/2!1!=3
total=6
k=3
(3,0,0) 3!/1!2!=3
(2,1,0) 3!/1!1!1!=6
(1,1,1) 3!/3!=1
total=10
k=4
(4,0,0) 3!/1!2!=3
(3,1,0) 3!/1!1!1!=6
(2,2,0) 3!/2!1!=3
(2,1,1) 3!/1!2!=3
total=15
k=5
(4,1,0) 3!/1!1!1!=6
(3,2,0) 3!/1!1!1!=6
(3,1,1) 3!/1!2!=3
(2,2,1) 3!/2!1!=3
total=18
k=6
(4,2,0) 3!/1!1!1!=6
(4,1,1) 3!/1!2!=3
(3,3,0) 3!/2!1!=3
(3,2,1) 3!/1!1!1!=6
(2,2,2) 3!/3!=1
total=19

(1+3+6+10+15+18)×2+19＝125

１２-２．多項定理について

上記において、組合せ格子点集合を断面とせずに、
直接、べき乗の格子点集合Ｅn,lに対して、ｎ次対称群Ｓnの同値類を取り、
左昇順の元を代表元として、その集合をＤnとすれば、
任意のｘ∈Ｄnについて、各成分ｘiは0≤ｘi≤ｌであり、
ｘi＝j,(ｌ≥j≥0)を満たす成分ｘiの個数をｔj(0≤ｔj≤ｎ)とすると、
その同値類の要素数は、
n(Ｒx)＝ｎ!／n(Ｈx)＝ｎ!／ｔl!ｔl-1!・・・ｔ1!ｔ0! ・・・【式１３】
(ｔl+ｔl-1+・・・+ｔ1+ｔ0＝ｎ)
となる。
そこで、
Ｔn＝｛ｔ｜ｔ＝(ｔl,ｔl-1,・・・,ｔ1,ｔ0),ｔl+ｔl-1+・・・+ｔ1+ｔ0＝ｎ,0≤ｔj≤ｎ(ｌ≥j≥0)｝ ・・・【式１４】
として、写像τを、
τ Ｄn → Ｔn
　ｘ　→　ｔ （ｘi＝j,(ｌ≥j≥0)を満たす成分ｘiの個数をｔj(0≤ｔj≤ｎ)とする）
とする。
すると、Ｄnは左昇順の元の集合なので、τは双射になる。
ｔ∈ＴnがＴnのすべての元を動けば、ｘ∈ＤnもＤnのすべての元を動く。
したがって、【式１３】をすべてのｔ∈Ｔnについて足し合わせれば、Ｅn,lの要素数となる。
これは、つまり、多項定理を示している。

多項定理の効率的な計算法

多項定理は、ｔ∈Ｔnのすべての元について【式１３】を計算して和を取る必要があるが、
実際には同じ要素数の同値類が多数存在する。それらをまとめる規則を紹介する。

まず、Ｈアルゴリズムの計算対象を簡潔に示すために、
べき乗格子点集合Ｅn,lのｎ次対称群Ｓnでの同値類の左昇順の元を代表元として、その集合をＤn,lとし、
その成分の総和がｋ(∑[i:1→n]ｘi＝ｋ）の格子点のみを要素としたＤn,lの部分集合をＤn,l,kとする。

ここで、【式１３】【式１４】を観察すればｔi＝ｔjは交換可能であり、
そこで、Ｔnを格子点集合として考えれば、
ｌ+1次対称群Ｓl+1の各同値類について【式１３】の値は等しく、
各代表元の【式１３】の値に同値類の要素数n(Ｒt)を掛けて総和を計算すれば、
n(Ｅn,l)が計算できると分かる。つまり、n(Ｅn,l)＝∑n(Ｒx)×n(Ｒt)である。
さらに、Ｔnを格子点集合として考えるので、
各代表元は、Ｄl+1,n,nをＨアルゴリズムの対象として計算すればよい。

さらに工夫すると、ｎがいくつのｔj≥1によって分けられているか、
つまり、いくつの項の和で分けられているかによってＤl+1,n,nを場合分けすれば、
たとえば、ｓ個(1≤ｓ≤min(l+1,n))に分けられているとすると、
そのｓ個にｔl〜ｔ0を並べる順列を考えれば良い。
ただし、分かれた項が同数の場合には、その箇所の順序を割り引く必要がある。
例：
ｎ＝10、ｌ＝3、３個に分けられている場合は、
(6,2,2)
(5,3,2)
(4,3,3)
があり、
(6,2,2)の場合は、4Ｐ3/2!通り
(5,3,2)の場合は、4Ｐ3通り
(4,3,3)の場合は、4Ｐ3/2!通り

そこで次に、ｎがi個のｔj≥1によって分けられているようなＤl+1,n,nの元の計算の仕方を示す。
まず、Ｄl+1,n,nにおいて、ｘi≥1なる成分がi≤ｕのみにある部分集合をＤl+1,n,n,i≤uとし、
i≤ｕを満たす全ての成分がｘi≥1で、i＞ｕを満たす全ての成分がｘi＝0である部分集合をＤl+1,n,n,uとする。
Ｄl+1,n,n,i≤u − Ｄl+1,n,n,i≤u-1 ⊂ Ｄl+1,n,n,uであり、
Ｄl+1,n,n,i≤u-1 ∩ Ｄl+1,n,n,u ＝ ∅なので、Ｄl+1,n,n,i≤u − Ｄl+1,n,n,i≤u-1 ＝ Ｄl+1,n,n,u
つまり、Ｄl+1,n,n,i≤u＝∪[i:0→u]Ｄl+1,n,n,iであり、
i≠jならばＤl+1,n,n,i∩Ｄl+1,n,n,j＝∅になる。
したがって、各Ｄl+1,n,n,i(1≤i≤min(l+1,n))を調べればよい。
ここで、Ｄ’l+1,n,n,i＝｛ｔ’｜ｔ’＝(ｔ0ー1,ｔ1ー1,・・・,ｔi-1ー1,ｔiー1)、ｔ∈Ｄl+1,n,n,i｝とすると、
Ｄ’l+1,n,n,iとＤi,n-1,n-iとの間に双射写像があることが分かる。
（なぜなら、Ｄl+1,n,n,iとＤi,n-1,n-iはともに左昇順だから。）
つまり、Ｄi,n-1,n-iを1≤i≤min(l+1,n)についてＨアルゴリズムで調べれば良いことが分かる。

以上について、まとめると、
Ｄi,n-1,n-iを1≤i≤min(l+1,n)についてＨアルゴリズムで調べ、
Ｄl+1,n,n,iに直して、Ｄl+1,n,n,iの各代表元の【式１３】にｔl〜ｔ0を並べる順列の数を掛けて、
総和を計算すればよいことが分かった。

例：n=3,l=4
(4+1)^3=125
1≤i≤min(4+1,3)=3
i=1,2,3

i=1
Ｄ1,2,2 → Ｄ5,3,3,1
(2) → (3,0,0,0,0)
n(Ｒx)=3!/3!0!0!0!0!=1
4+1Ｐ1=5
n(Ｒx)×4+1Ｐ1=5
ちなみに、
n(Ｒt)=5!/1!4!=5
n(Ｒx)×n(Ｒt)=5

i=2
Ｄ2,2,1 → Ｄ5,3,3,2
(1,0) → (2,1,0,0,0)
n(Ｒx)=3!/2!1!0!0!0!=3
4+1Ｐ2=20
n(Ｒx)×4+1Ｐ2=60
ちなみに、
n(Ｒt)=5!/1!1!3!=20
n(Ｒx)×n(Ｒt)=60

i=3
Ｄ3,2,0 → Ｄ5,3,3,3
(0,0,0) → (1,1,1,0,0)
n(Ｒx)=3!/1!1!1!0!0!=6
4+1Ｐ3/3!=10
n(Ｒx)×4+1Ｐ3/3!=60
ちなみに、
n(Ｒt)=5!/3!2!=10
n(Ｒx)×n(Ｒt)=60

n(Ｅn,l)＝5+60+60=125
ちなみに、
n(Ｅn,l)＝∑n(Ｒx)×n(Ｒt)＝5+60+60=125

例：n=4,l=5
(5+1)^4=1296
1≤i≤min(5+1,4)=4
i=1,2,3,4

Ｄi,n-1,n-i Ｄl+1,n,n,i
i=1
Ｄ1,3,3 → Ｄ6,4,4,1
(3) → (4,0,0,0,0,0)
n(Ｒx)=4!/4!0!0!0!0!0!=1
5+1Ｐ1=6
n(Ｒx)×5+1Ｐ1=6

i=2
Ｄ2,3,2 → Ｄ6,4,4,2
(2,0) → (3,1,0,0,0,0)
n(Ｒx)=4!/3!1!0!0!0!0!=4
5+1Ｐ2=30
n(Ｒx)×5+1Ｐ2=120
(1,1) → (2,2,0,0,0,0)
n(Ｒx)=4!/2!2!0!0!0!0!=6
5+1Ｐ2/2!=15
n(Ｒx)×5+1Ｐ2/2!=90

i=3
Ｄ3,3,1 → Ｄ6,4,4,3
(1,0,0) → (2,1,1,0,0,0)
n(Ｒx)=4!/2!1!1!0!0!0!=12
5+1Ｐ3/2!=60
n(Ｒx)×5+1Ｐ3/2!=720

i=4
Ｄ4,3,0 → Ｄ6,4,4,4
(0,0,0,0) → (1,1,1,1,0,0)
n(Ｒx)=4!/1!1!1!1!0!0!=24
5+1Ｐ4/4!=15
n(Ｒx)×5+1Ｐ4/4!=360

6+120+90+720+360=1296

１２-３．(ｌ＋1)^nと(ｎ＋1)^lの関係性

n(Ｅn,l)＝(ｌ＋1)^nだった。
ｘ∈Ｄnを観察すると、ｘの成分を座標に、座標を成分として考えても、
左昇順が保たれていることに気づく。
つまり、Ｅn,lとＥl,nには共通点がある。このことを以下に説明する。

ＳnによるＥl,nの同値類の左昇順の元について、その集合をＤ’nとする。
ｘ∈Ｄnとして、写像fを、
f: Ｄn → Ｄ’n
　　ｘ → ｙ
ただし、
1≤j≤lについて、ｘi≥jなる最大のiをｋとして、ｙj＝ｋ(0≤ｙj≤n,iがないときは0)
とする。

たしかに、1≤j＜j’≤lとして、
仮にｙj＜ｙj’とすると、ｘyj’があってｘyj’≥j’であり、したがってｘyj’≥j’＞jであり、
ｙjはｘi≥jなる最大のiなので、ｙj≥ｙj’、これは仮定と矛盾する。
したがって、ｙj≥ｙj’であり、ｙは左昇順となっているので、写像fは定義できる。

ｘ≠ｘ’,ｘi＜ｘ’iとして、ｘi＝ｘmを満たす最大のmを取ると、ｙ＝f(ｘ)としてｙxm＝ｍである。
ＤnとＤ’nは左昇順の元の集合なので、ｙxm+1＜ｍとなる。したがって、f(ｘ)≠f(ｘ’)となり、fは単射である。

f’をfと同様にＤ’n → Ｄnに定義すれば、やはりf’は単射なのでfは全射であり、双射である。

つまり、Ｅn,lのＤnとＥl,nのＤ’nは双射写像fにより変換できる。

例：
先程の例、
n=3,l=4
(4+1)^3=125
nl=12、偶数
0≤k≤6を調べて、0≤k≤5を2倍し、k=6を足す。
と
n=4,l=3
(3+1)^4=256
nl=12、偶数
0≤k≤6を調べて、0≤k≤5を2倍し、k=6を足す。
の変換を行う。

k=0
(0,0,0) → (0,0,0,0) 4!/4!=1
k=1
(1,0,0) → (1,0,0,0) 4!/1!3!=4
k=2
(2,0,0) → (1,1,0,0) 4!/2!2!=6
(1,1,0) → (2,0,0,0) 4!/1!3!=4
total=10
k=3
(3,0,0) → (1,1,1,0) 4!/3!1!=4
(2,1,0) → (2,1,0,0) 4!/1!1!2!=12
(1,1,1) → (3,0,0,0) 4!/1!3!=4
total=20
k=4
(4,0,0) → (1,1,1,1) 4!/4!=1
(3,1,0) → (2,1,1,0) 4!/1!2!1!=12
(2,2,0) → (2,2,0,0) 4!/2!2!=6
(2,1,1) → (3,1,0,0) 4!/1!1!2!=12
total=31
k=5
(4,1,0) → (2,1,1,1) 4!/1!3!=4
(3,2,0) → (2,2,1,0) 4!/2!1!1!=12
(3,1,1) → (3,1,1,0) 4!/1!2!1!=12
(2,2,1) → (3,2,0,0) 4!/1!1!2!=12
total=40
k=6
(4,2,0) → (2,2,1,1) 4!/2!2!=6
(4,1,1) → (3,1,1,1) 4!/1!3!=4
(3,3,0) → (2,2,2,0) 4!/3!1!=4
(3,2,1) → (3,2,1,0) 4!/1!1!1!1!=24
(2,2,2) → (3,3,0,0) 4!/2!2!=6
total=44

(1+4+10+20+31+40)×2+44＝256

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