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の関係性

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

9.格子点を用いた組合せの展開式

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

【証明】
Xn,lを観察すると、任意のxiは0又は1以上であることが分かる。
そこで、1以上であるxiの個数j(0≤j≤min(n,l))によってXn,lを分解する。
つまり、写像hを、
h:x → 「1以上であるxiの個数」
として、
Xn,l,j={x|x=(x1,x2,・・・xn-1,xn), 0≤∑[i:1→n]xi≤l, h(x)=j}
とすると、
Xn,l=∪[j:0→m]Xn,l,j
である。
さらに、Xn,l,jについて観察すると、
xにおいて、1以上であるxiの並び順は、nCj個あり、
その一つの並びにおいて、1以上であるxiに残りのl-jを並べた格子点集合Yn,l,jと、
j次元空間の原点から距離l-jまでにある格子点集合Xj,l-jには、双射写像を定義できる。
そこで、
n(Yn,l,j)=n(Xj,l-j)=j+(l-j)Cj=lCj
となり、したがって、
n(Xn,l,j)=nCj×n(Yn,l,j)=nCj×lCj
であり、
n+lCl=n(Xn,l)=n(∪[j:0→m]Xn,l,j)=∑[j:0→m]n(Xn,l,j)=∑[j:0→m]nCj×lCj   □

10.格子点を用いたべき乗と組合せの関係式

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

【証明】
Pn,l={x|x=(x1,x2,・・・xn-1,xn), 0≤xi≤l(1≤i≤n)}とする。
つまりl≥0において、n(Pn,l)=(l+1)^nである。
先程と同様に写像hを、
h:x → 「1以上であるxiの個数」
とする。
Pn,l,j={x|x=(x1,x2,・・・xn-1,xn), 0≤xi≤l(1≤i≤n), h(x)=j}とすると、
n(Pn,l,j)=nCj×l^jであり、
Pn,l=∪[j:0→n]Pn,l,jなので、
(l+1)^n=n(Pn,l)=∑[j:0→n]n(Pn,l,j)=∑[j:0→n]nCj×l^j
ここで、l+1=l’と置き直せばよい。   □

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

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

これは格子点集合を題材にして求めた関係式ではなく、ただ式変形によって導いた関係式だが紹介しておく。
l^n=∑[i:1→n](i!×l-1Ci-1×l^(n-i))+n!×l-1Cn
ただし、q>pならば、pCq=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$$
となる。

【証明】
l^n=(l-1)l^(n-1)+l^(n-1)=(l-1)l^(n-1)+1!×l-1C0×l^(n-1)
(l-1)l^(n-1)=(l-1)(l-2)l^(n-2)+2(l-1)l^(n-2)=(l-1)(l-2)l^(n-2)+2!×l-1C1×l^(n-2)
(l-1)(l-2)l^(n-2)=(l-1)(l-2)(l-3)l^(n-3)+3(l-1)(l-2)l^(n-3)=(l-1)(l-2)(l-3)l^(n-3)+3!×l-1C2×l^(n-3)
  ・
  ・
  ・
(l-1)(l-2)…(l-(n-2))(l-(n-1))l^(n-1)=(l-1)(l-2)…(l-(n-1))(l-n)l^(n-n)+n(l-1)(l-2)…(l-(n-1))l^(n-n)=n!×l-1Cn+n!×l-1Cn-1
であり、先頭の式に次式以降を次々に代入していけばよい。   □

12.べき乗の格子点の構造と計算法

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

12-1.組合せ格子点集合を断面とする計算法

べき乗の格子点集合En,lを、
En,l={x|x=(x1,x2,・・・,xn-1,xn), 0≤xi≤l}
と考える。つまり、n(En,l)=(l+1)^nである。(n≥1,l≥0)
組合せの格子点集合Xn,lは、
Xn,l={x|x=(x1,x2,・・・,xn-1,xn), 0≤∑[i:1→n]xi≤l}
であった。つまり、n(Xn,l)=n+lClが成り立つ。

そこで、En,lをXn,lで分解できれば、べき乗の組合せによる展開式ができる。
しかし、それはなかなか難しく、逆にEn,l⊂Xn,nlであることは容易に分かる。
かといって、Xn,nlをEn,lで分解することも難しそうだ。
ここでは、Xn,nlを、
Xn,[k]={x|x=(x1,x2,・・・,xn-1,xn), ∑[i:1→n]xi=k}
(ただし、[k]はkを固定していることを表すとする。)
として、
Xn,nl=∪[k:0→nl]Xn,[k]
のように分解したことを思い出し、
EXn,[k]=En,l∩Xn,[k]={x|x=(x1,x2,・・・,xn-1,xn), 0≤xi≤l, ∑[i:1→n]xi=k}
として、
En,l=∪[k:0→nl]EXn,[k]
と分解しょう。

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

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

Hアルゴリズム

「4.格子点の構造」の「格子点集合の対称性」では、格子点集合に置換を定義したが、
ここでは、格子点に対するn次対称群Snによる置換を考えて、
En,lに、対称関係を以下のように定義する。
x,y∈En,lについて、
x∼y ⇔ ∃σ∈Sn, σ(x)=y

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

