公式解説 の「条件の言い換え」部分を群論の言葉を用いて説明します．群について知らない方は この記事 などを参考にしてください．

以下では，群論の知識のうち，本問の理解に必要な部分だけを紹介します．

対称群について

\(n\) を正の整数とします．\((1,2,\dots,n)\) の順列として考えられるものは \(n!\) 通りあります．これら \(n!\) 個全てからなる集合を \(S_n\) とします．この \(S_n\) に対して合成で演算を入れることで群になります．これを 対称群 や 置換群，その元を 置換 と言います．

本問題は順列を置換とみて対称群について扱う問題だと考えることで見通しが良くなります．

互換

\(\sigma \in S_n\) について，\(\sigma\) がある \(2\) 点を入れ替え，それ以外の元は変えないものであるとき，\(\sigma\) を 互換 と呼びます．例えば \(n=5\) として \(\sigma = (1,5,3,4,2)\) は互換です（\(2\) と \(5\) を入れ替え，それ以外は変化していません）．特に，\(\sigma\) が \(i\) 番目の要素と \(j\) 番目の要素を入れ替える操作を表すとき，\(\sigma = (i,j)\) のように書きます．上の例は \(\sigma = (2,5)\) です．

有名な事実として，全ての置換はいくつかの互換の積で表すことが出来ます．この個数を \(m\) とすれば，\(m\) の偶奇は互換による表現に依らず一定です．これは余談ですが，\(m\) が偶数となる置換を偶置換と呼び，\(n\) 次の偶置換全体からなる集合 \(A_n\) は \(S_n\) の正規部分群となります．\(n \geq 5\) のとき，\(A_n\) はそれより小さい群の合成として表せないことが知られており，これにより \(5\) 次以上の方程式にいわゆる「解の公式」が存在しないことが説明されます．

互換 \((i,i+1)\) を考えましょう（このような互換を隣接互換や基本互換と呼びます）．\((\tau_j)_{j=1}^{m}\) 達を隣接互換とします．\(\sigma \in S_n\) について，\(\sigma = \tau_1\tau_2\cdots\tau_m\) が成り立つような最小の \(m\) は \(\sigma\) に対応する順列の転倒数となります．

巡回置換

\(\sigma \in S_n\) に対応する順列 \(p\) を考えます．\(p\) による functional graph を考えると，これはいくつかのサイクルから成ります．このサイクルを一つ取ります．これが

\[a_1 \to a_2 \to \cdots a_m \to a_{m+1} = a_1 \to \cdots\]

となっているとき，これを \((a_1,a_2,\dots,a_m)\) と書きます．例えば \(p = (5,7,4,6,2,3,1)\) のとき，これは \((1,5,2,7)\) と \((3,4,6)\) の \(2\) つの巡回置換からなり，\(\sigma = (1,5,2,7)(3,4,6)\) となります．特に互換は巡回置換の特別な場合です．

共役類について

\(G\) を群とします（対称群とは限りません）．

\(x,y \in G\) に対して，ある \(g \in G\) が存在して \(y = gxg^{-1}\) となるとき，\(x\) と \(y\) は（互いに）共役 であると言います．\(G\) 上の二項関係 \(\sim\) を共役によって定めると，これは同値関係となります．

同値関係とは

一般に，集合 $X$ と $X$ 上の二項関係 $\sim_X$ が以下を全て満たすとき，「$\sim_X$ は $X$ 上の同値関係である」と言います．

• （反射律）：任意の $x \in X$ に対して $x \sim_X x$
• （対称律）：任意の $x,y \in X$ に対して $x \sim_X y \implies y \sim_X x$
• （推移律）：任意の $x,y,z \in X$ に対して $(x \sim_X y \land y \sim_X z) \implies x \sim_X z$

（例）

