前節における単位ブロックの一般形は
∑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個の紫について同様の計算を行えばよいから
■tar2\1が0枚、tar1\2が1枚以上
同様に
■tar1\2が0枚、tar2\1が0枚
同様に、π-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が来ない場合」という意味。 |
第六稿
PR
