離散数学・組合せ論の問題

方針: $n$ 個の位置を $k$ 色で塗る方法全体に巡回群を回転で作用させ、バーンサイドの補題を使う。軌道の個数は整数なので、${\sum }_g|\mathrm{Fix}(g)|$ は $|G|=n$ で割り切れる。この和が問題の式に等しいことを示す。以下、$\gcd (0,n)=n$ とする。

設定。 ${\mathbb{Z}}_n=\mathbb{Z}/n\mathbb{Z}=\{0,1,\dots ,n-1\}$（加法は $n$ を法とする）とし、$X$ を写像 $c:{\mathbb{Z}}_n\to \{1,\dots ,k\}$ 全体の集合とする（$|X|=k^n$）。$r\in {\mathbb{Z}}_n$ に対し $(r\cdot c)(i)=c(i-r)$ と定めると、$0\cdot c=c$、$(r\cdot (s\cdot c))(i)=(s\cdot c)(i-r)=c(i-r-s)=((r+s)\cdot c)(i)$ なので、これは位数 $n$ の加法群 $G={\mathbb{Z}}_n$ の $X$ への作用である。$G$, $X$ はともに有限なので、バーンサイドの補題より軌道の個数を $N$ とすると
$$N=\frac{1}{n}\sum _{r=0}^{n-1}|\mathrm{Fix}(r)|.\text{\hspace{1em}(1)}$$

ステップ 1: $|\mathrm{Fix}(r)|=k^{\gcd (r,n)}$。 $r\in \{0,\dots ,n-1\}$ を固定し、$g=\gcd (r,n)$ とおく（$n\ge 1$ なので定義され、$r=0$ のとき $g=n$）。$H=\{tr:t\in \mathbb{Z}\}\subseteq {\mathbb{Z}}_n$（$r$ が生成する部分群）とする。

(i) $H=\{0,g,2g,\dots ,(n/g-1)g\}$ であること: $g\mid r$ かつ $g\mid n$ なので、$tr$ を $n$ で割った余りは $g$ の倍数で、$H$ は右辺に含まれる。逆に、用いてよい事実（$n\ne 0$ なので使える）から $ar+bn=g$ となる整数 $a,b$ があり、${\mathbb{Z}}_n$ で $g=ar\in H$、したがって $g$ の倍数はすべて $H$ に入る。右辺は $0\le jg<n$ を満たす $n/g$ 個の相異なる元なので $|H|=n/g$。$H$ は部分群なので、${\mathbb{Z}}_n$ は $H$ の剰余類 $i+H$ によって、それぞれ $|H|$ 個の元をもつちょうど $n/|H|=g$ 個の類に分割される。

(ii) $c\in \mathrm{Fix}(r)$ $⟺$ $c$ が各剰余類 $i+H$ の上で一定: $c\in \mathrm{Fix}(r)$ はすべての $i$ で $c(i-r)=c(i)$、すなわち（$i$ を $i+r$ に置き換えて）すべての $i$ で $c(i)=c(i+r)$ と同値である。これが成り立てば、$t$ についての帰納法で 0 以上のすべての整数 $t$ に対して $c(i)=c(i+tr)$ となる。${\mathbb{Z}}_n$ で $nr=0$ なので、任意の整数 $t$ について $tr$ は $t$ を $n$ で割った余り $t^{\prime }$ $(0\le t^{\prime }<n)$ を用いた $t^{\prime }r$ に等しく、$H$ のすべての元は $0\le t<n$ の $tr$ として現れる。よって $c$ は $i+H$ 上で一定である。逆に各剰余類上で一定なら、$i+r\in i+H$ なので $c(i)=c(i+r)$ がすべての $i$ で成り立ち、$c\in \mathrm{Fix}(r)$。

(i), (ii) より、固定される塗り方は $g$ 個の剰余類それぞれに色を 1 つずつ選ぶことと 1 対 1 に対応し、$|\mathrm{Fix}(r)|=k^g=k^{\gcd (r,n)}$。

ステップ 2: 和を約数ごとにまとめる。 $n$ の正の約数 $e$ に対して、$A_e=\{r\in \{0,\dots ,n-1\}:\gcd (r,n)=e\}$ とおく。$\gcd (r,n)$ は $n$ の正の約数なので、$\{0,\dots ,n-1\}$ はこれらの $A_e$ に分割される。$r\in A_e$ なら $e\mid r$ なので $r=es$（$0\le s<n/e$）と書ける。逆に $0\le s<n/e$ の各 $s$ に対し $r=es$ は $\{0,\dots ,n-1\}$ の元で、$\gcd (es,n)=\gcd (es,e\cdot \frac{n}{e})=e\cdot \gcd (s,n/e)$ より、$es\in A_e⟺\gcd (s,n/e)=1$ である。$d=n/e$ とおくと、$|A_e|$ は $0\le s<d$ で $\gcd (s,d)=1$ となる $s$ の個数に等しい。$s=0$ を $s=d$ に置き換えても $\gcd (0,d)=\gcd (d,d)=d$ なので条件の成否は変わらず、この個数は $1\le s\le d$ で $\gcd (s,d)=1$ となる個数 $\phi (d)$ に等しい。よって $|A_e|=\phi (n/e)$。

ステップ 1 と合わせて
$$\sum _{r=0}^{n-1}|\mathrm{Fix}(r)|=\sum _{e\mid n}|A_e|k^e=\sum _{e\mid n}\phi (n/e)k^e=\sum _{d\mid n}\phi (d)k^{n/d}.$$
最後の等号では、$e\mapsto d=n/e$ が $n$ の正の約数全体の上の全単射であることを使った。

ステップ 3: 結論。 $(1)$ より ${\sum }_{d\mid n}\phi (d)k^{n/d}=nN$ であり、$N$ は軌道の個数なので正の整数である。したがって ${\sum }_{d\mid n}\phi (d)k^{n/d}$ は $n$ で割り切れる。

（確認: $n=4,k=2$ では $\phi (1)2^4+\phi (2)2^2+\phi (4)2^1=16+4+4=24=4\cdot 6$。）

以上より、すべての正の整数 $n,k$ に対して $n\mid {\sum }_{d\mid n}\phi (d)k^{n/d}$ である。$■$