§E7.12Burnside の補題

最終更新

正方形の四頂点を二色で塗ると、塗り分けは全部で十六通りある。回転によって一致する塗り分けを同一視しても、その個数は十六を回転群の位数四で割った値にはならない。一色で塗った配置はすべての回転で固定される一方、一つの頂点だけを異なる色で塗った配置は恒等回転だけで固定されるからである。対称性を除いた個数を求めるには、配置ごとに異なる軌道の大きさを考慮する必要がある。

Burnside の補題は、有限群作用の軌道数を、群の各元が固定する点の個数の平均で表す。軌道を一つずつ列挙する代わりに対称変換ごとの不動点を数えることができるため、この補題は対称性を伴う数え上げの基本的な方法である。本記事では、Burnside の補題と正多角形の頂点塗り分けへの適用を扱う。

1 置換と群作用

定義 1.1. 有限集合VVの置換全体の群をSym⁡(V)\operatorname{Sym}(V)と書く。その部分群G≤Sym⁡(V)G\leq\operatorname{Sym}(V)をVV上の置換群 (permutation group) と呼ぶ。

定義 1.2. 有限群GGと有限集合XXに対し、写像

G×X⟶X,(g,x)⟼g⋅x G\times X\longrightarrow X,\qquad (g,x)\longmapsto g\cdot x

が

e⋅x=x,(gh)⋅x=g⋅(h⋅x) e\cdot x=x,\qquad (gh)\cdot x=g\cdot(h\cdot x)

を満たすとき、この写像をGGのXXへの左作用 (left action on a finite set) と呼ぶ。

1.1 塗り分けへの作用

定義 1.3. 頂点集合をVV、色集合をCCとする。塗り分け (coloring) は写像

f ⁣:V⟶C f\colon V\longrightarrow C

である。塗り分け全体の集合をCVC^Vと書く。

定義 1.4. 有限集合V,CV,C、有限群GG、準同型ρ ⁣:G→Sym⁡(V)\rho\colon G\to\operatorname{Sym}(V)に対し、塗り分け全体CVC^Vへの作用を

(g⋅f)(v)=f(ρ(g)−1(v)),すなわちg⋅f=f∘ρ(g)−1 (g\cdot f)(v)=f\bigl(\rho(g)^{-1}(v)\bigr), \qquad\text{すなわち}\qquad g\cdot f=f\circ\rho(g)^{-1}

と定める。この作用を塗り分けへの誘導作用 (induced action on colorings) と呼ぶ。

命題 1.5. 有限集合V,CV,C、有限群GG、群準同型

ρ ⁣:G⟶Sym⁡(V) \rho\colon G\longrightarrow\operatorname{Sym}(V)

に対し、

g⋅f=f∘ρ(g)−1(g∈G, f∈CV) g\cdot f=f\circ\rho(g)^{-1}\qquad(g\in G,\ f\in C^V)

と定める。この式によりGGのCVC^Vへの左作用が定められる。

証明.ρ(gh)=ρ(g)∘ρ(h)\rho(gh)=\rho(g)\circ\rho(h)であるから、

(gh)⋅f=f∘ρ(gh)−1=f∘ρ(h)−1∘ρ(g)−1=g⋅(h⋅f).\begin{aligned} (gh)\cdot f &=f\circ\rho(gh)^{-1}\\ &=f\circ\rho(h)^{-1}\circ\rho(g)^{-1}\\ &=g\cdot(h\cdot f). \end{aligned}

またe⋅f=fe\cdot f=fである。したがって、上の式により左作用が定められる。▨

命題 1.6. 二つの塗り分けf1,f2∈CVf_1,f_2\in C^Vが図形の対称変換によって一致することと、f1,f2f_1,f_2が同じGG-軌道に属することとは同値である。

証明. 塗り分けf2f_2がf1f_1に対称変換ggを施して得られることは、定義によりf2=g⋅f1f_2=g\cdot f_1と表される。等式f2=g⋅f1f_2=g\cdot f_1があるg∈Gg\in Gについて成り立つことは、f2∈G⋅f1f_2\in G\cdot f_1と同値である。▨

