∑(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》 |
のほうを用いることにする。
第何項か覚えてない
PR
