忍者ブログ

はしりがき

ガラパゴスへよおこそ。

[PR]

×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

エンジン基礎理論第二章第四節「n項重複」

二項重複、三項重複と進んできた流れを一般化して「n項重複」を考えよう。基本的な要素は「二項重複」「三項重複」で説明してあるから「具体的な数」を「変数」に書き換えるだけでよい。
まずはn項重複の基本的な構成について説明しよう。
第1ブロック、第2ブロック、……、第nブロックがあるとして、この中の1つの任意のブロックを指すとき、それを第δブロックと呼ぶことにする。そして第δブロックで埋め込むべきカードを総称してset(tarδ)と書く。
そしてそれらによって構成される素集合系が、その重複の度合い——「重複度」によって分類され、以下の表のようになる。

重複度 素集合系 個数
1 tar1,tar2,…,tarρ,…,tarn nC1
2 tar1∧2,tar1∧3,…,tar1∧n,tar2∧3,…,tar(n-1)∧n nC2
… … …
ρ tar1∧2∧…∧ρ,tar2∧3∧…∧(ρ+1),…,tar(n-ρ+1)∧(n-ρ+2)∧…∧n nCρ
… … …
n tar1∧2∧…∧n nCn

重複度ρに属する素集合系のうち任意の1つの素集合を取り出す際には、ρ個のブロックを選んでその両端をζ、ηと名付ける(といってもζからηまでは連番とは限らない)、という意味で(ζ...η)(ρ=ρ)と書き、その中で特にset(tarδ)に属しているものの中から任意の1つの素集合を取り出す際には(ζ...η)(ρ=ρ,set(tarδ))と書くことにする(見慣れないギリシャ文字はそれぞれζ(ツェータ)、η(イータ)、δ(デルタ)、ρ(ロー)と読む)。
これらの素集合の埋め込み枚数を問題にする際には先頭にjを付してj(ζ...η)(ρ=ρ,set(tarδ))と書く。任意の重複度、任意のブロックに属する素集合の埋め込み枚数はこれで記述できるわけだが、便宜上「ある規則で単位ブロックを並べた際の、直前の単位ブロックの埋め込み枚数」が必要になるため、これをjpre(ζ...η)(ρ=ρ,set(tarδ))と書くことにする。

n個のブロックによって構成されるブロック積を記述しよう。その際に2つほど注意を。n項重複においてはnの数に応じて単位ブロックの数が変わってくるので「一般形を記述しておいて範囲を指定する」という手法をとりたい。
たとえば第一ブロック内の重複度2の素集合系を記述する際には
Min[N(tar1∧2), i1-j10]
∑i1-j10Cj12*《N(tar1∧2), j12》*
j12=0

……*

Min[N((ζ...η)(ρ=2,set(tar1))), i1-j10-j12-...-jpre(ζ...η)(ρ=2,set(tar1))]
∑i1-j10-j12-...-j(ζ...η)(ρ=2,set(tar1))Cj(ζ...η)(ρ=2,set(tar1))*《N((ζ...η)(ρ=2,set(tar1))), j(ζ...η)(ρ=2,set(tar1))》*
j(ζ...η)(ρ=2,set(tar1))=0

……*

Min[N(tar1∧n), i1-j10-j12-...-j(ζ...η)(ρ=2,set(tar1))-...-j1(n-1)]
∑i1-j10-j12-j(ζ...η)(ρ=2,set(tar1))-...-j1(n-1)Cj1n*《N(tar1∧n), j1n》*
j1n=0

と本来書くべきところを、
Min[N((ζ...η)(ρ=2,set(tar1))), i1-j10-j12-...-jpre(ζ...η)(ρ=2,set(tar1))]
∑i1-j10-j12-...-j(ζ...η)(ρ=2,set(tar1))Cj(ζ...η)(ρ=2,set(tar1))*《N((ζ...η)(ρ=2,set(tar1))), j(ζ...η)(ρ=2,set(tar1))》*
j(ζ...η)(ρ=2,set(tar1))=0
 1≤ζ...η≤n
∑(ζ...η)=2

のように書くことにする。右側は「ζからηまでの各要素は1からnまでの間に収まる」「ζからηまでの個数すなわち重複度は2である」の意味。その範囲でとりうるすべての値の積の表現である。
また、第δブロックの単位ブロックによって埋め込まれるカードのうちset(tarδ)を含むようなものの枚数を∑jset(tarδ)と書くことにする。特に第δ'ブロックで埋め込まれたもののうちset(tarδ)を含むようなものの枚数を∑jδ'set(tarδ)と書く。さらに第δブロックへの影響は第1ブロック〜第δ-1ブロックの総和になるから、これを直前の記号「∑jδ'set(tarδ)」を用いて「∑∑j(1...δ-1)set(tarδ)」と書くことにする。
以上の約束に従ってn項重複を記述すると、
Min[μ-(n-1), N(set(tar1))]
∑      μCi1*
i1=1
 第1ブロックの
接続
Min[N(tar1), i1]
∑i1Cj10*《N(tar1), j10》*
j10=0		  
Min[N((ζ...η)(ρ=2,set(tar1))), i1-j10-j12-...-jpre(ζ...η)(ρ=2,set(tar1))]
∑i1-j10-j12-...-j(ζ...η)(ρ=2,set(tar1))Cj(ζ...η)(ρ=2,set(tar1))*《N((ζ...η)(ρ=2,set(tar1))), j(ζ...η)(ρ=2,set(tar1))》*
j(ζ...η)(ρ=2,set(tar1))=0
 		1≤ζ...η≤n
∑(ζ...η)=2
…… ……
Min[N((ζ...η)(ρ=ρ,set(tar1))), i1-j10-j12...-j1n...-jpre(ζ...η)(ρ=ρ,set(tar1))]
∑i1-j10-j12-...-j1n-...-jpre(ζ...η)(ρ=ρ,set(tar1))Cj(ζ...η)(ρ=ρ,set(tar1))*《N((ζ...η)(ρ=ρ,set(tar1))), j(ζ...η)(ρ=ρ,set(tar1))》*
j(ζ...η)(ρ=ρ,set(tar1))=0
 1≤ζ...η≤n
∑(ζ...η)=ρ
…… ……
Min[N((ζ...η)(ρ=n,set(tar1))), i1-j10-j12...-j1n...-jpre(ζ...η)(ρ=n,set(tar1))]
∑i1-j10-j12-...-j1n-...-jpre(ζ...η)(ρ=n,set(tar1))Cj(ζ...η)(ρ=n,set(tar1))*《N((ζ...η)(ρ=n,set(tar1))), j(ζ...η)(ρ=n,set(tar1))》
j(ζ...η)(ρ=n,set(tar1))=0
 1≤ζ...η≤n
∑(ζ...η)=n
 ∑i2=1Min[μ-i1-(n-2), N(set(tar2))-∑j1set(tar2)]μ-i1Ci2*
 第2ブロックの
接続
Min[N(tar2), i2]
∑i2Cj20*《N(tar2), j20》*
j20=0		  
Min[N((ζ...η)(ρ=2,set(tar2))), i2-j20-j21-...-jpre(ζ...η)(ρ=2,set(tar2))]
∑i2-j20-j21-...-j(ζ...η)(ρ=2,set(tar2))Cj(ζ...η)(ρ=2,set(tar2))*《N((ζ...η)(ρ=2,set(tar2))), j(ζ...η)(ρ=2,set(tar2))》*
j(ζ...η)(ρ=2,set(tar2))=0
 		1≤ζ...η≤n
∑(ζ...η)=2
……  
Min[N((ζ...η)(ρ=ρ,set(tar2))), i2-j20-j21...-j2n...-jpre(ζ...η)(ρ=ρ,set(tar2))]
∑i2-j20-j21-...-j2n-...-jpre(ζ...η)(ρ=ρ,set(tar2))Cj(ζ...η)(ρ=ρ,set(tar2))*《N((ζ...η)(ρ=ρ,set(tar2))), j(ζ...η)(ρ=ρ,set(tar2))》*
j(ζ...η)(ρ=ρ,set(tar2))=0
 		1≤ζ...η≤n
