2 群作用と数え上げ

2
群作用と数え上げ
1. 置換群
群：結合法則をみたす 2 項演算が定義された集合で，単位元と逆元の存在が保証さ
れた代数系．
対称群：n 個の要素からなる集合 N の全単射全体の集合上に合成を演算とした群．
Sn で表す．対象を N = {1, 2, · · · , n} とし，全単射 a ∈ Sn は j が a(j) = aj に写
されるという対応を列挙して
(
)
1 2 3 ··· n
a=
a1 a2 a3 · · · an
積は写像の合成であり，たとえば
(
)(
) (
)
1 2 3
1 2 3
1 2 3
=
2 1 3
1 3 2
2 3 1
対称群の要素を置換とよぶ．
2. 補題
任意の置換 a ∈ Sn は，共通の要素を含まない巡回置換の積として，積の順序を除
いて一意的に表せる．
3. 共役関係
a, b ∈ G が共役 ⇔ ある c ∈ G が存在して cac−1 = b
共役は同値関係．
4. 補題
Sn の共役類は n の分割に一対一に対応する．
5. 群作用
G を群，X を集合とする．Aut X を X の全単射全体の集合に合成を積とした群．
G の X への作用とは，G から Aut X への準同型 φ : G → Aut X のこと．φ(a) = φa
で表すと，準同型という性質から
(1) φe = idG
(2) 任意の a, b ∈ G と x ∈ X に対して，φab (x) = φa (φb (x))
φ が単射のとき，作用は効果的であるという．
6. 用語
(1) a ∈ G の固定点集合とは
Fix a = {x ∈ X ; a(x) = x}
(2) x ∈ {1, 2, · · · , n} の固定群とは
Gx = {a ∈ G ; a(x) = x}
(3) x ∈ {1, 2, · · · , n} の軌道とは
Ox = {a(x) ∈ X ; a ∈ G}
G の作用に関して同じ軌道に属するという関係は同値関係であり，とくに G の作
用は X を軌道に類別する．
7. 補題
(1) Fix aba−1 = a Fix b，とくに固定点集合の濃度は共役不変．
(2) x ∈ X, y ∈ Ox に対して Gx , Gy は共役
(3) |Ox | = |G/Gx |
8. 証明
いずれも容易
9. 補題 (コーシー・フロベニウス)
G の有限集合 X への作用の軌道の個数は固定点集合の濃度の平均値，すなわち
1 ∑
|Fix a|
|G| a∈G
10. 証明
O1 , O2 , · · · , Om を G の軌道とし，|Oi | = ki とおき，さらに x ∈ Oi のとき kx = ki
とおく．そこで計算，
1 ∑
1 ∑
|Fix a| =
|Gx |
|G| a∈G
|G| x∈X
1 ∑ |G|
=
|G| x∈X kx
1 ∑ |G|
=
=m
ki
|G| i=1 ki
m
11. 置換群は N に作用
Sn = Aut N なので，Γ < Sn は，包含写像 Γ → Aut N が，Γ の N への作用と見
なせる．Γ < Sn を置換群とよぶ．
12. 補題
γ ∈ Sn に対し，σj (γ) を γ が含む長さ j の巡回置換の個数とする．
(1)
σ1 (γ) + 2σ2 (γ) + · · · + nσn (γ) = n
(2) σ(γ) = σ1 (γ) + σ2 (γ) + · · · + σn (γ) は γ で生成される巡回群 hγi の作用の軌道
の個数．
∑
σ1 (γ) σ2 (γ)
σ (γ)
(3)
x2
· · · xnn は共役類の濃度の母関数で，x = x1 = x2 = · · · = xn
γ∈Γ x1
とおくと軌道の個数が等しい元の個数の母関数．x = 1 とおくと Γ の濃度．
13. 証明
容易
14. 定義
置換群 Γ (⊂ Sn ) の巡回指数とは
1 ∑ σ1 (γ) σ2 (γ)
x
x2
· · · xσnn (γ)
|Γ| γ∈Γ 1
15. 群の作用に付随する写像の集合への作用
Γ を N = {1, 2, · · · , n} に作用する置換群とする．R を有限集合としたとき，
M = {f | f : N → R}
には，γ ∈ Γ, f ∈ M に対して
γf (x) = f (γ −1 (x))
として γf ∈ M を定めると，Γ の M への作用が定まる．実際
ef = f,
(γ · γ 0 )f = γγf0
が成り立つ．
16. 定理 (ポリア)
Γ の M への作用の軌道の個数は Γ の N への作用の巡回指数のすべての変数に |R|
を代入してえられる数に一致する．
17. 証明
コーシー・フロベニウスの補題を用い，Γ の M への作用の軌道の個数を，各元 γ ∈ Γ
の固定点の個数の平均値として計算する．
まず，f ∈ M が γ ∈ Γ の固定点であること，すなわち γf = f であることと，任意
の x ∈ N = {1, 2, · · · , n} に対し
γf (x) = f (γ −1 (x)) = f (x)
が成り立つことは同値である．この等式は γ が生成する Γ の部分群 H の作用の軌
道上では f が定数値であることを意味する．そこで σ(γ) を H = hγi の N への作
用の軌道の個数であったことを思い出すと，固定点の個数，すなわち軌道上は R の
一定の値を取る写像の個数は |R|σ(γ) . したがって求める数は
1 ∑ σ(γ)
1 ∑ σ1 (γ)+σ2 (γ)+···+σn (γ)
|R|
=
|R|
|Γ| γ∈Γ
|Γ| γ∈Γ
1 ∑ σ1 (γ) σ1 (γ)
=
|R|
|R|
· · · |R|σ1 (γ)
|Γ| γ∈Γ
18. 例
一つの球と二つの 4 面体を三つの箱に入れる入れ方の個数．
1
巡回指数は (x31 + x1 x2 ) であり，すべての変数に 3 を代入して 18 を得る．
2
19. 例
立方体の表面を n 色で塗分ける塗分け方の個数．
1 6
巡回指数は
(x + 3x21 x22 + 6x21 x4 + 6x32 + 8x23 ) であり，すべての変数に n を代入
24 1
して結果を得る．
20. オイラー関数
自然数 m ∈ N に対して
ϕ(m) = #{n ∈ Z ; 1 ≤ n ≤ m, (n, m) = 1}
で定まる関数をオイラー関数という．
21. 演習
(1) n ≤ 100 に対して ϕ(n) を計算せよ．
(2) p, q を互いに異なる素数とするとき ϕ(pq) = (p − 1)(q − 1) であることを示せ．
(3) p を素数とするとき ϕ(p2 ) を求めよ．
(4) (a, b) = 1 のとき，ϕ(ab) = ϕ(a)ϕ(b) を示せ．
(5) ϕ(120), ϕ(180) を計算せよ．
(6)
(1, 1) (2, 1) · · · (n, 1) (2, 1) (2, 2) · · · (n, 2) = ϕ(1)ϕ(2) · · · ϕ(n)
. . . . . . . . . . . . . . . . . . . . . . . .
(n, 1) (n, 2) · · · (n, n)
を示せ．
22. (重複円順列)
n 個の円周上の点を N 色で塗分ける塗分け方の個数．
1∑
n/d
巡回指数は
ϕ(d)xd であり，変数に N を代入して結果を得る．
n
d|n
23. 系
N = 1 とおけば，
1∑
ϕ(d) = 1,
n
d|n
とくに
∑
ϕ(d) = n
d|n
である．
24. 演習
(1) n (≤ 6) 個の頂点をもつ単純グラフの同型類の個数を求めよ．
(2) トーラス上の 3 × 3 のます目を r 色で塗分ける塗分け方の個数を求めよ．
(3) 対称群 Sn の巡回指数を求めよ．
(4) 正則表現の巡回指数を求めよ．
(5) 巡回指数に xj = aj1 + aj2 + · · · + akn を代入した多項式は，ポリアの定理の数え
上げの内訳と解釈できることを示せ．

Download Report