ぐんぐん群が分かる6(最終回)

前回までの話
ぐんぐん群がわかる
ぐんぐん群がわかる2
ぐんぐん群がわかる3
ぐんぐん群がわかる4
ぐんぐん群がわかる5

まずはトーティエント関数について。
トーティント関数は
φ(n)=1以上n以下でnと互いに素な自然数の個数
というものです。
今更ですが、同じ記号を異なる意味で使っているところがちょくちょくあります。
すべて異なる記号にできればよかったのですが、なかなか難しいですので。
文脈で判断できると思いますというか判断願います。

まず、a,bが互いに素な自然数のとき、φ(ab)=φ(a)φ(b)が成り立ちます。
ある自然数がabと互いに素であることは、その数がa、bの両方と互いに素であることと同値です。
1からabまでのab個の自然数を横にa個、縦にb個の長方形に並べると、
m行n列目の数は、(m-1)a+n　と表せます。
この数がaと互いに素であることは、nとaが互いに素であることと同値です。
従って各行のa個の数の中には、aと互いに素な数がφ(a)個あります。
a個の列の内、φ(a)個の列の数のみがaと互いに素というわけです。

そのような列の一つに着目すると、列内のb個の数をbで割った余りはすべて異なります。
仮にm1行目とm2行目の数をbで割った余りが同じだと仮定すると、
2つの数の差はbの倍数になりますが、それが(m2-m1)aと等しいことになり、
aとbが互いに素という条件に矛盾します。
aについての議論と同様にして、
各列のb個の数の中にはbと互いに素な数がφ(b)個あることが分かります。

以上より、a,bの両方と互いに素な数はφ(a)φ(b)個であり、φ(ab)=φ(a)φ(b)です。


n=1の場合、φ(1)=1です。
n≧2で、nの素因数が唯一つの場合
その素因数をpとすると、ある自然数mを使ってn=p^mと書けます。
pは2以上の自然数です。
1以上p^m以下の自然数をpで割った余りは、1,2,3,･･･,p-1,0を繰り返します。
余りの種類はp個なので、この繰り返しはp^(m-1)回です。
繰り返し1回分に注目すると、そのp個の数の中でp^mと互いに素でないのは余りが0のものだけ。
従って、互いに素な数が占める割合は(p-1)/p=1-1/p　です。
よってこの場合はφ(n)=n*(1-1/p)

nの素因数が2つ以上の場合
nを素因数分解して、n=p1^m1*p2^m2*･･･*pk^mkとなったとします。
(p1,p2,･･･,pkは相異なる素数、m1,m2,･･･,mkは自然数)
各素数の冪p1^m1,p2^m2,･･･,pk^mkは互いに素なので、
φ(n)= φ(p1^m1)*φ(p2^m2)*･･･*φ(pk^mk)
=p1^m1(1-1/p1)*p2^m2(1-1/p2)*・・・*pk^mk(1-1/pk)
=n*(1-1/p1)(1-1/p2)･･･(1-1/pk)
となります。
φ(n)はnの素因数が分かれば計算できます。


φ(1)=1,φ(2)=1,φ(3)=2
φ(4)=2,φ(5)=4
φ(6)=φ(2)*φ(3)=2
φ(7)=6,φ(8)=4,φ(9)=6
φ(10)=φ(2)*φ(5)=4
φ(11)=10
φ(12)=φ(3)*φ(4)=4
となっています。

では、具体的に円順列の個数を計算してみましょう。
例によって、黒玉4個と白玉4個の場合。
n=8,k=4,nとkの公約数は1,2,4ですので、
Σφ(s)C(n/s,k/s) [sはn,kの公約数]
=φ(1)C(8,4)+φ(2)C(4,2)+φ(4)C(2,1)=1*70+1*6+2*2=80
これをnで割ると、10個と求められます。

黒玉6個、白玉6個の場合は
φ(1)C(12,6)+φ(2)C(6,3)+φ(3)C(4,2)+φ(6)C(2,1)=1*924+1*20+2*2=960
960/12=80
というように簡単に計算できるのです！