∑(ζ...η)=ρ
……  
Min[N((ζ...η)(ρ=n,set(tar2))), i2-j20-j21...-j2n...-jpre(ζ...η)(ρ=n,set(tar2))]
∑i2-j20-j22-...-j2n-...-jpre(ζ...η)(ρ=n,set(tar2))Cj(ζ...η)(ρ=n,set(tar2))*《N((ζ...η)(ρ=n,set(tar2))), j(ζ...η)(ρ=n,set(tar2))》
j(ζ...η)(ρ=n,set(tar2))=0
 		1≤ζ...η≤n
∑(ζ...η)=n
……  
∑iδ=1Min[μ-i1-i2...-i(δ-1), N(set(tarδ))-∑∑j(1...δ-1)set(tarδ)]μ-i1-i2...-i(δ-1)Ciδ*
 第δブロックの
接続
Min[N(tarδ), iδ]
∑iδCjδ0*《N(tarδ), jδ0》*
jδ0=0		  
Min[N((ζ...η)(ρ=2,set(tarδ))), iδ-jδ0-jδ1-...-jpre(ζ...η)(ρ=2,set(tarδ))]
∑iδ-jδ0-jδ1-...-j(ζ...η)(ρ=2,set(tarδ))Cj(ζ...η)(ρ=2,set(tarδ))*《N((ζ...η)(ρ=2,set(tarδ))), j(ζ...η)(ρ=2,set(tarδ))》*
j(ζ...η)(ρ=2,set(tarδ))=0
 1≤ζ...η≤n
∑(ζ...η)=2
……  
Min[N((ζ...η)(ρ=ρ,set(tarδ))), iδ-jδ0-jδ1-...-jpre(ζ...η)(ρ=ρ,set(tarδ))]
∑iδ-jδ0-jδ1-...-j(ζ...η)(ρ=ρ,set(tarδ))Cj(ζ...η)(ρ=ρ,set(tarδ))*《N((ζ...η)(ρ=ρ,set(tarδ))), j(ζ...η)(ρ=ρ,set(tarδ))》*
j(ζ...η)(ρ=ρ,set(tarδ))=0
 		1≤ζ...η≤n
∑(ζ...η)=ρ
……  
Min[N((ζ...η)(ρ=n,set(tarδ))), iδ-jδ0-jδ1-...-jpre(ζ...η)(ρ=n,set(tarδ))]
∑iδ-jδ0-jδ1-...-j(ζ...η)(ρ=n,set(tarδ))Cj(ζ...η)(ρ=n,set(tarδ))*《N((ζ...η)(ρ=n,set(tarδ))), j(ζ...η)(ρ=n,set(tarδ))》*
j(ζ...η)(ρ=n,set(tarδ))=0
 1≤ζ...η≤n
∑(ζ...η)=n
……  
∑in=1Min[μ-i1-i2...-i(n-1), N(set(tarn))-∑∑j(1...n-1)set(tarn)]μ-i1-i2...-i(n-1)Cin*
 第nブロックの
接続
Min[N(tarn), in]
∑inCjn0*《N(tarn), jn0》*
jn0=0		  
Min[N((ζ...η)(ρ=2,set(tarn))), in-jn0-jn1-...-jpre(ζ...η)(ρ=2,set(tarn))]
∑in-jn0-jn1-...-j(ζ...η)(ρ=2,set(tarn))Cj(ζ...η)(ρ=2,set(tarn))*《N((ζ...η)(ρ=2,set(tarn))), j(ζ...η)(ρ=2,set(tarn))》*
j(ζ...η)(ρ=2,set(tarn))=0
 1≤ζ...η≤n
∑(ζ...η)=2
……  
Min[N((ζ...η)(ρ=ρ,set(tarn))), in-jn0-jn1-...-jpre(ζ...η)(ρ=ρ,set(tarn))]
∑in-jn0-jn1-...-j(ζ...η)(ρ=ρ,set(tarn))Cj(ζ...η)(ρ=ρ,set(tarn))*《N((ζ...η)(ρ=ρ,set(tarn))), j(ζ...η)(ρ=ρ,set(tarn))》*
j(ζ...η)(ρ=ρ,set(tarn))=0
 1≤ζ...η≤n
∑(ζ...η)=ρ
……  
Min[N((ζ...η)(ρ=n,set(tarn))), in-jn0-jn1-...-jpre(ζ...η)(ρ=n,set(tarn))]
∑in-jn0-jn1-...-j(ζ...η)(ρ=n,set(tarn))Cj(ζ...η)(ρ=n,set(tarn))*《N((ζ...η)(ρ=n,set(tarn))), j(ζ...η)(ρ=n,set(tarn))》*
j(ζ...η)(ρ=n,set(tarn))=0
 1≤ζ...η≤n
∑(ζ...η)=n

さらに∑(ζ...η)=1から∑(ζ...η)=nまでをたたんで1≤∑(ζ...η)=ρ≤nと書くと
Min[μ-(n-1), N(set(tar1))]
∑      μCi1*
i1=1
 第1ブロックの
接続
Min[N((ζ...η)(ρ=ρ,set(tar1))), i1-j10-j12...-j1n...-jpre(ζ...η)(ρ=ρ,set(tar1))]
∑i1-j10-j12-...-j1n-...-jpre(ζ...η)(ρ=ρ,set(tar1))Cj(ζ...η)(ρ=ρ,set(tar1))*《N((ζ...η)(ρ=ρ,set(tar1))), j(ζ...η)(ρ=ρ,set(tar1))》*n-1Cρ-1
j(ζ...η)(ρ=ρ,set(tar1))=0
 1≤ζ...η≤n
1≤∑(ζ...η)=ρ≤n
……  
∑iδ=1Min[μ-i1-i2...-i(δ-1), N(set(tarδ))-∑∑j(1...δ-1)set(tarδ)]μ-i1-i2...-i(δ-1)Ciδ*
 第δブロックの
接続
Min[N((ζ...η)(ρ=ρ,set(tarδ))), iδ-jδ0-jδ1-...-jpre(ζ...η)(ρ=ρ,set(tarδ))]
∑iδ-jδ0-jδ1-...-j(ζ...η)(ρ=ρ,set(tarδ))Cj(ζ...η)(ρ=ρ,set(tarδ))*《N((ζ...η)(ρ=ρ,set(tarδ))), j(ζ...η)(ρ=ρ,set(tarδ))》*
j(ζ...η)(ρ=ρ,set(tarδ))=0
 1≤ζ...η≤n
1≤∑(ζ...η)=ρ≤n
……  
∑in=1Min[μ-i1-i2...-i(n-1), N(set(tarn))-∑∑j(1...n-1)set(tarn)]μ-i1-i2...-i(n-1)Cin*
 第nブロックの
接続
Min[N((ζ...η)(ρ=ρ,set(tarn))), in-jn0-jn1-...-jpre(ζ...η)(ρ=ρ,set(tarn))]
∑in-jn0-jn1-...-j(ζ...η)(ρ=ρ,set(tarn))Cj(ζ...η)(ρ=ρ,set(tarn))*《N((ζ...η)(ρ=ρ,set(tarn))), j(ζ...η)(ρ=ρ,set(tarn))》*
j(ζ...η)(ρ=ρ,set(tarn))=0
 1≤ζ...η≤n
1≤∑(ζ...η)=ρ≤n

さらに第1ブロックから第nブロックまでをたたんで1≤δ≤nと書くと
∑iδ=1Min[μ-i1-i2...-i(δ-1), N(set(tarδ))-∑∑j(1...δ-1)set(tarδ)]μ-i1-i2...-i(δ-1)Ciδ*
 第δブロックの接続
Min[N((ζ...η)(ρ=ρ,set(tarδ))), iδ-jδ0-jδ1-...-jpre(ζ...η)(ρ=ρ,set(tarδ))]
∑iδ-jδ0-jδ1-...-j(ζ...η)(ρ=ρ,set(tarδ))Cj(ζ...η)(ρ=ρ,set(tarδ))*《N((ζ...η)(ρ=ρ,set(tarδ))), j(ζ...η)(ρ=ρ,set(tarδ))》*
j(ζ...η)(ρ=ρ,set(tarδ))=0
 1≤δ≤n