定義 1.7. 有限群GGが有限集合XXに作用するとする。x∈Xx\in Xに対し、

Stab⁡(x)={g∈G∣g⋅x=x} \Stab{x}=\{g\in G\mid g\cdot x=x\}

をxxの安定化群 (stabilizer) と呼ぶ。g∈Gg\in Gに対し、

Fix⁡X(g)={x∈X∣g⋅x=x} \operatorname{Fix}_X(g)=\{x\in X\mid g\cdot x=x\}

をggの不動点集合 (fixed-point set) と呼ぶ。

定理 1.8 (軌道安定化群定理). 有限群GGが有限集合XXに作用するとき、各x∈Xx\in Xに対して

∣G⋅x∣=∣G∣∣Stab⁡(x)∣ |G\cdot x|=\frac{|G|}{|\Stab{x}|}

が成り立つ。

証明.§E7.10 定理 4.5により、G⋅xG\cdot xと左剰余類集合G/Stab⁡(x)G/\Stab{x}の間に全単射がある。 Lagrange の定理を用いると

∣G/Stab⁡(x)∣=[G:Stab⁡(x)]=∣G∣∣Stab⁡(x)∣ |G/\Stab{x}|=[G:\Stab{x}]=\frac{|G|}{|\Stab{x}|}

である。▨

2 置換の巡回置換分解と固定される塗り分け

定義 2.1. 有限集合VVの置換σ\sigmaに対し、⟨σ⟩\langle\sigma\rangleのVVへの作用の軌道をσ\sigmaの巡回軌道 (cycle orbit) と呼ぶ。巡回軌道の個数をc(σ)c(\sigma)と書く。

命題 2.2. 有限集合V,CV,Cと∣C∣=k|C|=kに対し、置換σ∈Sym⁡(V)\sigma\in\operatorname{Sym}(V)が固定する塗り分けの個数は

∣Fix⁡CV(σ)∣=kc(σ) \left|\operatorname{Fix}_{C^V}(\sigma)\right|=k^{c(\sigma)}

である。V=C=∅V=C=\varnothingの場合に現れる000^0は11とする。

証明.σ⋅f=f\sigma\cdot f=fであることは、

f(σ−1(v))=f(v)(v∈V) f(\sigma^{-1}(v))=f(v)\qquad(v\in V)

が成り立つことと同値である。この等式を繰り返し用いると、ffは各巡回軌道上で一定である。逆に、各巡回軌道上で一定な塗り分けはσ\sigmaによって固定される。各巡回軌道にはkk通りの色を独立に選ぶことができるから、不動点数はkc(σ)k^{c(\sigma)}である。▨

3 Burnside の補題

定理 3.1 (Burnside の補題). 有限群GGが有限集合XXに作用するとき、軌道数は

∣X/G∣=1∣G∣∑g∈G∣Fix⁡X(g)∣ |X/G| =\frac{1}{|G|}\sum_{g\in G}|\operatorname{Fix}_X(g)|

である。

証明. 組の集合

Ω={(g,x)∈G×X∣g⋅x=x} \Omega=\{(g,x)\in G\times X\mid g\cdot x=x\}

を考える。第一成分ggを先に固定して数えると、

∣Ω∣=∑g∈G∣Fix⁡X(g)∣ |\Omega|=\sum_{g\in G}|\operatorname{Fix}_X(g)|

である。

第二成分xxを先に固定して数えると、

∣Ω∣=∑x∈X∣Stab⁡(x)∣ |\Omega|=\sum_{x\in X}|\Stab{x}|

である。軌道O⊆X\mathcal O\subseteq Xとy∈Oy\in\mathcal Oに対し、G⋅y=OG\cdot y=\mathcal Oである。§E7.10 定理 4.5により