数珠順列についても考えてみましょう。

反転に対する不変配置を考えてみます。
正n角形の中心を通る直線を対称軸とする対称変換で、
ある頂点をn個の頂点のどれかに移すn通りのものが考えられます。
n,kの偶奇によって、場合分けします。

・n,kがともに偶数の場合
反転の対称軸が2つの頂点を通るものと、頂点を通らないものの2種類があります。
それぞれはn/2個ずつです。
反転の対称軸が2つの頂点を通るとき、
残りの(n-2)個の石の配置が対称になりますので、
その(n-2)個に含まれる黒玉、白玉の数は偶数。
よって、対称軸上の2点に含まれる黒玉、白玉の数も偶数であり、0個または2個です。
つまり、対称軸上の2つの玉の色は同じです。
この対称軸で数珠を2つに切断して伸ばしてみると、左右対称で、
上下に同色の半片がくっついた状態になります。
上の半片を取り外して下の半片にくっつけてやると、それぞれn/2個の玉の列になります。
このn/2個の列内の並びは自由ですので、この反転に対して不変な配置の個数は、
C(n/2,k/2)です。




対称軸が頂点を通らないとき、
不変配置の個数は、C(n/2,k/2)個です。

それぞれの反転はn/2個ずつありますので、不変配置の個数の総計は、
n×C(n/2,k/2)
となります。

・nが偶数で、kが奇数の場合
反転の対称軸が2つの頂点を通るとき、
対称軸上の黒石の個数は奇数でないといけないので、1個です。
対称軸上の石の配置は2通り、
対称軸外の石の配置は、C(n/2-1,(k-1)/2)となります。

反転の対称軸が頂点を通らないとき、
kは奇数ですので、不変となる配置はありません。

よって、不変配置の個数の総計は、
n/2×2×C(n/2-1,(k-1)/2)=n×C(n/2-1,(k-1)/2)
となります。

・nが奇数でkが偶数の場合
任意の反転の対称軸は1つの頂点を通ります。
kが偶数なので、その頂点は黒石ではありません。
よって、石の配置の個数はC((n-1)/2,k/2)
これがn個あるので不変配置の個数の総計は、n×C((n-1)/2,k/2)個です。

・n,kがともに奇数の場合
任意の反転の対称軸は1つの頂点を通ります。
kが奇数なので、その頂点は黒石です。
よって、石の配置の個数はC((n-1)/2,(k-1)/2)
これがn個あるので不変配置の個数の総計は、n×C((n-1)/2,(k-1)/2)個です。

以上をあえて一つの式で表すと、kを2で割ったときの余りをrとして、
n×C([(n-r)/2],(k-r)/2)
と書けます。
([]はガウス記号。[x]はxを超えない最大の整数)
これが反転に対する不変配置の個数の総計です。

回転に対する不変配置の個数をP,反転に対する不変配置の個数をQとすると、
P=Σφ(s)C(n/s,k/s) [sはn,kの公約数]
Q=n×C([(n-r)/2],(k-r)/2)
と計算できることが分かりました。
(rはkを2で割ったときの余り)
円順列の総数は、P/n。
数珠順列の総数は、(P+Q)/2n です。

黒石4個、白石4個の場合、
r=0ですので、Q=8*C(4,2)=48
P=80でしたので、数珠順列の個数は(48+80)/16=8個です。

立方体の面の塗り分けなどでも使えます。
回転させて同じ配置になるものは同じとみなした場合の数え上げでは、
回転操作が群になりますので、バーンサイドの補題が使えます。
ルービックキューブの状態の総数を求めるのにも使えそうです。
同じとみなす作用が群になればどんなものにも使えるのです。

群についてはここでいったん終了としますが、他にも群論が絡んでくる面白い話はあります。
例えばバナッハ=タルスキーのパラドックス。
これについてはいつか書きたいと思います。