1≤ζ...η≤n
1≤∑(ζ...η)=ρ≤n

と記述できる。

重複分を除する係数についての考察に入ろう。第1ブロック〜第nブロックの中から任意にρ個のブロックを選んだものを第sブロック〜第tブロックと書くと(必ずしも連番でない)、これらに対応するπ個の「tars∧...∧t」が埋め込まれたとき、その1つ1つについて第sブロック〜第tブロックの中第何ブロックの担当になるかというパターンがρ通りある。
このとき、第sブロック〜第tブロックの中の任意の1つのブロックを第xブロックと書くと、第xブロックのカード（つまりset(tarx)）でありtars∧…∧tではないカード、
set(tars)-tars∧...∧t
……
set(tarx)-tars∧...∧t
……
set(tart)-tars∧...∧t
(これが全部でρ個ある)
のうち、埋め込み枚数が0になるものの数を欠乏数ω（オメガ）と書くことにすると、重複分を除する係数Kは
K = 1/ρπ-ω

と書ける。これが重複度ρについてnCρ個存在し、ρが1からnまで動くから、π[(ζ...η)(ρ=ρ)]を任意の重複度ρの素集合の埋め込み枚数とすると、前と同様に「ζからηまでの各要素が1からnまで動く」「その個数すなわち重複度ρが1からnまで動く」ときの各係数の総積の範囲表現は
K = 1/ρ[π(ζ...η)(ρ=ρ)])-ω 1≤(ζ...η)≤n
1≤∑(ζ...η)=ρ≤n

となる。最後にすべてまとめると、n項重複の一般形は以下のように記述される。
∑iδ=1Min[μ-i1-i2...-i(δ-1), N(set(tarδ))-∑∑j(1...δ-1)set(tarδ)]μ-i1-i2...-i(δ-1)Ciδ*
 第δブロックの接続
Min[N((ζ...η)(ρ=ρ,set(tarδ))), iδ-jδ0-jδ1-...-jpre(ζ...η)(ρ=ρ,set(tarδ))]
∑iδ-jδ0-jδ1-...-j(ζ...η)(ρ=ρ,set(tarδ))Cj(ζ...η)(ρ=ρ,set(tarδ))*《N((ζ...η)(ρ=ρ,set(tarδ))), j(ζ...η)(ρ=ρ,set(tarδ))》*K
j(ζ...η)(ρ=ρ,set(tarδ))=0
 1≤δ≤n
1≤ζ...η≤n
1≤∑(ζ...η)=ρ≤n
K = 1/ρ[π(ζ...η)(ρ=ρ)])-ω 1≤(ζ...η)≤n
1≤∑(ζ...η)=ρ≤n

ただし、記号の意味は次の通り。
μ 全領域
δ 1≤δ≤nの任意の整数
set(tarδ) 第δブロックで埋め込むべき素集合の総和
∑∑j(1...δ-1)set(tarδ) 第1ブロック〜第δ-1ブロックにおける、set(tarδ)の減少枚数の総和
(ζ...η)(ρ=ρ,set(tarδ)) 重複度ρに属する素集合系のうちset(tarδ)に属している任意の1つの素集合
N() ()の中に入っている種類のカードのデッキ内初期枚数(最初何枚デッキに入っていたか)
ρ 重複度
ω 欠乏数
π[] []の中に入っている種類のカードの埋め込み枚数


第一稿
これ推敲するのめんどいよう
PR

Tips

「組み合わせ数学入門I」（C・L・リウ著、伊里正夫、伊里由美共訳、共立全書（共立出版））
「数え上げ組み合わせ論入門」（成嶋弘著、日評数学選書（日本評論社））
から使えそうな公式を抽出。

■スターリングの近似公式

n! ≒ √(2πn) * (n/e)^n
π：円周率
e：ネピアの数/自然対数の底

絶対誤差(差)はnの増大とともに増大するが、相対誤差(商)は単調減少するとのこと。確率では相対誤差のみが問題となるから、十分良い近似が得られる。
ちなみにn=40を放り込むと8.14217264 * 1047。これで40! = 8.15915283 * 1047を割ると1.00208546となる。
Wikipedia丸写しだけど、1+1/(12n)+1/(288n2)-139/(51840n3)を掛けてやることでさらに精度が上がるっぽい。計算すると8.15915283*1047だから信頼できそうか。

■母関数
勉強中

■第2種スターリング数
集合A(|A| = n)を{ Bi | ∨i=1kBi = A, Bi∧Bj = ø (i ≠ j) }に分割したとき、分割パターン数はnSkで表され、次のような式(漸化式と一般公式)を得る。
nSk = 1
 (k = 1,n)
nSk = n-1Sk-1 + k * n-1Sk
(2 ≤ k ≤n-1)
nSk = ∑i=0k(-1)i * (k-i)n / { i! * (k-i)! }

実際に使うのはB(n) = ∑k=1nnSkaのように総和をとったものだが、これについても次の漸化式

B(n+1) = ∑k=0nnCk* B(k)

が成立するみたい。一般式は分からなくても、プログラミングの都合上は漸化式で十分なんだよなー。

エンジン基礎理論第二章第三節「三項重複」

次はtar1,tar2,tar3をこの順番で埋めることを考える。項を増やすにあたって、いくつか規約を設けておきたい。

tar1 かつtar2でtar3が入らないようなものをtar1∧2\3と書いてきたが、これからはtar1∧2のように書いて、暗黙のうちに tar1とtar2以外の集合は排除するものとする。これに際して、本来の意味でのtar1∧2はtar1∧2∧3+tar1∧2のように表し、本来の意味でのtar1はtar1+tar1∧2+tar1∧3+tar1∧2∧3と書いてこれを改めてset(tar1)とする。
また、今まではtar1ブロック、tar2ブロック・・・のように書いてきたが、この書き方では誤解を招くから、第一ブロック、第二ブロック・・・という表現とする。
一番目の手法で作られたtar1、tar1∧2などはこれ以上分割できない。このような集合を素集合といい、複数の素集合をひっくるめて素集合系という。

さて本題。二項重複と同様の手法を用いて第一〜第三ブロックを展開するのだが、その前に素集合系を明らかにしておきたい。
tar1,tar2,tar3,
tar1∧2,tar2∧3,tar1∧3,
tar1∧2∧3。

実際に数式を展開しよう。長いので最上段を第一ブロック、上から二段目を第二ブロック、上から三段目を第三ブロックとしよう。最後の開いたブロックは省略。
∑i1=1Min[μ-2, N(tar1)]μCi1*《N(tar1), i1》   *   ∑i2=1Min[μ-i1-1, N(tar2)](μ-i1)Ci2*《N(tar2), i2》* ∑i3=1Min[μ-i1-i2, N(tar3)](μ-i1-i2)Ci3*《N(tar3), i3》
茶色部分を展開する。

↓
∑i1=1Min[μ-2, N(set(tar1))]μCi1*

∑j10=0Min[N(tar1), i1]i1Cj10*《N(tar1), j10》*

∑j12=0Min[N(tar1∧2), i1-j10]i1-j10Cj12*《N(tar1∧2), j12》*

∑j13=0Min[N(tar1∧3), i1-j10-j12]i1-j10-j12Cj13*《N(tar1∧3), j13》*

《N(tar1∧2∧3), i1- j10-j12-j13》		 上から、
第一ブロックの領域を確保する項
そこにtar1を埋める
残ったところにtar1∧2を埋める
残ったところにtar1∧3を埋める
残ったところに余すことなくtar1∧2∧3を埋める
∑i2=1Min[μ-i1-1, N(set(tar2))-(i1-j10-j13)]μ-i1Ci2*

∑j20=0Min[N(tar2), i2]i2Cj20*《N(tar1), j20》*

∑j21=0Min[N(tar1∧2)-(j12), i2-j20]i2-j20Cj21*《N(tar1∧2)-(j12), j21》*