∣Stab⁡(y)∣=∣G∣∣O∣|\Stab{y}|=\frac{|G|}{|\mathcal O|}

であるから、

∑y∈O∣Stab⁡(y)∣=∣O∣∣G∣∣O∣=∣G∣\sum_{y\in\mathcal O}|\Stab{y}| =|\mathcal O|\frac{|G|}{|\mathcal O|} =|G|

である。したがって、すべての軌道について和を取ると

∣Ω∣=∣X/G∣ ∣G∣ |\Omega|=|X/G|\,|G|

となる。二つの計数結果を等置し、∣G∣|G|で割れば主張を得る。▨

定理 3.2 (塗り分けに対する Burnside の補題). 有限群GGが準同型ρ ⁣:G→Sym⁡(V)\rho\colon G\to\operatorname{Sym}(V)によって有限頂点集合VVに作用し、有限色集合CCの元の個数をkkとする。対称性を除いた塗り分けの個数は

∣CV/G∣=1∣G∣∑g∈Gkc(ρ(g)) |C^V/G| =\frac{1}{|G|}\sum_{g\in G}k^{c(\rho(g))}

である。

証明.命題 2.2により、各g∈Gg\in Gが固定する塗り分けの個数はkc(ρ(g))k^{c(\rho(g))}である。定理 3.1をX=CVX=C^Vに適用すると、主張の等式を得る。▨

3.1 正方形の二色塗り分けの軌道数

例 3.3. 正方形の四頂点を二色で塗り、回転によって一致する塗り分けを同一視する。回転群C4C_4の各元が固定する塗り分けの個数は次の通りである。

回転角巡回軌道の個数不動点数0424=16π/212π222=43π/212\begin{array}{c|c|c} \text{回転角} & \text{巡回軌道の個数} & \text{不動点数}\\ \hline 0 & 4 & 2^4=16\\ \pi/2 & 1 & 2\\ \pi & 2 & 2^2=4\\ 3\pi/2 & 1 & 2 \end{array}

したがって、Burnside の補題から軌道数は

16+2+4+24=6 \frac{16+2+4+2}{4}=6

である。

注意 3.4. 総数1616を∣C4∣=4|C_4|=4で割ると44になるが、正しい答えは66である。一色だけを用いる塗り分けはすべての回転で固定される。一つの頂点だけを一方の色で塗る塗り分けは、恒等回転以外では固定されない。したがって、すべての軌道が四元を持つわけではない。

4 正nn角形の回転

定義 4.1. 正の整数nnに対し、Z/nZ\Z/n\Zの置換rrをr(a)=a+1r(a)=a+1で定める。整数jjに対してrj(a)=a+jr^j(a)=a+jである。n≥3n\geq3の場合は正nn角形の頂点をZ/nZ\Z/n\Zと同一視し、rjr^jをjj頂点分の回転 (rotation) とする。nnとjjの最大公約数をgcd⁡(n,j)\gcd(n,j)と書き、gcd⁡(n,0)=n\gcd(n,0)=nとする。

補題 4.2. 正の整数nnと整数jjに対し、n∣mjn\mid mjを満たす正の整数mmが存在する。そのようなmmのうち最小のものは

ngcd⁡(n,j) \frac{n}{\gcd(n,j)}

である。

証明.d=gcd⁡(n,j)d=\gcd(n,j)と置き、

A={m∈Z∣m>0, n∣mj} A=\{m\in\Z\mid m>0,\ n\mid mj\}

と置く。m=nm=nはn∣njn\mid njを満たすから、AAは空でない。AAの最小元をttとする。

ddはnnとjjの公約数であるから、n/dn/dは正の整数であり、j/dj/dは整数である。等式(n/d)j=n(j/d)(n/d)j=n(j/d)からn∣(n/d)jn\mid(n/d)jが従うので、n/d∈An/d\in Aである。ttの最小性によりt≤n/dt\leq n/dである。