EXn,[k]の各同値類のすべての代表元の集合をDn,[k]⊂EXn,[k]とし、
x,y∈Dn,[k]、I={i|1≤i≤n, xi>yi又はxi<yi}として、
Iの最小元m=min(I)について、xm>ym ⇒ x>y
(つまり、より左にある成分の大きさを優先順位が高いものとして考える。)
という順序をDn,[k]に定める。これは全順序である。
さらに、x≥yかつx≤yであれば、
x≥yより、ある1≤i≤nがあって、1≤j<iついてxj=yjであり、xi≥yiである。
仮に、xi>yiとすると、1≤j<iついてxj=yjなので、x>yであり、x≤yに反する。
したがって、xi=yiである。
任意の1≤i≤nについて、これは成り立つので、x=yである。
対偶をとり、x≠y ⇒ x<y又はx>y である。
したがって、Dn,[k]の元はこの順序によって一列に並べることができる。
つまり、あるx∋Dn,[k]より小さな元で最大の元(下限)は、ただ一つあるか、一つもないかのどちらかである。
そのため、Dn,[k]の最大元から初めて、その元よりも小さな元の最大元(下限)を探して、最小元まで列挙していけば、
Dn,[k]のすべての元を列挙したことになる。

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

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

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

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

【証明】
「1」により計算される元がDn,[k]の最大元であることは明らか。
任意の元x∈Dn,[k]について、x>y,zとし、
xとyの順序を決める成分をmy、xとzの順序を決める成分をmzとすれば、
my<mzであれば、1≥i≥my,zi=xiであり、zmy=xmy>ymyなので、z>yである。
したがって、x>zを満たす最大元zは、xとzの順序を決める成分mzが1≤mz≤nで最大の必要がある。
次に、最大元zはmzにおいて、xmz>zmzなので、xi≥2でなければならない。
さもなければ、zmy=0であるのにzmy+1以降の総和が1以上であり、Dn,[k]の元が左昇順であることに矛盾する。
さらに、xmz=zmz+1でなければならない。なぜなら、xmz=zmz+2以下を満たす元があるとすると、
少なくともzmy+1以降の総和は2以上であり、そのいくつかをzmzに移動してxmz=zmz+1とすることができ、
xmz=zmz+1を満たす元は、xmz=zmz+2以下を満たす元よりも大きい。
そして、zmy+1以降はzmyを基準に最大化されている必要がある。
一方、zmy+1以降がzmyを基準に最大化した元が成分の制限nに入りきらなければ、それより小さなxmz=zmz+1を満たす元はすべて制限nを超えるので存在しない。そのため、最大化された元の有無を調べるので足りる。
したがって、これらの条件を満たす1≤mz≤nで最大の成分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)

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

「4.格子点の構造」の「格子点集合の定義」の議論と同様に、
Hx={σ∈Sn|x=σ(x)}とすると、
HxはSnの部分群であり、xの同値類をRxとすると、
n!=n(Rx)n(Hx)である。
したがって、n(Rx)=n!/n(Hx)であり、
n(Hx)は、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

12-2.多項定理について

上記において、組合せ格子点集合を断面とせずに、
直接、べき乗の格子点集合En,lに対して、n次対称群Snの同値類を取り、
左昇順の元を代表元として、その集合をDnとすれば、
任意のx∈Dnについて、各成分xiは0≤xi≤lであり、
xi=j,(l≥j≥0)を満たす成分xiの個数をtj(0≤tj≤n)とすると、
その同値類の要素数は、
n(Rx)=n!/n(Hx)=n!/tl!tl-1!・・・t1!t0! ・・・【式13】
(tl+tl-1+・・・+t1+t0=n)
となる。
そこで、
Tn={t|t=(tl,tl-1,・・・,t1,t0),tl+tl-1+・・・+t1+t0=n,0≤tj≤n(l≥j≥0)} ・・・【式14】
として、写像τを、
τ Dn → Tn
 x → t (xi=j,(l≥j≥0)を満たす成分xiの個数をtj(0≤tj≤n)とする)
とする。
すると、Dnは左昇順の元の集合なので、τは双射になる。
t∈TnがTnのすべての元を動けば、x∈DnもDnのすべての元を動く。
したがって、【式13】をすべてのt∈Tnについて足し合わせれば、En,lの要素数となる。
これは、つまり、多項定理を示している。

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

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

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

ここで、【式13】【式14】を観察すればti=tjは交換可能であり、
そこで、Tnを格子点集合として考えれば、
l+1次対称群Sl+1の各同値類について【式13】の値は等しく、
各代表元の【式13】の値に同値類の要素数n(Rt)を掛けて総和を計算すれば、
n(En,l)が計算できると分かる。つまり、n(En,l)=∑n(Rx)×n(Rt)である。
さらに、Tnを格子点集合として考えるので、
各代表元は、Dl+1,n,nをHアルゴリズムの対象として計算すればよい。