∑j23=0Min[N(tar2∧3), i2-j20-j21]i2-j20-j21Cj23*《N(tar2∧3), j23》*

《N(tar1∧2∧3)-(i1-j10-j12-j13), i2- j20-j21-j23》		 上から、
第二ブロックの領域を確保する項
そこにtar2を埋める
残ったところにtar1∧2を埋める
残ったところにtar2∧3を埋める
残ったところに余すことなくtar1∧2∧3を埋める
∑i3=1Min[μ-i1-i2, N(set(tar3))-(i1-j10-j12)-(i2-j20-j21)]μ-i1-i2Ci3*

∑j30=0Min[N(tar3), i3]i3Cj30*《N(tar3), j30》*

∑j31=0Min[N(tar1∧3)-(j13), i3-j30]i3-j30Cj31*《N(tar1∧3)-(j13), j31》*

∑j32=0Min[N(tar2∧3)-(j23), i3-j30-j31]i3-j30-j31Cj32*《N(tar2∧3)-(j23), j32》*

《N(tar1∧2∧3)-(i1-j10-j12-j13)-(i2-j20-j21-j23), i3-j30-j31-j32》		 上から、
第三ブロックの領域を確保する項
そこにtar3を埋める
残ったところにtar1∧3を埋める
残ったところにtar2∧3を埋める
残ったところに余すことなくtar1∧2∧3を埋める
各四通りに分割。ここで一番上の「ブロックの領域を確保する項」を「接続」と呼ぶ。またtar1の埋め込み枚数はj10,tar1∧2はj12(於tar1ブロック)およびj21(於tar2ブロック)のように、jの後の数字とtarの番号を対応させている。
接続に含まれている各項は素集合を扱っているから、単位ブロックである。最低1枚は必ず埋め込む必要のあるブロックと、埋め込めなければ他のものでもいい 単位ブロックの違いがシグマの開始点の1か0かを左右する。上限は「埋め込む領域がなくなる（後続ブロックの事情も考慮）」か「埋め込むカードがなくなるか」の小さいほう。前のブロックによるデッキ内の枚数変化も考慮。
ここでどの種類のカードを何枚埋め込んだか(以後「埋め込み枚数」)は右の表の通りになる。
tar1 j10
tar2 j20
tar3 j30
tar1∧2 j12+j21
tar2∧3 j23+j32
tar1∧3 j13+j31
tar1∧2∧3 下記
  tar1∧2∧3は(i1-j10-j12-j13)+(i2-j20-j21-j23)+(i3-j30-j31-j32)

これに（三項重複の場合の）係数Kを加えて完成となる。
二項重複のときには重複領域が1つしかなかったが、三項重複は複数の重複領域が混在している。たとえば以下のような場合。

■■■■■■■■■■■■■■

■tar1
■tar2
■tar3
■tar1∧2
■tar2∧3

2個ある紫の領域について4倍の数え上げが行われるから、それを修正しなければならない——というのが前節の話であった。今回はそれに加え、黄色の領域2個についても同様のことが言えて、紫の個数・位置に無関係に起こるから4*4=16倍になっていることに注意する必要がある。
さらに次のパターン。

■■■■■■■■■■■■■■■■■■

■tar1
■tar2
■tar3
■tar1∧2
■tar2∧3
■tar1∧3
■tar1∧2∧3

紫の領域について4倍、黄色の領域について4倍、橙色の領域について4倍、黒色の領域については9倍である（3+3C2*2!）。ゆえに4*4*4*9=576倍。赤青緑の枚数による場合分けはもちろん必要だが、おおざっぱに概要を説明するとこうなる。
さらに一般化。

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

上記の展開式にならって埋め込み枚数を次のようにする。
tar1 j10 π[1]
tar2 j20 π[2]
tar3 j30 π[3]
tar1∧2 j12+j21 π[12]
tar2∧3 j23+j32 π[23]
tar1∧3 j13+j31 π[13]
tar1∧2∧3 下記 π[123]
tar1∧2∧3は(i1-j10-j12-j13)+(i2-j20-j21-j23)+(i3-j30-j31-j32)

tar1∧2に関する係数をK12
tar2∧3に関する係数をK23
tar1∧3に関する係数をK13
tar1∧2∧3に関する係数をK123
と書くと、tar1∧2,tar2∧3,tar1∧3については二項重複となり、π[1],π[2],π[3]≠0のときは前節と同じことが言えて、K12=1/2π[12], K13=1/2π[13], K23=1/2π[23]を得る。
しかしπ[1],π[2],π[3]のいずれかが0になるとき、二項重複にはない問題が露呈する。「tar1の埋め込み枚数が0のとき、埋め込まれたtar1∧2のうち1枚が第一ブロックの担当として確定する」というのが前の話であったが、今回の事情は「tar1の埋め込み枚数が0枚のとき、埋め込まれたtar1∧2,tar1∧3,tar1∧2∧3のうち1枚が第一ブロックの担当として確定する」というもの。つまり、どのtarについて手を加えなければならないのかが確定しない。そこで視点を変えて、ひとつに注目するのではなく全体を俯瞰する必要がある。
まずtar1の埋め込み枚数のみが0のとき：π[1]=0,π[2]≠0,π[3]≠0を考える。
このとき、π[1]≠0の場合の係数K=K12*K23*K13*K123は1/2π[12]+π[13]+π[23]*3π[123]である。ここで「π[1]=0とした場合にどのような修正をすべきか」を考えると解決の糸口が見えてくる。つまり2π[12]+π[13]+π[23]*3π[123]から第一ブロックの担当が0枚になるようなパターンを引けばよいのだ。これをαとおくと

tar1∧2：すべて第二ブロックの担当
tar1∧3：すべて第三ブロックの担当
tar2∧3：制限なし
tar1∧2∧3：すべて第二ブロックの担当または第三ブロックの担当

となるから、結局1/( 2π[12]+π[13]+π[23]*3π[123]-2π[23]*2π[123] )とすればよい。π[1]≠0,π[2]=0の場合も同様。

次にπ[1]=π[2]=0,π[3]≠0の場合。第一ブロックの担当が0枚になるパターンと第二ブロックの担当が0枚になるパターンの和集合をとる。ブロック計算の仕方により第一(二)ブロックの担当は必ず存在することに注意。上記のαはここで

tar1∧2：すべて第一ブロックの担当またはすべて第二ブロックの担当
tar1∧3：すべて第三ブロックの担当
tar2∧3：すべて第三ブロックの担当
tar1∧2∧3：すべて第三ブロックの担当

となるから、結局1/( 2π[12]+π[13]+π[23]*3π[123]-2 )でよい。π[1]=π[3]=0,π[2]≠0やπ[2]=π[3]=0,π[1]≠0も同様。

最後にπ[1]=π[2]=π[3]=0の場合。「第一ブロックの担当が欠落」「第二ブロックの担当が欠落」「第三ブロックの担当が欠落」の3つがある







---キリトリ---

以上を総括する。次の3つの点に注意。
埋め込み枚数は多項式のため、数式に組み入れると見にくい。そこで改めて埋め込み枚数を書き直す。
[π1] = j10
[π2] = j20
[π3] = j30
[π12] = j12+j21
[π23] = j23+j32
[π13] = j13+j31
[π123] = (i1-j10-j12-j13)+(i2-j20-j21-j23)+(i3-j30-j31-j32)
「枚数」という値は負にはならないから、「枚数」が1枚以上ということは0枚ではないことと同値。
したがって n ≥ 1はn ≠ 0と書いても意味は変わらない。
またも条件分岐が煩いが、=0となる式の数を仮に欠乏数ωと書くとω=0のとき、ω=1のとき、ω=2のとき、ω=3のとき、という分岐になっていることが分かる。またK12のように2重に重複している部分とK123のように3重に重複している部分があるが、この重複の度合いを仮に重複数ρと書くと、係数の値は1/ρ[π]-ωのように表現できる。これは次の節でのn項重複、すなわち二項重複、三項重複と進んできた流れを一般化する段階で中心的な役割を果たす変数である。

さて、三項重複における係数Kは次のように定まる：

K = K12 * K23 * K13 * K123