整数の除法によってn=qt+sn=qt+s、0≤s<t0\leq s<tと書く。n∣njn\mid njとn∣tjn\mid tjから

n∣(n−qt)j=sj n\mid(n-qt)j=sj

が従う。s>0s>0ならばs∈As\in Aとなり、ttの最小性に反する。したがってs=0s=0であり、ttはnnを割り切る。

u=n/tu=n/tと置くと、uuは正の整数である。n∣tjn\mid tjはtu∣tjtu\mid tjと書き直すことができ、t>0t>0であるからu∣ju\mid jである。またu∣nu\mid nである。したがってuuはnnとjjの公約数であり、ddが最大公約数であることからu≤du\leq dである。ゆえにt=n/u≥n/dt=n/u\geq n/dである。

t≤n/dt\leq n/dとt≥n/dt\geq n/dからt=n/dt=n/dを得る。▨

補題 4.3. 正の整数nnと整数jjに対し、rrをr(a)=a+1r(a)=a+1で定めるZ/nZ\Z/n\Zの置換とする。このとき

∣⟨rj⟩∣=ngcd⁡(n,j) \left|\langle r^j\rangle\right|=\frac{n}{\gcd(n,j)}

が成り立つ。さらに、rjr^jの巡回軌道はいずれもn/gcd⁡(n,j)n/\gcd(n,j)個の頂点からなる。

証明.t=n/gcd⁡(n,j)t=n/\gcd(n,j)と置く。整数mmに対し、(rj)m(r^j)^mはa∈Z/nZa\in\Z/n\Zをa+mja+mjへ写す。したがって、次の三つの条件は同値である。

  1. あるa∈Z/nZa\in\Z/n\Zが存在して(rj)m(a)=a(r^j)^m(a)=aが成り立つ。
  2. n∣mjn\mid mjが成り立つ。
  3. すべてのa∈Z/nZa\in\Z/n\Zについて(rj)m(a)=a(r^j)^m(a)=aが成り立つ。すなわち(rj)m(r^j)^mは恒等写像である。

実際、Z/nZ\Z/n\Zにおいてa+mj=aa+mj=aが成り立つことはn∣mjn\mid mjと同値であり、条件n∣mjn\mid mjはaaに依存しない。

補題 4.2と上の同値関係により、(rj)m(r^j)^mが恒等写像となる最小の正の整数mmはttである。したがってrjr^jの位数はttであり、§E7.2 定理 5.1により

⟨rj⟩={(rj)s∣0≤s<t}\langle r^j\rangle=\{(r^j)^s\mid0\leq s<t\}

であり、このtt個の元は相異なる。したがって∣⟨rj⟩∣=t|\langle r^j\rangle|=tである。

⟨rj⟩\langle r^j\rangleの元(rj)m(r^j)^mがaaを固定するならば、上の同値によって(rj)m(r^j)^mは恒等写像である。したがってaaの安定化群は単位元だけからなる。定理 1.8により、⟨rj⟩\langle r^j\rangleの作用によるaaの軌道の要素数は

∣⟨rj⟩∣1=t \frac{\left|\langle r^j\rangle\right|}{1}=t

である。aaは任意に取ったから、rjr^jの巡回軌道はいずれもtt個の頂点からなる。▨

注意 4.4. 一般の置換では、巡回軌道の長さは一致しない。たとえばV={1,2,3,4,5}V=\{1,2,3,4,5\}の置換σ\sigmaをσ(1)=2\sigma(1)=2、σ(2)=1\sigma(2)=1、σ(3)=4\sigma(3)=4、σ(4)=5\sigma(4)=5、σ(5)=3\sigma(5)=3で定めると、σ\sigmaの巡回軌道は{1,2}\{1,2\}と{3,4,5}\{3,4,5\}であり、長さは異なる。補題 4.3で長さが一致するのは、⟨rj⟩\langle r^j\rangleの作用において各頂点の安定化群が単位元だけからなり、軌道安定化群定理により与えられる軌道の要素数が頂点によらないからである。

