バーンサイドの補題

正六角形の板の $6$ つの頂点のそれぞれを、赤・青・白の $3$ 色のうちいずれか $1$ 色で塗る（使わない色があってもよい）。板を中心のまわりに回転して互いに重ね合わせられる塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。ただし、裏返し（鏡映）による同一視は行わない。

円板を中心から $6$ 等分して、$6$ 個の合同な扇形をつくる。それぞれの扇形を白か黒のどちらか $1$ 色で塗る（どちらかの色を使わなくてもよい）。円板を中心のまわりに回転して重ね合わせられる塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。ただし、円板の裏返しによる同一視は行わない。

正方形の $4$ つの頂点のそれぞれを、赤・青・黄の $3$ 色のうちいずれか $1$ 色で塗る（使わない色があってもよい）。正方形をその中心のまわりに回転させて互いに重ね合わせられる塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。ただし、裏返し（鏡映）による同一視は行わない。

$7$ 変数のブール関数とは写像 $f:\{0,1{\}}^7\to \{0,1\}$ のこととする。$7$ 変数のブール関数 $f$ で、次の 2 つの条件をともに満たすものの個数を求めよ。

$(1)$（巡回不変性）すべての $(x_1,\dots ,x_7)\in \{0,1{\}}^7$ に対して $$f(x_1,x_2,\dots ,x_7)=f(x_2,x_3,\dots ,x_7,x_1).$$

$(2)$（自己双対性）すべての $(x_1,\dots ,x_7)\in \{0,1{\}}^7$ に対して $$f(1-x_1,1-x_2,\dots ,1-x_7)=1-f(x_1,x_2,\dots ,x_7).$$

正四面体の $6$ 本の辺のそれぞれを、赤・青・黄の $3$ 色のうちのどれか $1$ 色で塗る。ただし、$3$ 色すべてを少なくとも $1$ 回ずつ使うものとする。正四面体の回転（向きを保つ合同変換）で互いに重ね合わせられる塗り方は同じとみなすとき、異なる塗り方は何通りあるか求めよ。

$4\times 4$ のマス目（16 個の正方形のマスからなる正方形の盤）に、区別のつかない 4 個の石を、どの 2 個も同じマスに入らないように置く。盤を回転または裏返し（正方形の対称移動、全部で 8 通り）によって重ね合わせられる置き方は同じものとみなすとき、異なる置き方は何通りあるか。

正四面体の 6 本の辺のそれぞれを、赤・青・黄の 3 色のうちいずれか 1 色で塗る（使わない色があってもよい）。正四面体の回転によって互いに重ね合わせられる塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。ただし、裏返し（鏡映）による同一視は行わない。

赤い玉 4 個と青い玉 6 個（同じ色の玉どうしは区別しない）の計 10 個を、円周上に等間隔に並べた 10 か所に 1 個ずつ置き、ひもを通して輪（ブレスレット）を作る。輪の回転および裏返しによって互いに重ね合わせられる並べ方は同じものとみなすとき、異なる輪は何通りできるか。

${\mathbb{F}}_7$ を位数 $7$ の有限体とし、$$G=\{f_{a,b}:{\mathbb{F}}_7\to {\mathbb{F}}_7,f_{a,b}(x)=ax+b\mid a\in {\mathbb{F}}_7^{\times },b\in {\mathbb{F}}_7\}$$ を写像の合成に関する群（位数 $42$）とする。${\mathbb{F}}_7$ の各元に赤・青・緑の $3$ 色のいずれかを塗る塗り方全体の集合を $X$ とする（$|X|=3^7$）。$c\in X$ を写像 $c:{\mathbb{F}}_7\to \{\text{赤},\text{青},\text{緑}\}$ とみなし、$g\in G$ を $(g\cdot c)(x)=c(g^{-1}(x))$ によって $X$ に作用させる。この作用の軌道の個数を求めよ。

${\mathbb{F}}_5$ を位数 $5$ の有限体とし、$$G=\{{\phi }_{a,b}:{\mathbb{F}}_5\to {\mathbb{F}}_5,{\phi }_{a,b}(x)=ax+b\mid a\in {\mathbb{F}}_5^{\times },b\in {\mathbb{F}}_5\}$$ を写像の合成を積とする群（位数 $20$）とする。写像 $f:{\mathbb{F}}_5\to \{1,2,3\}$ 全体の集合を $X$ とし（$|X|=3^5$）、$G$ は $X$ に $$(g\cdot f)(x)=f\left(g^{-1}(x)\right)(g\in G,f\in X,x\in {\mathbb{F}}_5)$$ によって作用する。この作用による $X$ の軌道の個数を求めよ。