ただし、K12 ,K23 ,K13 ,K123は次の表に従う。
係数 値 条件    
K12 1/2[π12] [π12] ≠ 0 and (i1-j12) ≠ 0
and
(i2-j21) ≠ 0
  1/2[π12]-1 [π12] ≠ 0 and (i1-j12) = 0
and
(i2-j21) ≠ 0
or
(i1-j12) ≠ 0
and
(i2-j21) = 0
  1/2[π12]-2 [π12] ≠ 0 and (i1-j12) = 0
and
(i2-j21) = 0
  1 [π12] = 0    
K23 1/2[π23] [π23] ≠ 0 and (i2-j23) ≠ 0
and
(i3-j32) ≠ 0
  1/2[π23]-1 [π23] ≠ 0 and (i2-j23) = 0
and
(i3-j32) ≠ 0
or
(i2-j23) ≠ 0
and
(i3-j32) = 0
  1/2[π23]-2 [π23] ≠ 0 and (i2-j23) = 0
and
(i3-j32) = 0
  1 [π23] = 0    
K13 1/2[π13] [π13] ≠ 0 and (i1-j13) ≠ 0
and
(i3-j31) ≠ 0
  1/2[π13]-1 [π13] ≠ 0 and (i1-j13) = 0
and
(i3-j31) ≠ 0
or
(i1-j13) ≠ 0
and
(i3-j31) = 0
  1/2[π13]-2 [π13] ≠ 0 and (i1-j13) = 0
and
(i3-j31) = 0
  1 [π13] = 0    
K123 1/3[π123] [π123] ≠ 0 and ([π1]+[π12]+[π13]) ≠ 0
and
([π2]+[π12]+[π23]) ≠ 0
and
([π3]+[π13]+[π23]) ≠ 0
  1/3[π123]-1 [π123] ≠ 0 and ([π1]+[π12]+[π13]) = 0
and
([π2]+[π12]+[π23]) ≠ 0
and
([π3]+[π13]+[π23]) ≠ 0
or
([π1]+[π12]+[π13]) ≠ 0
and
([π2]+[π12]+[π23]) = 0
and
([π3]+[π13]+[π23]) ≠ 0
or
([π1]+[π12]+[π13]) ≠ 0
and
([π2]+[π12]+[π23]) ≠ 0
and
([π3]+[π13]+[π23]) = 0
  1/3[π123]-2 [π123] ≠ 0 and ([π1]+[π12]+[π13]) ≠ 0
and
([π2]+[π12]+[π23]) = 0
and
([π3]+[π13]+[π23]) = 0
or
([π1]+[π12]+[π13]) = 0
and
([π2]+[π12]+[π23]) ≠ 0
and
([π3]+[π13]+[π23]) = 0
or
([π1]+[π12]+[π13]) = 0
and
([π2]+[π12]+[π23]) = 0
and
([π3]+[π13]+[π23]) ≠ 0
  1/3[π123]-3 [π123] ≠ 0 and ([π1]+[π12]+[π13]) = 0
and
([π2]+[π12]+[π23]) = 0
and
([π3]+[π13]+[π23]) = 0
  1 [π123] = 0    

第三稿

エンジン基礎理論第二章第二節「二項重複」

前節における単位ブロックの一般形は

∑i=1Min[μ-∑ip-q, N(tar)](μ-∑ip)Ci*N(tar)!/{N(tar)-i}!
または
∑i=1Min[μ-∑ip-q, N(all-tar)](μ-∑ip)Ci*N(all-tar)!/{N(all-tar)-i}!

であった。N(tar)!/{N(tar)-i}!はPC上ではごちゃごちゃして見えるので、本章からは《N(tar), i》と省略記号を導入する。
そこで改めて上の単位ブロックの一般形を書き直すと

∑i=1Min[μ-∑ip-q, N(tar)](μ-∑ip)Ci*《N(tar), i》
または
∑i=1Min[μ-∑ip-q, N(all-tar)](μ-∑ip)Ci*《N(all-tar), i》

となる。

パラメータ∑ip,qはブロックの組み合わせ方から決まる数であって、ブロックの積をとれば一意的に決まることがは自明である。一方μ(all)も i1,i2,i3,...のみによっ て記述できるから、ライブラリアウトの場合を除けばすぐ定義できることは明らか。問題はtarである。たとえば（ブロックA）・（ブロックB）となってい るとき、ブロックAにおけるtar1とブロックBにおけるtar2に重複部分が存在しないか完全に一致していればよいのだが、重複部分がある場合、 tar1をi枚埋めたときにデッキ内のtar2はi枚減っているかどうかが「分からない」。もしブロックAで「tar1ではあるがtar2ではない」部分を取ったならN(tar2)はそのままでいいが、「tar1でもありtar2でもある」部分を取ったならN(tar2)から1枚分を差し引かなければなら ない——という操作をi回繰り返す。ブロック積をとったとき、各ブロック間にこのような事情があると単純な積を定義することができない。
具体例を示そう。tar1とtar2をこの順番で選ぶことを考える。tar1\2,tar2\1,tar1∧2はそれぞれ空集合ではないとすると、
（tar1ブロック）・（tar2ブロック）
が最も素朴な形だが、

∑i1=1Min[μ-1, N(tar1)]μCi1*《tar1, i1》   *   ∑i2=1Min[μ-i, N(tar2)](μ-i1)Ci2*《N(tar2), i2》
とりあえず値を代入しただけ。省略記号の導入に注意。

としてしまうと不都合である。tar1ブロックでtar1∧2を選んだ場合、tar2が1枚減るように計算しなければならないのだは、tar2ブロックではそのことを考慮していない。
ここでtar1ブロックをよく見てみよう。tar1ブロックはtar1とtar1∧2が混在しているが、「残領域i1枚にtar1\2とtar1∧2を入れるパターン数」と捉えれば、共通部分のないtar1\2ブロックとtar1∧2ブロックの積と考えることができて、
∑i1=1Min[μ-1, N(tar1)]μCi1*∑j1=0Min[N(tar1\2), i1)]i1Cj1*《N(tar1\2), j1》*《N(tar1∧2), i1- j1》*  ∑i2=1Min[μ-i1, N(tar2)-(i1-j1)](μ-i1)Ci2*《N(tar2)-(i1-j1), i2》
茶文字部分がtar1ブロックを開いた箇所である。このような記述の仕方によってtar2ブロックにおけるtar1∧2の枚数減少を記述することができる。

と書ける。ただし、これだけではやや問題がある。tar2ブロックも同様に開くと
∑i1=1Min[μ-1, N(tar1)]μCi1*∑j1=0Min[N(tar1\2), i1]i1Cj1*《N(tar1\2), j1》*《N(tar1∧2), i1- j1》*  ∑i2=1Min[μ-i1, N(tar2)-(i1-j1)](μ-i1)Ci2*  ∑j2=0Min[N(tar2\1), i2]i2Cj2  *《N(tar2\1), j2》*《N(tar1∧2)-(i1-j1), i2-j2》
同上。

となるが、これを模式的に表すと

■■■■■■■■■■■■
└───┘└─────┘←tar2ブロック
↑tar1ブロック
■：tar1\2
■：tar2\1
■：tar1∧2

となり、「tar1ブロックによって埋められたもの」と「tar2ブロックによって埋められたもの」とでtar1∧2が2カ所に分かれていることが分かる。この事実はパターン数え上げにおいて不都合である。
tar1\2を埋める際にはi1枚の領域の組み合わせを選び出し、その中からj1枚の領域の組み合わせを選び出し、そこに1枚ずつ埋めていく、という作業になるから重複の余地はない。tar2\1も同様である。
tar1∧2は少し問題がある。tar1を埋めるときに左の紫が、tar2を埋めるときに右の紫が配置されることになるのだが、逆に、tar1を埋めるときに右の紫を、tar2を埋めるときに左の紫を配置したとしても、同じ結果が得られる。さらに言えば、tar1を埋めるときに両方の紫を入れたパターンも、tar2を埋めるときに両方とも入れるパターンも同様。つまり、このままだと同じパターンを重複して数えていることになるのだ。より詳しく見てみよう。
tar1\2,tar2\1は各1枚以上埋められ、紫が2個だと仮定して、tar1\2とtar2\1の位置を固定すると、
tar1ブロックが左右両方の紫を担当する場合
tar2ブロックが左右両方の紫を担当する場合
tar1ブロックが左の紫を、tar2ブロックが右の紫を担当する場合
tar2ブロックが左の紫を、tar1ブロックが右の紫を担当する場合