命題 4.5. 正の整数nnと整数jjに対し、rj(a)=a+jr^j(a)=a+jで定めるZ/nZ\Z/n\Zの置換の巡回軌道数は

c(rj)=gcd⁡(n,j) c(r^j)=\gcd(n,j)

である。

証明.t=n/gcd⁡(n,j)t=n/\gcd(n,j)と置く。補題 4.3により、rjr^jの巡回軌道はいずれもちょうどtt個の頂点からなる。§E7.10 命題 4.3により、巡回軌道の全体はZ/nZ\Z/n\Zを互いに素な部分集合へ分割する。したがって§D2.2 定理 2.1により

n=c(rj) t n=c(r^j)\,t

であり、

c(rj)=nt=gcd⁡(n,j) c(r^j)=\frac nt=\gcd(n,j)

である。▨

定理 4.6.n≥3n\geq3、k≥1k\geq1とする。正nn角形の頂点をkk色で塗り、回転によって一致する塗り分けを同一視する。その個数は

Nrot(n,k)=1n∑j=0n−1kgcd⁡(n,j)=1n∑d∣nφ(d)kn/d N_{\mathrm{rot}}(n,k) =\frac{1}{n}\sum_{j=0}^{n-1}k^{\gcd(n,j)} =\frac{1}{n}\sum_{d\mid n}\varphi(d)k^{n/d}

である。ここでφ\varphiは Euler のトーシェント関数である。この関数の定義は§D2.3 定義 3.1で扱った。

証明. 回転群Cn=⟨r⟩C_n=\langle r\rangleに定理 3.2を適用する。命題 4.5により、rjr^jの不動点数はkgcd⁡(n,j)k^{\gcd(n,j)}である。この不動点数を Burnside の補題の式へ代入すると、第一の等式を得る。

ddをnnの正の約数とし、e=n/de=n/dと置く。0≤j<n0\leq j<nを満たす整数jjについて、

gcd⁡(n,j)=e⟺j=ea,0≤a<d,gcd⁡(a,d)=1 \gcd(n,j)=e \quad\Longleftrightarrow\quad j=ea,\quad 0\leq a<d,\quad \gcd(a,d)=1

が成り立つ。

j=eaj=ea、0≤a<d0\leq a<dと仮定する。正の整数mmに対し、n∣mjn\mid mjはed∣meaed\mid meaと書き直すことができ、e>0e>0であるから、この条件はd∣mad\mid maと同値である。補題 4.2により、n∣mjn\mid mjを満たす最小の正の整数はn/gcd⁡(n,j)n/\gcd(n,j)であり、d∣mad\mid maを満たす最小の正の整数はd/gcd⁡(d,a)d/\gcd(d,a)である。二つの条件が同値であることから

ngcd⁡(n,j)=dgcd⁡(d,a),すなわちgcd⁡(n,j)=egcd⁡(d,a) \frac{n}{\gcd(n,j)}=\frac{d}{\gcd(d,a)}, \qquad\text{すなわち}\qquad \gcd(n,j)=e\gcd(d,a)

を得る。したがって、gcd⁡(n,j)=e\gcd(n,j)=eとgcd⁡(a,d)=1\gcd(a,d)=1とは同値である。gcd⁡(n,j)=e\gcd(n,j)=eとすると、eeはjjを割り切るからj=eaj=eaと書くことができ、0≤j<n=ed0\leq j<n=edから0≤a<d0\leq a<dである。以上により上の同値が成り立つ。

11以上dd以下でddと互いに素な整数の個数はφ(d)\varphi(d)である。d≥2d\geq2の場合、0≤a<d0\leq a<dでddと互いに素な整数aaの個数はこれに等しく、d=1d=1の場合はどちらの個数も11である。したがって、gcd⁡(n,j)=n/d\gcd(n,j)=n/dを満たすjj（0≤j<n0\leq j<n）はちょうどφ(d)\varphi(d)個あり、命題 4.5により、そのような回転rjr^jの巡回軌道数はn/dn/dである。gcd⁡(n,j)\gcd(n,j)はnnの正の約数であるから、d=n/gcd⁡(n,j)d=n/\gcd(n,j)もまたnnの正の約数であり、各jj（0≤j<n0\leq j<n）はこのddに対してちょうど一度数えられる。したがってddをnnの正の約数全体にわたって動かせば、

