日進ムーンウォーカー

Alien to people, Behind people, Closed to people, Distant from people, Eliminate me Fujita

筆不抄(17):区別のないものを区別のない3つの箱に分ける場合の数について

これはエッセイでもなんでもない。ただ表題について説明を試みるだけの記事である。

 

無数のボールと、それを入れるための3つの箱がある。ボールをこれらの箱に分けて入れるとき、その分け方は何通りあるかという問題である。

ひとまず空の箱があってもいいことにする。そちらの方が考えやすい。

初歩的な注意点は、3つの箱に入ったボールの数を(a,b,c)のように表すとき、(a,b,c)と(c,a,b)は同じものとカウントする。なぜなら、箱に区別がないから、どの2つの箱を入れ替えても入れ替える以前との区別がない。

箱が2つの場合はクソ簡単で、例えばボールが2n個のときは(0,2n)、(1,2n-1)、・・・、(n,n)のn通りになる。ボールが奇数個の時も同じ要領で導ける。

 

ところが3つになると、途端にややこしく面倒になる。その導出について1つの方法を思いついたので、以下に説明する。

まず表記については、さきほどと同様に、それぞれの箱に入っているボールの数をカッコ内に並べて書く。このとき、必ず数の大きさが(大、中、小)の順となるように書くようにする。

方針をざっくり示す。最初に、ボールを1つの箱に固めてしまう。この箱を箱Aとしよう。これを初期状態として、空の2つの箱にボールを分配していく。ここで、2つの操作を考える。

1つが、名付けて「凸積み」。箱Aを除く2つの箱のボールの数の差が開くように、ボールを箱Aから移す。別の言い方をすれば、ボールが多い方の箱にボールを移す。

便宜上、箱A以外の2つの箱のボールの数が等しいときに凸積みを行うとき、ボールを移す先の箱を決めておく。これを箱Bとする。残りの箱を箱Cとする。つまり、箱Aのボールの数≧箱Bのボールの数≧箱Cのボールの数が成立するということである。

もう1つの操作が、「平積み」。さっきとは反対に、箱Bと箱Cのボールの数の差を縮めるようにボールを移す。要は、ボールが少ない方の箱にボールを移す。

こう2つの操作を想定するところまでは、なんら目新しいアイデアはない。多少画期的に思えるのはここからである。

全ての状態は初期状態から以上の2操作を適当な数行うことで再現できる。これを図示する。1つの状態を点で、凸積みを下矢印(↓)、平積みを右矢印(→)で表す。すると、この矢印と点は全体として整然とした図形を成すか、規則的な配置に落ち着く。これを(この点を)数え上げれば、問題の解となる。

 

実際に考えてみる。ボールの数を3で割った余りと、ボールの数の偶奇で6通りの場合分けが要るが、基本的に大体どれもすること自体は同じなので、ボールが6n個のときでためしにやってみる。

f:id:Betterthannot:20210301203528p:plain

まず点を打ち、これを初期状態(6n,0,0)、点Pとする。先に示したルールに則り、凸積みする。初期状態ではどちらの箱にボールを移しても数に差が開くので、平積みすることはできない。点Pから、下に矢印を伸ばす。

凸積みを何回繰り返せるか考えると、(3n,3n,0)の状態になるまでは可能である。つまり、点Pから3n本下に矢印を伸ばせる。この点を点Qとする。

一方、凸積みと平積みをコンボさせると、右斜め下へ矢印を伸ばせる。これは箱Bと箱Cに1つずつボールを移す操作にあたる。初期状態からコンボは何度行えるかというと、(2n,2n,2n)の状態になるまでであり、2n回である。この点を点Rとする。

点Rから点Qへはどのように行けるだろうか。ここで、左矢印、すなわち平積みの逆、箱Bと箱Cのボールの数が開くように箱Cからボールを箱Aに戻す操作を「凸降ろし」と呼ぶことにする。同時に凸積みの逆の操作すなわち上矢印、つまり2つの箱のボールの数の差が縮まるようにボールを箱Aに戻す操作を「平降ろし」と呼ぶことにする。

ややこしくて申し訳ないが、「平積み」←→「凸降ろし」、「凸積み」←→「平降ろし」である。操作自体は決して難しくない。

点Rから凸降ろしを繰り返して到達する点を点R’とする。要は、点P,Q,Rを三角形とみるとき、Rから辺PQに下ろした垂線の足のことであり、(4n,2n,0)である。ここから凸積みをn回行うことで点Qに至る。

ここに概観が示された。各状態を表す点はおおよそ、底辺3n、高さ2nの三角形の面積個あると分かる。まずこの時点で、点P、点R、点R'を結んで出来る三角形内には(2n+1)n個の点がある。

f:id:Betterthannot:20210301203858p:plain

箱Aから箱Bへボールを移すと、差としては2開く。つまり凸積み、あるいは縦に移動する際には、あらかじめ箱Aのボールの数が箱Bより2個以上多くなくてはいけない。

つまり、点Rから点Qへ至るためには、凸降ろし*2+凸積みが適当な数行われれば良い。点R、点R'、点Qを結んで出来る三角形内には、(2n+1)n÷2個の点がある。さっきの数と足して、重複した点を除けば、6n個の区別のないボールを3つの区別のない箱に分ける場合の数は(3nー2)(2n+1)÷2通りと出る。

 

もう一つ、クラシックで明解な方法が存在するので紹介したい。概要をざっくり説明すると、解をめちゃめちゃ粗く見積もった後、条件と照らし合わせて修正していく方法である。

カッコ( , , )を、スロットだと思って見てみてほしい。ボールが6n個あるとき、このスロットの目は最大で6nを示すから、スロットとしては(6n,6n,6n)という表示も可能である。つまり、表示の総数は6n+1の3乗通りになる。

しかし、ボールが地球上の物質からできている以上、無からボールが創造されたり、ボールが跡形も無く消滅することはない。3つの目の和はピッタリ6nでなければならない。これを「物質条件」と名付ける。

この条件に適合しない表示の数を数え上げ、排除する。一つのスロットの目を固定すると考えやすい。左端の目が6nのとき、他の目の和は0でなければならない。(0,0)の一通りを除く全てのパターンが排除される。具体的な計算は面倒なのでしない。

左端の目が6nーkのとき、条件にあうパターンの数は「k個のボールを2つの区別のある箱に分けるときの場合の数」通りであり、これはk+1通りである。よって物質条件を満たすパターン総数は簡単な和の計算で求められる。

そしてもう一つの条件が課せられる。「重複条件」とでも名付ける。(6n,0,0)、(0,6n,0)、(0,0,6n)、これは最終的に全て同じものとカウントされるが、まだこの段階では3つとカウントされている。このような重複を排除していく。

3つの数が全て異なるとき、1つの同じと見なされるパターンが6つとカウントされているので、そのようなパターンの数の5倍を総数から引く。3つの数のうち2つが同じ時、上記の例のように2通り余計にカウントされているので、これを引く。3つとも同じ数のパターンははじめから1通りしかないので、放置で構わない。

 

以上である。「えっ?だから何だったの?」と思われるかもしれないが、とりあえず表題について一通り説明をしたので、もう書くことがない。何か書かねばならないとしたら、愛知県の市区町村を書き並べてもよかったが、きっと尾張の有象無象を列挙しているうちに関心は尽きる。(2933字)