の4パターンをすべて別々のものとして計算するように、上の式は要求している。
これらはtar1\2とtar2\1の位置の選び方によらないから、本来1パターンであるものを4パターンと扱っているという事実が、あらゆるtar1\2とtar2\1の位置の選び方に関して言える。したがって真のパターン数の4倍を計上していることになる。（ただし紫が2個であること、tar1\2とtar2\1が最低1枚以上あることの2つを前提にしていることに注意）
同様に、紫が3個だと仮定すると、tar1\2とtar2\1の位置を固定して、
tar1ブロックがすべての紫を担当する場合
tar2ブロックがすべての紫を担当する場合
tar1ブロックが一番左の紫を、tar2ブロックが右2つの紫を担当する場合
tar1ブロックが真ん中の紫を、tar2ブロックが両端2つの紫を担当する場合
tar1ブロックが一番右の紫を、tar2ブロックが左2つの紫を担当する場合
tar2ブロックが一番左の紫を、tar1ブロックが右2つの紫を担当する場合
tar2ブロックが真ん中の紫を、tar1ブロックが両端2つの紫を担当する場合
tar2ブロックが一番右の紫を、tar1ブロックが左2つの紫を担当する場合

の8パターンとして別々に計算していて、これらはtar1\2とtar2\1の位置の選び方によらないから、真のパターン数の8倍を計上していることになる。
さらに一般化しよう。tar1\2とtar2\1が少なくともそれぞれ1枚以上あるとして、紫がπ個だと仮定、もちろん十分な領域数があるものとする。
さらにπ個の紫に対して1番目の紫、2番目の紫、・・・、π番目の紫として区別すると、tar1\2とtar2\1の位置を固定して、
tar1ブロックがすべての紫を担当する場合■
tar2ブロックがすべての紫を担当する場合■
tar1ブロックが1番目の紫を、tar2ブロックが残るπ-1個の紫を担当する場合■
tar1ブロックが2番目の紫を、tar2ブロックが残るπ-1個の紫を担当する場合
・・・
tar1ブロックがπ番目の紫を、tar2ブロックが残るπ-1個の紫を担当する場合■
tar1ブロックが1番目と2番目の紫を、tar2ブロックが残るπ-2個の紫を担当する場合■
・・・
tar1ブロックがπ-1番目とπ番目の紫を、tar2ブロックが残るπ-2個の紫を担当する場合■
（以後、π個の中からm個をtar1ブロックの担当、残るπ-m個がtar2ブロックの担当だと割り当てる）

となり、結局■■の間は2=πC0+πCπ通り、■■の間はπ=πC1通り、■■の間はπC2通り、・・・の総和をとって
 ∑m=0ππCm
=2π
tar1ブロックの担当が0個のとき、1個のとき、2個のとき、・・・π個のときで場合分けしたとき、どの紫を選ぶかはそれぞれπC0個、πC1個、πC2個、・・・、πCπ個ある。その総和。実はこれ、2πに等しい。「二項定理」で検索してみよう。

この倍数分のパターンを計上していたことになるから、逆数をかければ重複分を除することができる。
「あれ？■■の間、■■の間、■■の間、……が2πになるのは分かったけど、tar1ブロックとtar2ブロックを入れ替えたパターン、例えば
tar2ブロックが1番目の紫を、tar1ブロックが残るπ-1個の紫を担当する場合■
tar2ブロックが2番目の紫を、tar1ブロックが残るπ-1個の紫を担当する場合
・・・
tar2ブロックがπ番目の紫を、tar1ブロックが残るπ-1個の紫を担当する場合■

は計算に入れないの？」と思われるかもしれないが、例えば
tar2ブロックが2番目の紫を、tar1ブロックが残るπ-1個の紫を担当する場合

は
tar1ブロックが1番目と3番目と4番目と……とπ番目の紫を、tar2ブロックが残る1個の紫を担当する場合

と対応しており、そのようなパターンも上に折り込み済みとなっている。
上記のパターン数え上げには別の解釈もできる。すなわち紫1つ1つに「tar1ブロックの担当」か「tar2ブロックの担当」かが考えられるから、π個の紫に対してtar1ブロックとtar2ブロックの二通り、2π通りのパターンがあるはずだ、という考え方だ。こちらのほうが簡単かもしれないが、まあ理解しやすいほうを選んでほしい。

さて、
tar1\2が0枚、tar2\1が1枚以上
tar2\1が0枚、tar1\2が1枚以上
tar1\2が0枚、tar2\1が0枚
の各場合についての検討に入ろう。tar1\2やtar2\1の埋め込み枚数が0枚となる場合、「各ブロックから最低1枚のカードを出す」という制約によりtar1∧2(紫)のうち1つまたは2つがどのブロックの担当か確定することになる（例えば赤と紫だけのパターンでは、紫のうち1つは必ずtar2ブロックの担当であるはずだ）。ここではπ個のtar1∧2(紫)のうち1つ(2つ)の担当が確定しているから、残るπ-1個(π-2個)についての担当のパターンの数え上げ、つまり2π-1(2π-2)通りになる。「担当が確定したtar1∧2(紫)がどこにあるかによって場合分けしないの？」という疑問があるかもしれないが、「確定」した位置においてのみ「tar1ブロックの担当」or「tar2ブロックの担当」が「tar1ブロックの担当(確定)」になるだけで、別に他の位置が「確定」となっても同じパターンを生成する可能性はあることに気づけば間違いだと分かるはず。

■tar1\2が0枚、tar2\1が1枚以上
このとき、紫すなわちtar1∧2のうち1つはtar1ブロックの担当であることが確定している。
すなわち残るπ-1個の紫について同様の計算を行えばよいから
 ∑m=0π-1π-1Cm
=2π-1

■tar2\1が0枚、tar1\2が1枚以上
同様に
∑m=0π-1π-1Cm
=2π-1

■tar1\2が0枚、tar2\1が0枚
同様に、π-2個の紫について同様の計算を行う。
∑m=0π-2π-2Cm
=2π-2

以上を総括して

重複分を除する係数をKとおくと、
∑i1=1Min[μ-1, N(tar1)]μCi1*∑j1=0Min[N(tar1\2), i1]i1Cj1*《N(tar1\2), j1》*《N(tar1∧2), i1- j1》*  ∑i2=1Min[μ-i, N(tar2)-(i1-j1)](μ-i1)Ci2*  ∑j2=0Min[N(tar2\1), i2]i2Cj2  *《N(tar2\1), j2》*《N(tar1∧2)-(i1-j1), i2-j2》* K
π = (i1-j1)+(i2-j2)
K = { 1/2π (π ≥ 1、j1 ≥ 1かつj2 ≥ 1のとき)
         1/2π-1 (π ≥ 1、j1 = 0またはj2 = 0、j1 ≠ j2のとき)
         1/2π-2 (π ≥ 1、j1 = 0かつj2 = 0のとき)
         1                   (π = 0のとき)}
Kはシグマより前に出してはいけない。πはtar1∧2の枚数であった。π = 0ならば問題は生じないのでそのままでよいが、π ≥ 1ならば上述の問題が起きるのでtar1\2やtar2\1の枚数によって場合分けしてパターンの重複倍数で割っている。条件分岐が煩瑣に見えるが、要するに「tar1\2とtar2\1が両方とも1枚以上埋め込まれる場合」「tar1\2とtar2\1のうち片方が0枚埋め込まれる場合」「tar1\2とtar2\1の両方とも0枚埋め込まれる場合」(以上、tar1∧2(紫)が1枚以上埋め込まれることが前提)、「そもそもtar1∧2が来ない場合」という意味。


第六稿