∑j=0n−1kgcd⁡(n,j)=∑d∣nφ(d)kn/d \sum_{j=0}^{n-1}k^{\gcd(n,j)} =\sum_{d\mid n}\varphi(d)k^{n/d}

を得る。▨

例 4.7. 回転だけを同一視するとき、

Nrot(6,3)=16(36+3+32+33+32+3)=7806=130\begin{aligned} N_{\mathrm{rot}}(6,3) &=\frac{1}{6}\left( 3^6+3+3^2+3^3+3^2+3 \right)\\ &=\frac{780}{6}=130 \end{aligned}

である。

5 正nn角形と二面体群D2nD_{2n}

定理 5.1.n≥3n\geq3、k≥1k\geq1とする。正nn角形の頂点をkk色で塗り、位数2n2nの二面体群D2nD_{2n}の回転または鏡映によって一致する塗り分けを同一視する。その個数は

Ndih(n,k)=12n(∑d∣nφ(d)kn/d+Rn(k)) N_{\mathrm{dih}}(n,k) =\frac{1}{2n} \left( \sum_{d\mid n}\varphi(d)k^{n/d}+R_n(k) \right)

である。ただし、

Rn(k)={nk(n+1)/2,n が奇数のとき,n2(kn/2+1+kn/2),n が偶数のとき R_n(k)= \begin{cases} nk^{(n+1)/2}, & n\text{ が奇数のとき},\\[4pt] \dfrac n2\left(k^{n/2+1}+k^{n/2}\right), & n\text{ が偶数のとき} \end{cases}

である。

証明. 回転による不動点数の和は定理 4.6の証明から

∑d∣nφ(d)kn/d \sum_{d\mid n}\varphi(d)k^{n/d}

である。

nnが奇数ならば、各鏡映軸は一つの頂点とその対辺の中点を通る。この鏡映は一つの頂点を固定し、残りのn−1n-1個の頂点を(n−1)/2(n-1)/2個の二点軌道に分ける。したがって巡回軌道数は(n+1)/2(n+1)/2であり、一つの鏡映の不動塗り分け数はk(n+1)/2k^{(n+1)/2}である。鏡映はnn個あるから、

Rn(k)=nk(n+1)/2 R_n(k)=nk^{(n+1)/2}

である。

nnが偶数ならば、鏡映は二種類ある。向かい合う二頂点を通る軸に関する鏡映はn/2n/2個あり、二頂点を固定して残りを二点ずつ交換する。巡回軌道数は

2+n−22=n2+1 2+\frac{n-2}{2}=\frac n2+1

である。向かい合う二辺の中点を通る軸に関する鏡映もn/2n/2個あり、頂点を固定せず、頂点をn/2n/2個の二点軌道に分ける。したがって、鏡映による不動点数の和は

Rn(k)=n2kn/2+1+n2kn/2 R_n(k)=\frac n2k^{n/2+1}+\frac n2k^{n/2}

である。最後に、位数2n2nのD2nD_{2n}に Burnside の補題を適用すれば主張を得る。▨

例 5.2. 正六角形の頂点を三色で塗り、二面体群D12D_{12}の作用で一致する塗り分けを同一視する。回転による不動点数の和は

36+2⋅3+2⋅32+33=780 3^6+2\cdot3+2\cdot3^2+3^3=780

である。頂点を二つ固定する鏡映は三つあり、それぞれ34=813^4=81個の塗り分けを固定する。頂点を固定しない鏡映も三つあり、それぞれ33=273^3=27個の塗り分けを固定する。したがって、

Ndih(6,3)=780+3⋅81+3⋅2712=92 N_{\mathrm{dih}}(6,3) =\frac{780+3\cdot81+3\cdot27}{12} =92

である。

注意 5.3.定理 3.2により与えられるのは軌道の個数であり、各軌道の代表となる塗り分けではない。代表を求めるには、配置を一つずつ調べ、すでに得た軌道に属するかどうかを別に判定する必要がある。

6 演習

問題 6.1.

  1. 正三角形の頂点をkk色で塗り、回転だけを同一視する場合の軌道数を求めよ。
  2. 正方形の頂点を二色で塗り、二面体群D8D_8の作用で一致する塗り分けを同一視する場合の軌道数を求めよ。
  3. nnが偶数のとき、二面体群D2nD_{2n}に含まれる二種類の鏡映の巡回軌道数がそれぞれn/2+1n/2+1とn/2n/2になることを、頂点の対応を図示して確かめよ。
  4. 有限群GGが二つ以上の元をもつ有限集合XXに可移に作用するとする。定理 3.1を用いて、XXのどの点も固定しないg∈Gg\in Gが存在することを示せ。また、XXが一点集合の場合にはこの結論が成り立たないことを確かめよ。
解答 (演習の要点).
  1. 恒等回転はk3k^3個の塗り分けを固定し、二つの非自明な回転はそれぞれ三頂点を一つの巡回軌道にするためkk個を固定する。Burnside の補題により軌道数は k3+2k3\frac{k^3+2k}{3} である。
  2. 四つの回転による不動点数の和は24+2+22+2=242^4+2+2^2+2=24である。二つの頂点軸の鏡映はそれぞれ三つの巡回軌道を持ち、二つの辺軸の鏡映はそれぞれ二つの巡回軌道を持つため、鏡映による和も2⋅23+2⋅22=242\cdot2^3+2\cdot2^2=24である。したがってD8D_8による軌道数は 24+248=6\frac{24+24}{8}=6 となる。
  3. 頂点を通る軸の鏡映は二頂点を固定し、残るn−2n-2頂点を(n−2)/2(n-2)/2個の二点軌道に分けるので、巡回軌道数は2+(n−2)/2=n/2+12+(n-2)/2=n/2+1である。辺の中点を通る軸の鏡映は頂点を固定せず、全頂点をn/2n/2個の二点軌道に分ける。
  4. 作用は可移であるから軌道はただ一つであり、定理 3.1により∑g∈G∣Fix⁡X(g)∣=∣G∣\sum_{g\in G}|\operatorname{Fix}_X(g)|=|G|である。単位元eeはすべての点を固定するので∣Fix⁡X(e)∣=∣X∣≥2|\operatorname{Fix}_X(e)|=|X|\ge2である。すべてのg∈Gg\in Gが少なくとも一つの点を固定すると仮定すると、g≠eg\ne eについて∣Fix⁡X(g)∣≥1|\operatorname{Fix}_X(g)|\ge1であるから ∑g∈G∣Fix⁡X(g)∣≥∣X∣+(∣G∣−1)≥∣G∣+1\sum_{g\in G}|\operatorname{Fix}_X(g)|\ge|X|+(|G|-1)\ge|G|+1 となり、上の等式に反する。したがって∣Fix⁡X(g)∣=0|\operatorname{Fix}_X(g)|=0を満たすg∈Gg\in Gが存在する。XXが一点集合{x}\{x\}の場合は、すべてのggがg⋅x=xg\cdot x=xを満たすので、どの点も固定しない元は存在しない。上の評価で∣X∣≥2|X|\ge2を用いたのはこのためである。

▨

参考文献

  1. Peter J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, Cambridge, 1994.群作用による軌道の数え上げを参考にした。
  2. J. H. van Lint and R. M. Wilson, A Course in Combinatorics, 2nd ed., Cambridge University Press, 2001.Burnside の補題と Pólya の数え上げを参考にした。

前提記事