群論の問題

作用する群. 成分の位置 $(i,j)$（$1\le i,j\le 3$）の集合を $C$ とする。$(\sigma ,\tau )\in S_3\times S_3$ を $(i,j)\mapsto (\sigma (i),\tau (j))$、転置を $T:(i,j)\mapsto (j,i)$ とすると、これらは $C$ の置換群 $G$ を生成する。$T(\sigma ,\tau )T=(\tau ,\sigma )$ なので $G=(S_3\times S_3)⋊⟨T⟩$, $|G|=72$ であり、$G$ は $C$ への作用を通して $X$（$C\to \{0,1\}$ の写像全体）に作用する。求めるものはこの作用の軌道の数である。

$g\in G$ が $C$ 上で $c(g)$ 個の巡回置換に分解するとき、$g$ で固定される行列は各巡回上で成分が一定のものなので $|X^g|=2^{c(g)}$。バーンサイドの補題より
$$\#(X/G)=\frac{1}{72}\sum _{g\in G}{2}^{c(g)}.$$

(1) $g=(\sigma ,\tau )$ の場合. 長さ $a$ の $\sigma$ の巡回と長さ $b$ の $\tau$ の巡回の直積 $ab$ 個の位置は $\gcd (a,b)$ 個の巡回に分かれる。$S_3$ の元の巡回型は、恒等置換 $(1,1,1)$ が $1$ 個、互換 $(2,1)$ が $3$ 個、$3$-巡回置換 $(3)$ が $2$ 個。

合計は $512+6\cdot 64+4\cdot 8+9\cdot 32+12\cdot 4+4\cdot 8=512+384+32+288+48+32=1296$。

(2) $g=(\sigma ,\tau )T$ の場合. $g(i,j)=(\sigma (j),\tau (i))$ である。位置の付け替え $\Phi (i,j)=(i,\sigma (j))$ により
$$\Phi g{\Phi }^{-1}(i,j)=\Phi (j,\tau (i))=(j,\rho (i)),\rho =\sigma \tau$$
となるので、$c(g)$ は $h_{\rho }:(i,j)\mapsto (j,\rho (i))$ の巡回の個数に等しく、$\rho$ の共役類だけで決まる。各 $\rho$ に対し $\sigma \tau =\rho$ となる組は $6$ 個（$\tau$ を任意に選ぶと $\sigma$ が決まる）なので、$\rho$ が恒等置換・互換・$3$-巡回置換である $g$ はそれぞれ $6$, $18$, $12$ 個。
- $\rho =e$: $h_{\rho }$ は転置。対角の $3$ 個が固定され、残り $6$ 個が $3$ つの互換をなすので $c=6$。
- $\rho =(12)$: $(1,1)\to (1,2)\to (2,2)\to (2,1)\to (1,1)$, $(1,3)\to (3,2)\to (2,3)\to (3,1)\to (1,3)$, $(3,3)$ は固定。$c=3$。
- $\rho =(123)$: $(1,1)\to (1,2)\to (2,2)\to (2,3)\to (3,3)\to (3,1)\to (1,1)$ と $(1,3)\to (3,2)\to (2,1)\to (1,3)$。$c=2$。

合計は $6\cdot 2^6+18\cdot 2^3+12\cdot 2^2=384+144+48=576$。

結論.
$$\#(X/G)=\frac{1296+576}{72}=\frac{1872}{72}=26.$$

（参考: 転置を使わない $S_3\times S_3$ のみの作用では $1296/36=36$ 類になる。）

操作全体が生成する群 $\Gamma =(S_3\times S_3)⋊C_2$（位数 72）の $X$ への作用の軌道数をバーンサイドの補題で数える。作用は $A\mapsto PAQ$（行・列の並べ替え）と転置であり、$\Gamma$ の元は (a) $A_{ij}\mapsto A_{\sigma (i),\tau (j)}$ 型（36 個）と (b) 転置を伴う $A_{ij}^{\prime }=A_{\alpha (j),\beta (i)}$ 型（36 個）に分かれる。

(a) 型: $S_3\times S_3$ のみによる軌道数は、$3\times 3$ の 0-1 行列を行列・列の並べ替えで同一視した個数として既知の 36（行・列の置換 $(\sigma ,\tau )$ について不動点数 $2^{c(\sigma ,\tau )}$ の総和 $=36\cdot 36=1296$）。

(b) 型: 不動点は $A_{ij}=A_{\alpha (j),\beta (i)}$ を満たすもの。セル $(i,j)\mapsto (\alpha (j),\beta (i))=:\phi (i,j)$ の巡回置換の個数を $c$ とすると不動点数は $2^c$。共役で $\alpha =\mathrm{id}$, $\beta =\pi$ に取れ、$\pi =\beta \alpha$ の共役類だけで決まり、各 $\pi$ に対応する $(\alpha ,\beta )$ は 6 組ずつ。
- $\pi =e$: $\phi (i,j)=(j,i)$、巡回 6 個（固定 3、互換 3）→ $2^6=64$
- $\pi$ が互換（3 個）: 例 $\pi =(12)$。$(1,1)\to (1,2)\to (2,2)\to (2,1)$、$(1,3)\to (3,2)\to (2,3)\to (3,1)$ の 4-巡回 2 個と固定点 $(3,3)$ → 巡回 3 個 → $2^3=8$
- $\pi$ が 3-巡回（2 個）: $i=\pi j$ を満たす 3 セルが 3-巡回 1 個、残り 6 セルが 6-巡回 1 個 → 巡回 2 個 → $2^2=4$

(b) 型の不動点数の総和は $6(64+3\cdot 8+2\cdot 4)=6\cdot 96=576$。

軌道数 $=(1296+576)/72=1872/72=26$。

検算: $2\times 2$ の場合は同様に、行列・列並べ替えで 7 類、転置も許すと 6 類になることが直接数えて確認でき、方法は整合する。$3\times 3$ では (36 + 転置で不変な類の個数 $x$)/2 $=26$ より $x=16$ となり $0\le x\le 36$ で矛盾しない。