エンジン基礎理論第二章第一節「ブロック」

∑(summation)の記法について。∑の上下に始点と終点を書くのが普通だが、エディタの都合により∑k=1nk = 1/2*n*(n-1)のように上付き文字と下付き文字で表現する。

カードゲームにおける確率の解釈は、サイコロの目の確率の考え方——つまり全体が1で、各目の確率が同様に確からしいので、6等分して1/6である——と同じ解釈ができる。つまり、全体が1で、n枚引いたときの全パターン40! / (40-n)!がすべて同様に確からしいから40! / (40-n)!等分して1 /{40! / (40-n)!}=(40-n)! / 40!である、というふうに捉えることができ、このパターン1つあたりの確率とパターンの総数との積で求める確率が得られる。パターン1つあたりの確率は一定だから、パターン数え上げの問題とみることができる。「確率」で考えると分母分子の双方を吟味しなければならないが、「パターン数え上げ」の問題とみれば扱いやすい自然数の問題となる。
さて、後々パターン数え上げを行うのだが、それらは次のような図式で考えることになる。

■■■■■■■■■■

これはカードを10枚引いた状態の模式図である。ドローカードの存在を考えなければ、先攻11ターン目、後攻10ターン目に相当する。ドローカードを考えるなら引いた枚数分ターンを早めてやれば良い(こうして出来た仮想的なターンが、後で扱う「仮想ターン」である)。四角の1つ1つがカードの1枚1枚で、左5枚(オレンジ)が初手5枚、次の1枚(赤)が先攻2ターン目/後攻1ターン目に引いたカード、その次の1枚(青)が先攻3ターン目/後攻2ターン目に引いたカード、……という順になっている。これらの四角を「領域」と呼び、ある固定された領域についてパターン数を数えるとき、「固定された領域」を「全領域」、なんらかの形で領域の状態が既に決まっているときの「残りの領域」を「残領域」と呼ぶ。一気に説明してしまったが、言葉の意味はその使い方によって規定されるものだ。「説明」よりも「使い方」から意味を汲み取ってほしい。
さて、パターン数を数え上げるということは「全領域n枚の領域の一つ一つを決定すること」に他ならない。たとえば互いに区別する(†1)カードtarがデッキの中に初期状態でN(tar)枚あり、それによってn枚の領域のうちi枚を決定する(†2)とき、そのパターン数は

nCi*N(tar)*{N(tar)-1}*...*{N(tar)-(i-1)} （n個の領域からi個選ぶときの組み合わせ数）×（デッキ中の目的カードの枚数）×（デッキ中の目的カードの枚数-1）×・・・×（デッキ中の目的カードの枚数-(i-1)）
=nCi*N(tar)!/{N(tar)-i}! 階乗記号を使って形式的に整理。ここで左の式の分母の「i」が、上の「茶色の項の個数がi個ある」ことに対応している。

となる。しかし分数は見辛いのでN(tar)!/{N(tar)-i}!を《N(tar),i》と書くことにしよう。

(†1)ここで互いに区別するカードと書いたが、これ以降は特に断らず、同じ種類のカードであっても互いに区別するものとする（(40-n)!/40!とパターン 数の積を考えるのだから、当然。）。また初期状態でN(tar)枚というのは、途中でデッキ内のtarが減少した場合は{N(tar)-1}のように減少 分を差し引くことで対応するから途中でN(tar)の枚数が減るようなことは考えないということである。換言すれば、N(tar)は定数である。
(†2)領域の状態を決定することを、(カードを)「埋め込む」と表現する。

さて、これをもう一歩進めて、「tar1がデッキの中にN(tar1)枚、同じくtar2がデッキの中にN(tar2)枚あるとき、tar1によってn枚の領域のうちi1枚、tar2によってi2枚を埋め、領域が残っていれば、そこにはtar1もtar2も入らない」ときのパターン数を考えよう。またtar1かつtar2であるようなカードはないものとする（後述するが、tar1かつtar2であるカードがあると複雑になるから、「ブロック」の基本を述べるうえでは省く）。
まずtar1が1枚埋め込まれる場合、tar1が2枚埋め込まれる場合・・・と場合分け&総和をとる、という操作を上限（tar2が入る領域がなくなる手前(†3)か、tar1がなくなるかの小さい方）まで行う。
∑i1=1Min[n-1, N(tar1)]nCi1*《N(tar1),i1》
ここでMin[x,y]はx,yのうち最小の値を意味する。
（n個の残領域をちょうど1枚埋めるときのパターン数）＋（n個の残領域をちょうど2枚埋めるときのパターン数）＋・・・＋（n個の残領域をちょうどMin[n-1,N(tar1)]枚埋めるときのパターン数）←ここのMin[n-1,N(tar1)]は、n個の領域をすべて埋めるとtar2の入る場所がなくなってしまうために最大でもn-1までしか入らないようにしておくこと＋デッキ内にあるtar1の枚数より大きくなることはないという事情から、これらのうち小さいほうを上限とする、という意味。

(†3)tar1が全領域n枚をすべて埋め込んでしまうと、tar2の埋め込む領域がなくなってしまう。

これらの各場合、すなわちtar1が1枚埋め込まれたとき、tar1が2枚埋め込まれたとき・・のそれぞれについて、tar1が埋めた後の残りの領域n-i枚の中にtar2の居場所を考えるから
∑i1=1Min[n-1, N(tar1)]nCi1*《N(tar1),i1》*∑i2=1Min[n-i1, N(tar2)](n-i1)Ci2*《N(tar2),i2》
茶色は新規追加分。左側のシグマの中に右側のシグマが入っている、という入れ子構造になっている。しかし交換法則が成り立たないことに注意すれば「左のシグマ・組合せ・階乗」と「右のシグマ・組合せ・階乗」の積と擬似的に思うことができる。tar1が1枚埋め込まれたとき、tar1が2枚埋め込まれたとき・・・のそれぞれについてtar2が1枚埋め込まれたとき、tar2が2枚埋め込まれたとき、・・・を考える。なお、この式は
∑i1=1Min[n-1, N(tar1)]∑i2=1Min[n-i1, N(tar2)]nCi1*《N(tar1),i1》*(n-i1)Ci2*《N(tar2),i2》
とシグマの位置を移しても意味は同じ。碁盤の目のように、横軸に左のシグマの埋まる枚数i1枚を、縦軸に右のシグマの埋まる枚数i2枚をとってみると、i1+i2=nとなるところが境界となり、境界線上とその内側の碁盤の目の1つ1つの値(値は格子の各部屋ではなく、縦横の直線の交点であることに注意)をすべて足し合わせていくことがシグマを2つ重ねることの意味である(†4)。右側のシグマの上限にiが含まれていることから、両シグマの交換だけはできないことに注意(†5)。シグマが3つ以上の場合はこれの類推から考えればよい。たとえばシグマが3つのときは立方体を賽の目に切ったもので、平面i1+i2+i3=n、直線i1=1,i2=1,i3=1により構成される三角錐の境界上またはその内側に含まれる各点をすべて集めたものがシグマを3つ重ねることの図形的表現である。4つ以上はもはや図形表現できないが、シグマが2つ、3つの場合を押さえておけば、似たようなものだと心の中で思っておくことができるだろう。(†6)(†7)
†4：つまりi1=1,i2=1,i1+i2=nにより構成される三角形の境界上またはそれより内側にある点をすべて集めたものが【「tar1をi1枚埋める＋tar2 をi2枚埋める」において合わせてn枚を超えないようなパターンの総和、(i1,i2)=(1,1),(i1,i2)=(1,2),……(i1,i2)=(n-1,1)】の図形的表現である。なお、 上限がn-1ではなくN(tar1)のほうに引っかかるときは、そこだけ三角形が「欠ける」ことになる。
†5：逆に言えば、i1がなければ交換可能である
†6：本質は「カードを順次埋め込む」ことであって、図形的表現はそれを「納得」するための視覚的手段にすぎない。
†7：格子による「交点」ではなく「部屋」に値を置くことにすると、3次元格子の各部屋を有限の3次元空間とみなして4.5,6次元目を入れることができ(整数間の幅を狭くすればいくらでも整数が入れるから有限でもかまわない)、さらにそれによる格子の各部屋に7,8,9次元目を入れる……といくらでも図形的表現が可能。次元数が莫大にならない限り階段状になってしまうのが難点だが。

