http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q10120572235
n次元立方体の頂点を2色以内で塗るときのパターン(回転による同一視を考慮する)を求める問題である。
上記回答が最初の考察で、
その後に補足のノートを書いたものを下記に転記した。
その後にさらに整理した記述が、以下にある(英語):
Number of different ways to color vertices
of a n-dimensional hypercube using at most K colors
この数列はその後にオンライン整数列大辞典に登録されている。
https://oeis.org/A237748
n次元空間で座標軸を入れ替えるような"回転"を考える。
座標軸をx1軸,x2軸,...,xn軸というふうに名付ける。
それぞれの向きの単位ベクトルを A,B,C,D,.. とおく
それらを-1倍したベクトルを a,b,c,d,.. とおく。
例えば A,B,C,Dを回転した後が b,a,D,C のとき
この回転を ABCD → baDC と表記することにする。
(この回転でa,b,c,dを回転させるとB,A,d,cになる。)
回転は、n文字の置換と、大文字小文字の反転の組み合わせとなる。
独自の用語として、
大文字小文字の反転が偶数個の回転を正回転
大文字小文字の反転が奇数個の回転を負回転
と呼ぶことにします。
(正負が表すものは特にないですが名付けないと呼ぶのが面倒)
位置ベクトルが ±A±B±C±D... で表される2^n個の点を考える。
回転を繰り返し行うと、
それぞれの点は0個以上の別の点を経由してから戻ってきます。
回転を繰り返して行き来できる点同士を同値類と見なします
2^n個の点は何種類の同値類に分かれるか?
を回転の記述から求めるのが今回の目的です。
特定の同値類が含んでいる頂点の個数を
群論の用語を借りてその同値類の位数と呼ぶことにします
置換は、交わらない巡回置換の積で表せます
例えば ABCDEF → DACFBE という置換は
次の2つの巡回置換 (ADFEB),(C) と分解されます
(ADFEB)とは巡回置換A→D→F→E→B→Aの意味です
そこでまずは回転の置換が1つの巡回置換で表される時の
頂点たちの同値類の個数について(あまり論理的な説明でないですが):
<1>
・ABCDE→BCDEA だったら
±(A+B+C+D+E) であらわされる2つの頂点は不動点で位数1です。
その他の点では 位数が5になります。
一般に、kが奇数の時k文字の巡回置換で表される正回転は同様になります。
すなわち「位数1の同値類が2個, 残りは位数k」,頂点の個数を考えると
「位数1の同値類が2個, 位数kの同値類が (2^k-2)/k 個」という結果です。
例えば ABCDE→bCdEA についても確認しておくと
X=-B, Y=-C, x=B, y=C と置きなおすことでAXYDE→XYDEA と書かれるので
上記と同様になることが分かるでしょう
<2>
負回転の時は同様にはなりません。
ABC→bca を考えると、大文字小文字を無視すれば<1>の通りですが
回転をk回するとちょうど大文字小文字が全部入れ替わる結果となります。
(奇数の時の負回転としては適当に置きなおすことで
全部の大文字小文字が入れ替わる場合を考えれば良いのがポイントです)
踏み込んで考察すれば、kが奇数の時k文字の巡回置換で表される負回転では
「位数2の同値類が1個, 位数2kの同値類が (2^k-2)/2k 個」という結果です。
<3>
文字が偶数個の場合については、正回転の時は奇数の時と同じです
【追記:間違いを見つけた】
偶数・奇数で分けるのではなく、素数・合成数で分けるべきらしい
合成数の時については考えなおさなければいけない
aをkの約数とする。
位数がaの約数である同値類の要素の個数は合計2^a個ある。
よってメビウス関数μ(n)を使うと(メビウスの反転公式)
位数がaである同値類の要素の個数は Σμ(k/d)*2^d
位数がaである同値類の個数は Σμ(k/d)*2^d / a となる。
そのうち記述を整理し直します。
【追記ここまで】
負回転の時に、奇数個の時と同様にはいかないです。
このタイプの一般化ができていないので例を挙げておくしかないです。
・AB→Ba では位数4の同値類が1つ
・ABCD→BCDa では位数8の同値類が2つ
・ABCDEF→BCDEFa では位数4の同値類が1つ+位数12の同値類が5個
だと思います。
最後の位数4の同値類は具体的には次のものです。
A+B+c+d+E+F → a+B+C+d+e+F → a+b+C+D+e+f → A+b+c+D+E+f
<4>
巡回置換を合成するとき
(AB)について位数aの同値類と
(CD)について位数bの同値類を合成すると [(AB),(CD)は恣意的です]
合成された周期は最小公倍数となることと、
頂点の個数のつじつまを合わせることを考えると
【位数(aとbの最小公倍数)の同値類】が【(aとbの最大公約数)個】できる
ということになります。
例えば ABCDE→ BADEc を考えてみる
AB→BAについては @位数1の同値類が2個, A位数2の同値類が1個
CDE→DEcについては B位数2の同値類が1個, C位数6の同値類が1個
多項式の展開のように掛け合わせます
@Bから 位数2の同値類が2個
@Cから 位数6の同値類が2個
ABから 位数2の同値類が2個
ACから 位数6の同値類が2個
上2つの個数が2なのはもともとの@の個数が2個あるから
下2つの個数が2なのは位数の最大公約数が2である所から
従って求める同値類の個数は8個という風に求まります。
この結果は ABCDE -> BCaED : 60*2^8 という行に対応します
【追記】
分かった
負回転については同値類の位数は必ず偶数になるから
負回転を2回行ったものについて考察すれば良い。
ABCDEF→BCDEFa を2回行った回転は ABCDEF→CDEFab
それは(ACE)の負回転と(BDF)の負回転の合成である。
従って
@位数2の同値類が1個, A位数6の元が1個
B位数2の同値類が1個, C位数6の元が1個
を合成することで
位数2の同値類が2個+位数6の同値類が10個
という結果を得る。
2回行った回転についてこの結果だから
1回だけだったら位数は2倍、個数は半分で
「位数4の同値類が1つ+位数12の同値類が5個」と合致
記述の整理はどこか別の機会においてするとして
元のQ&Aに書かれた間違いの訂正を報告します:
誤:
ABCDE -> BCDAe : 30*2^9
ABCDE -> bcDAe : 180*2^9
ABCDE -> bcdae : 30*2^9
正:
ABCDE -> BCDAe : 30*2^10
ABCDE -> bcDAe : 180*2^10
ABCDE -> bcdae : 30*2^10
実際に ABCDE -> BCDAe について書きだしてみると次の10通り
ABCDE = ABCDe
abcde = abcdE
aBCDE = AbCDe = ABcDE = ABCde
aBCDe = AbCDE = ABcDe = ABCdE
AbcdE = aBcde = abCdE = abcDe
Abcde = aBcdE = abCde = abcDE
abCDE = AbcDe = ABcdE = aBCde
abCDe = AbcDE = ABcde = aBCdE
aBcDE = AbCde
aBcDe = AbCdE
この訂正によるa[5]の増分は (240*2^10-2^9)/1920 = 64 です
戻る