$n$, $k$ を正の整数とし、$\phi$ をオイラー関数（正の整数 $d$ に対し、$1\le s\le d$ で $\gcd (s,d)=1$ を満たす整数 $s$ の個数）とする。このとき
$$\sum _{d\mid n}\phi (d)k^{n/d}$$
は $n$ で割り切れることを、バーンサイドの補題を用いて証明せよ。ここで ${\sum }_{d\mid n}$ は $n$ の正の約数 $d$ すべてについての和を表す。

ただし、バーンサイドの補題（有限群 $G$ が有限集合 $X$ に作用するとき、軌道の個数は $\frac{1}{|G|}\sum _{g\in G}|\mathrm{Fix}(g)|$ に等しい。$\mathrm{Fix}(g)=\{x\in X:gx=x\}$）と、整数 $a,b$（少なくとも一方は $0$ でない）に対して $ax+by=\gcd (a,b)$ を満たす整数 $x,y$ が存在することは用いてよい。

$4\times 4$ のマス目（$16$ 個の正方形のマス）から、ちょうど $4$ マスを選んで黒く塗り、残りの $12$ マスを白く塗る。マス目全体（正方形）の対称変換、すなわち中心のまわりの $0^{\circ },90^{\circ },180^{\circ },270^{\circ }$ の回転と、$4$ 本の対称軸（縦・横の中線 $2$ 本と対角線 $2$ 本）に関する裏返しの計 $8$ 個の変換のいずれかで互いに重ね合わせられる塗り方は同じものとみなす。このとき、異なる塗り方は何通りあるか。

$3\times 3$ のマス目（正方形の盤）の $9$ 個のマスのうち、ちょうど $4$ 個を黒で、残りの $5$ 個を白で塗る。正方形の対称変換群（中心のまわりの $0^{\circ },90^{\circ },180^{\circ },270^{\circ }$ の回転と、$4$ 本の対称軸に関する裏返しの、合わせて $8$ 個の変換からなる二面体群）によって互いに重ね合わせられる塗り方は同じものとみなす。異なる塗り方は何通りあるか。

正八面体の $8$ つの面を、赤・青・緑の $3$ 色で塗る。ただし、赤の面がちょうど $2$ 枚、青の面がちょうど $3$ 枚、緑の面がちょうど $3$ 枚となるように塗る。正八面体の回転（空間内の向きを保つ合同変換で正八面体を自分自身に重ねるもの、全部で $24$ 個）によって互いに移り合う塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。

立方体の 12 本の辺のうち、ちょうど 6 本を赤、残りの 6 本を青で塗る。立方体の回転によって互いに重ね合わせられる塗り方は同じものとみなすとき、異なる塗り方は何通りあるか。ただし、裏返し（鏡映）による同一視は行わない。

成分がすべて $0$ または $1$ である $3\times 3$ 行列全体の集合を $X$ とする（$|X|=2^9$）。$A,B\in X$ について、$A$ に「行の並べ替え」「列の並べ替え」「転置」の操作を有限回（$0$ 回も含む）くり返して $B$ が得られるとき、$A$ と $B$ は同値であるという。この同値関係による $X$ の同値類の個数を求めよ。

有限群 $G$ が有限集合 $X$ に（左から）推移的に作用しているとし、$n=|X|\ge 2$ とする。$g\in G$ に対し $\mathrm{Fix}(g)=\{x\in X\mid gx=x\}$ とおき、不動点をもたない元全体を $D=\{g\in G\mid \mathrm{Fix}(g)=\varnothing \}$ とする。このとき
$$\frac{|D|}{|G|}\ge \frac{1}{n}$$
が成り立つことを証明せよ。ただし、バーンサイドの補題「有限群 $H$ が有限集合 $Y$ に作用するとき、軌道の個数は $\frac{1}{|H|}\sum _{h\in H}|\{y\in Y\mid hy=y\}|$ に等しい」は用いてよい。