さらに残る領域n-i1-i2枚の中にtar1もtar2も埋め込まれないことを保証しなければならない。残ったところにtar1やtar2が埋め込まれると、パターンを重複して数え上げることになってしまうからだ。
tar1でもtar2でもないカードはall-tar1-tar2と表され、デッキ内の枚数はN(all-tar1-tar2)と書けるから、
∑i1=1Min[n-1, N(tar1)]nCi1*《N(tar1),i1》*∑i2=1Min[n-i1, N(tar2)](n-i1)Cj*《N(tar2),i2》*《N(all-tar1-tar2),n-i1-i2》
茶色は新規追加分。末尾に（残った領域にtar1でもtar2でもないカードを埋めるパターン数）を掛けた。tar1とtar2を選ぶ段階で共通して存在した「シグマ」と「C（組み合わせ数）」がここで消えているのは、それぞれ「これで最後だから何枚埋めるかによって場合分け＋総和をとる必要がない」と「残った領域をすべて埋めることになるからどの領域を選ぶかという問題はそもそも発生しない」が理由になる。

となり、これで完成した。

さて、ここからが重要なのだが、これを三つのブロックに分割する。
∑i1=1Min[n-1, N(tar1)]nCi1*《N(tar1),i1》　（ブロック１）
∑i2=1Min[n-i1, N(tar2)](n-i1)Cj*《N(tar2),i2》　（ブロック２）
《N(all-tar1-tar2),n-i1-i2》　（ブロック３）

このとき、ブロック１はtar1について、ブロック２はtar2について、ブロック３は残りの領域について記述した項を意味することを確認しておきたい。
何度も言うように、パターンの数え上げとは「残領域数n枚の領域の一つ一つを決定すること」に他ならないのだが、上記のブロック分割の考え方を以てすれば、たとえば新しくtar3が増えたとしても（もちろんN(tar1∧tar3)=N(tar2∧tar3)=0とする。ここからN(tar1∧2∧3)=0も導かれる。）
∑i1=1Min[n-2, N(tar1)]nCi1*《N(tar1),i1》　（ブロック１）
∑i2=1Min[n-1-i1, N(tar2)](n-i1)Cj*《N(tar2),i2》　（ブロック２）
∑i3=1Min[n-i1-i2, N(tar3)](n-i1-i2)Cj*《N(tar3),i3》（ブロック３）
《N(all-tar1-tar2-tar3),n-i1-i2-i3》（ブロック４）

とひとつブロックを増やすだけでよく（もちろん細部をいじることは必要だが）、これによって任意のtar1,tar2,...,tarnについてパターンを数え上げることができ、それは「全領域数n枚の領域の一つ一つを決定すること」に他ならない。
ここから素朴なブロックの定義を考えてみよう。ブロックどうしの組み合わせ、すなわちブロック積については次の節に回すとして、ここではひとつひとつの最小単位としてのブロック、すなわち「単位ブロック」を定義する。
上の話から出てくるブロックの一般形は
∑i=1Min[n-m, N(tar)]nCi*《N(tar),i》

である。ここでnは全領域数、mは後続のブロックのための領域を少なくとも1つずつ残しておかなければならない事情から決定される数。このとき、ブロックのパラメータはn,m,N(tar)の3つ。これらの数がすべて定義されることがまずひとつ。これは少なくとも単位ブロックを考える上では自動的に定義されると思っていい。これらはブロックどうしの組み合わせを考える際にはじめて問題となる。
さて、まずはブロック単体からの視点。もしこの位置にだけは入れないというカードが存在した場合、n枚からi枚を自由に選んでその中に自由にカードを入れることができず、またこの位置にはこのカードだけは入れないということもそれと同値な条件だから「tarが任意の位置に入れること」が必要だ。ここで「入れる」とは、「最適判断」まで含めて吟味した上で「それがその位置に入った場合に成立するパターンが存在する」ことと定義する。逆に「tarが任意の位置に入れること」が成立すればn個の残領域の中からi枚選んでtarを埋める作業は一通り可能であるから、ブロック単体を見た場合は「tarが任意の位置に入れること」⇔「単位ブロックが定義される」と考えてよい。
次にブロックを組み合わせからの視点。冒頭ではtar1とtar2に共通部分がないと仮定して話を簡単にしたが、実際にはそのような場合がある。これの計算方法は次の節に書いているのだが、単位ブロックの組み合わせで複雑な事態を説明するという観点に立てば、「単位ブロックのtarは素集合であること」という条件が必要になる（素集合についての説明は次節を参照。「機能・リンク」からブログ内検索を使うと便利）。ここでは深くは触れないでおくが、たとえばtar1,tar2という2つの集合に対して、互いに素なtar1\2,tar2\1,tar1∧2という3つの集合がこの場合の「素集合」である。(†8)

(†8)上で計算したように、例えばtar1→tar2の順で埋め込むとすると、tar1ブロックでtar1\2を埋め込むのかtar1∧2を埋め込むのかによってデッキ内のtar2の枚数がN(tar2)になるかN(tar2)-xになるのかが変わるから、そこで場合分けが必要になり、その際にtar1\2と tar1∧2を区別するような集合体系が必要になる。

この単位ブロックの積によってパターン数を求めることになるが、ブロックの積についてはやはり後回しにして、前後にブロックがあることも考えた単位ブロックの一般形を再定義しておきたい。

∑i=1Min[n-m, N(tar)]nCi*《N(tar),i》

において、nは全領域数、mは後続ブロック数を考慮した数であった。ここで単位ブロックの使用範囲を広げるために、「全領域」ではなく「残領域」を考えよう。Σip=i1+i2+i3+...とおき（そのブロックよりも前にあるブロックにおいて埋め込まれた領域の個数の総和。たとえば4つのブロックを並べた(∑i1=1Min[]～)(∑i2=1Min[]～)(∑i3=1Min[]～)(∑i4=1Min[]～)において4番目のブロックにおける∑ipは∑ip=i1+i2+i3である。）、n'を残領域とすると、n'はn-∑ipと書ける。
またmを「後続のブロックのための領域を少なくとも1つずつ残しておかなければならない事情から決定される数」といったが、結論から言えば「閉じたブロックの要求する最低枚数の総和」である。ここで「閉じたブロック」とは
∑i=1Min[n-m, N(tar)]nCi*《N(tar),i》

の形をしたもので、これと対比して
∑i=1Min[n-m, N(all-tar)]nCi*《N(all-tar),i》

の形をしたものを「開いたブロック」という。「閉じたブロック」はtarを選ぶためのブロックであり、「開いたブロック」はtarを選ばないためのブロックである。「閉じたブロック」には必要なカードが入り、「開いたブロック」はあとの領域を上手く埋めるためのものにすぎないから、それぞれの「閉じたブロック」に必要な最低枚数の総和を考えれば十分。
この「閉じたブロックの要求する最低枚数の総和」をqとおき、今までの全領域nの記号を破棄して、これをμを書くことにすると、
閉じたブロックの一般形は
∑i=1Min[μ-∑ip-q, N(tar)](μ-∑ip)Ci*《N(tar),i》
全領域をμ、これより前のブロックによって埋まる領域数を∑p、これより後の閉じたブロックが要求する最低枚数の総和をqとしたときの「残領域μ-∑p枚の中にtar1とtar2が入っているパターンの総数」

開いたブロックの一般形は、やはり
∑i=1Min[μ-∑ip-q, N(all-tar)](μ-∑p)Ci*《N(all-tar),i》

しかし、tarを選ばないということは all-tarを選ぶことと同値だから、「単位ブロックの一般形」というときは
∑i=1Min[μ-∑ip-q, N(tar)](μ-∑ip)Ci*《N(tar),i》

のほうを用いることにする。

第何項か覚えてない

TemplateDesign by KARMA7

忍者ブログ [PR]