立方体の着色等の組み合わせ問題で必要な、Burnside 定理から導出された巡回置換指数 (Cycle Index) をリストアップしておく。

立方体の6面  (x16 + 3x12x22 + 6x23 + 6x12x4 + 8x32) / 24
立方体の8頂点 (x18 + 9x24 + 6x42 + 8x12x32) / 24
立方体の12辺  (x112 + 3x26 + 6x43 + 6x12x25 + 8x34) / 24

これらの式では、回転したら同じように見えるものだと同じ組合せだとカウントする。例えば、立方体の6面に、1面だけが赤でほかの5面はすべて緑の立方体は1つしかない、という具合。

ここでは、例をもって、式の使い方をデモしてみる。

1例目。立方体の8頂点を異なる2色で塗る異なる塗り方を計算してみる。2色をそれぞれ a, b で表現し、上の式 (2) に、x のところを a+b に置き換え、添え字の数字を右肩のべき乗の位置に変えると、
  ((a+b)8 + 9(a2+b2)4 + 6(a4+b4)2 + 8(a+b)2(a3+b3)2) / 24
になり、a=1, b=1 にすると、式は
  (28 + 9*24 + 6*22 + 8*22*22) / 24 = 23
になり、塗り方が23通りあることが判る。

2例目。立方体の12辺を異なる6色で塗る場合の組合せ総数。
x に a+b+c+d+e+f を代入;
  ((a+b+c+d+e+f)12 + 3(a2+b2+c2+d2+e2+f2)6 + 6(a4+b4+c4+d4+e4+f4)3 + 6(a+b+c+d+e+f)2 (a2+b2+c2+d2+e2+f2)5 + 8(a3+b3+c3+d3+e3+f3)4) / 24
a, b, c, e, d, f にそれぞれ値 1 を代入する。
 (612 + 3*66 + 6*63 + 6*62*65 + 8*64) / 24 = 90775566 通り

3例目。n色の色紙を立方体の6面に貼り付けたときにできる異なる色の立方体の数。
変数 x の中に n を直接代入しておく。(1例目や2例目のように、a, b, c 等を使って展開しても最終的に1の代入になるだけなので、その個数をカウントすれば展開結果が判るので)。
  (n6 + 3*n2*n2 + 6*n3 + 6*n2*n + 8*n2) / 24
  = (n6 + 3n4 + 12n3 + 8n2) / 24  ← ACM #10733
 つまり、n=1なら答えは1通り、n=2なら10通り、n=1000では 41666792167000000 通りの異なる色の立方体が得られるわけだ。

このように、回転を含んでいる組合せ問題は、巡回置換指数を使うと簡単に解けてしまう。マジックという言葉にぴったりの技法。

Comments are closed.

Post Navigation