さらに工夫すると、nがいくつのtj≥1によって分けられているか、
つまり、いくつの項の和で分けられているかによってDl+1,n,nを場合分けすれば、
たとえば、s個(1≤s≤min(l+1,n))に分けられているとすると、
そのs個にtl〜t0を並べる順列を考えれば良い。
ただし、分かれた項が同数の場合には、その箇所の順序を割り引く必要がある。
例:
n=10、l=3、3個に分けられている場合は、
(6,2,2)
(5,3,2)
(4,3,3)
があり、
(6,2,2)の場合は、4P3/2!通り
(5,3,2)の場合は、4P3通り
(4,3,3)の場合は、4P3/2!通り

そこで次に、nがi個のtj≥1によって分けられているようなDl+1,n,nの元の計算の仕方を示す。
まず、Dl+1,n,nにおいて、xi≥1なる成分がi≤uのみにある部分集合をDl+1,n,n,i≤uとし、
i≤uを満たす全ての成分がxi≥1で、i>uを満たす全ての成分がxi=0である部分集合をDl+1,n,n,uとする。
Dl+1,n,n,i≤u − Dl+1,n,n,i≤u-1 ⊂ Dl+1,n,n,uであり、
Dl+1,n,n,i≤u-1 ∩ Dl+1,n,n,u = ∅なので、Dl+1,n,n,i≤u − Dl+1,n,n,i≤u-1 = Dl+1,n,n,u
つまり、Dl+1,n,n,i≤u=∪[i:0→u]Dl+1,n,n,iであり、
i≠jならばDl+1,n,n,i∩Dl+1,n,n,j=∅になる。
したがって、各Dl+1,n,n,i(1≤i≤min(l+1,n))を調べればよい。
ここで、D’l+1,n,n,i={t’|t’=(t0ー1,t1ー1,・・・,ti-1ー1,tiー1)、t∈Dl+1,n,n,i}とすると、
D’l+1,n,n,iとDi,n-1,n-iとの間に双射写像があることが分かる。
(なぜなら、Dl+1,n,n,iとDi,n-1,n-iはともに左昇順だから。)
つまり、Di,n-1,n-iを1≤i≤min(l+1,n)についてHアルゴリズムで調べれば良いことが分かる。

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

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

i=1
D1,2,2 → D5,3,3,1
(2) → (3,0,0,0,0)
n(Rx)=3!/3!0!0!0!0!=1
4+1P1=5
n(Rx)×4+1P1=5
ちなみに、
n(Rt)=5!/1!4!=5
n(Rx)×n(Rt)=5

i=2
D2,2,1 → D5,3,3,2
(1,0) → (2,1,0,0,0)
n(Rx)=3!/2!1!0!0!0!=3
4+1P2=20
n(Rx)×4+1P2=60
ちなみに、
n(Rt)=5!/1!1!3!=20
n(Rx)×n(Rt)=60

i=3
D3,2,0 → D5,3,3,3
(0,0,0) → (1,1,1,0,0)
n(Rx)=3!/1!1!1!0!0!=6
4+1P3/3!=10
n(Rx)×4+1P3/3!=60
ちなみに、
n(Rt)=5!/3!2!=10
n(Rx)×n(Rt)=60

n(En,l)=5+60+60=125
ちなみに、
n(En,l)=∑n(Rx)×n(Rt)=5+60+60=125

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

Di,n-1,n-i Dl+1,n,n,i
i=1
D1,3,3 → D6,4,4,1
(3) → (4,0,0,0,0,0)
n(Rx)=4!/4!0!0!0!0!0!=1
5+1P1=6
n(Rx)×5+1P1=6

i=2
D2,3,2 → D6,4,4,2
(2,0) → (3,1,0,0,0,0)
n(Rx)=4!/3!1!0!0!0!0!=4
5+1P2=30
n(Rx)×5+1P2=120
(1,1) → (2,2,0,0,0,0)
n(Rx)=4!/2!2!0!0!0!0!=6
5+1P2/2!=15
n(Rx)×5+1P2/2!=90

i=3
D3,3,1 → D6,4,4,3
(1,0,0) → (2,1,1,0,0,0)
n(Rx)=4!/2!1!1!0!0!0!=12
5+1P3/2!=60
n(Rx)×5+1P3/2!=720

i=4
D4,3,0 → D6,4,4,4
(0,0,0,0) → (1,1,1,1,0,0)
n(Rx)=4!/1!1!1!1!0!0!=24
5+1P4/4!=15
n(Rx)×5+1P4/4!=360

6+120+90+720+360=1296

12-3.(l+1)^nと(n+1)^lの関係性

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

SnによるEl,nの同値類の左昇順の元について、その集合をD’nとする。
x∈Dnとして、写像fを、
f: Dn → D’n
  x → y
ただし、
1≤j≤lについて、xi≥jなる最大のiをkとして、yj=k(0≤yj≤n,iがないときは0)
とする。

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

x≠x’,xi<x’iとして、xi=xmを満たす最大のmを取ると、y=f(x)としてyxm=mである。
DnとD’nは左昇順の元の集合なので、yxm+1<mとなる。したがって、f(x)≠f(x’)となり、fは単射である。

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

つまり、En,lのDnとEl,nのD’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