• 実数全体 $\mathbb{R}$ を考える．$a,b \in \mathbb{R}$ に対して $a \sim_{\mathbb{R}} b$ を「ある整数 $n$ が存在して $b=a+n$」 とするとこれは同値関係
• 実数を小数部分によって分類していると思うことが出来ます
• グラフ $G=(V,E)$ を考える．$u,v \in V$ に対して $u \sim_G v$ を「$u$ と $v$ は同じ連結成分に属する」とするとこれは同値関係

\(x^G\) を \(x^G \coloneqq \lbrace y \in G \mid x \sim y \rbrace\) によって定め，これを「\(x\) の共役類」と呼びます．

本問の解説

さて，公式解説の「条件の言い換え」の式を見てみましょう．

• \(P = XQ^{-1}\)
• \(QXQ^{-1}=Y\)

\(P,Q,X,Y\) は順列であったから対称群 \(S_N\) の元と思うことが出来ます．よって，\(2\) 番目の式から 「\(X\) と \(Y\) は共役である」ということが言えます．

次を示すことにしましょう．これは対称群における共役類の重要な特徴付けです．なお，この特徴付けの系として，\(S_n\) の共役類の個数（class number） は \(n\) の分割数に一致することが分かります．

• \(S_n\) において， \(\sigma, \tau \in \Sigma_n\) が共役 \(\iff\) \(( \sigma\) による \(n\) の分割 \() = ( \tau\) による \(n\) の分割 \()\)

「$\sigma$ による $n$ の分割」とは

先に述べたように $\sigma \in S_n$ について $\sigma$ は巡回置換の積で書くことができました．これを $$\sigma = (k^{(1)}_{1}, k^{(1)}_{2}, \dots, k^{(1)}_{s_1})(k^{(2)}_{1}, k^{(2)}_{2}, \dots, k^{(2)}_{s_2}) \cdots (k^{(r)}_{1}, k^{(r)}_{2}, \dots, k^{(r)}_{s_r})$$ とおきます．ここで $$s_1 + s_2 + \cdots + s_r = n, s_1 \leq s_2 \leq \cdots \leq s_r$$ としても良く，このときの $(s_1,s_2,\dots,s_r)$ を $\sigma$ による $n$ の分割と言います．

この事実に対する直感的な理解は公式解説の図を見るのが良いでしょう．

（証明）

\((\Rightarrow)\) \(g \in S_n\) とし

• \(\sigma = (k^{(1)}_{1}, k^{(1)}_{2}, \dots, k^{(1)}_{s_1}) \cdots (k^{(r)}_{1}, k^{(r)}_{2}, \dots, k^{(r)}_{s_r})\)
• \(\tau = g \sigma g^{-1}\)

とする．このとき

\[\tau = (g(k^{(1)}_{1}), g(k^{(1)}_{2}), \dots, g(k^{(1)}_{s_1})) \cdots (g(k^{(r)}_{1}), g(k^{(r)}_{2}), \dots, g(k^{(r)}_{s_r}))\]

となるので \(( \sigma\) による \(n\) の分割 \() = ( \tau\) による \(n\) の分割 \()\) となる．

\((\Leftarrow)\) \(\sigma\) と \(\tau\) による \(n\) の分割が等しいので

• \(\sigma = (k^{(1)}_{1}, k^{(1)}_{2}, \dots, k^{(1)}_{s_1}) \cdots (k^{(r)}_{1}, k^{(r)}_{2}, \dots, k^{(r)}_{s_r})\)
• \(\tau = (l^{(1)}_{1}, l^{(1)}_{2}, \dots, l^{(1)}_{s_1}) \cdots (l^{(r)}_{1}, l^{(r)}_{2}, \dots, l^{(r)}_{s_r})\)

とおく．このとき各 \(i,j\) に対して

\(g(k^{(i)}_j) = l^{(i)}_j\) となるように \(g \in S_n\) を定めると \(\tau = g \sigma g^{-1}\) となるので \(\sigma\) と \(\tau\) は共役となる．

（証明終）

なお，証明の後半の \(g\) の構成は公式解説の最後にある「復元処理」となっています．

これによって，公式解説の言い換えを得ることが出来ました．