💱

競プロ er のための群論 (swap と順列と対称群)

2023/02/03に公開

math

tech

この記事はブログから移植したものです。

この記事では競技プログラミングと群論に関する解説をします。競技プログラミングの問題を群論という立場から見ることで、新たな視点を得ることができるようになると思います。また、群論の入門にもなればいいなと思っています。

swap と順列

競技プログラミングの問題に、swap と順列は多く登場します。swap とは、2 つの要素を入れ替える操作のことです。例えば、次のような問題があります。

第二回全国統一プログラミング王決定戦予選 C - Swaps
$N$ 要素からなる 2 つの整数列 $A_1,\ldots,A_N$ および $B_1,\ldots,B_N$ が与えられます。以下の操作を $N-2$ 回まで (0 回でもよい) 行うことで、1 以上 $N$ 以下のすべての整数 $i$ に対して $A_i\le B_i$ となるようにできるか判定してください。

1 以上 $N$ 以下の相異なる整数 $x,y$ を選び、 $A_x$ の値と $A_y$ の値を入れ替える。

また、(長さ $N$ の) 順列とは、 $N$ 個のものの並べ替えのことです。例えば、次のような問題があります。

AtCoder Beginner Contest 175 D - Moving Piece
高橋君は $1,2,\ldots,N$ の番号のついた $N$ マスからなるマス目の上で、コマを使ってゲームを行おうとしています。マス $i$ には整数 $C_i$ が書かれています。また、 $1,2,\ldots,N$ の順列 $P_1,P_2,\ldots,P_N$ が与えられています。
これから高橋君は好きなマスを 1 つ選んでコマを 1 つ置き、1 回以上 $K$ 回以下の好きな回数だけ、次のような方法でコマを移動させます。

1 回の移動では、現在コマがマス $i \ (1\le i\le N)$ にあるなら、コマをマス $P_i$ に移動させる。このとき、スコアに $C_{P_i}$ が加算される。

高橋君のために、ゲーム終了時のスコアとしてあり得る値の最大値を求めてください。(ゲーム開始時のスコアは 0 です。)

この記事の目標は、swap や順列を群論 (特に対称群) の立場から捉えることです。

対称群

swap も順列も、 $1,2,\ldots,N$ を並べ替える操作を表しています。数学的に表現すると、 $X$ を $N$ 個の元からなる集合 $\{1,2,\ldots,N\}$ とするとき、 $X$ から $X$ への写像とみることができます。順列も swap も $1,2,\ldots,N$ の並べ替えであることから、この写像は一対一に対応していることがわかります。よって、順列とは $X$ から $X$ への全単射とみることができます。また、swap は順列の特別なものとみることができます。

$X=\{1,2,\ldots,N\}$ に対して、 $X$ から $X$ への全単射全体からなる集合を $S_N$ とおきます。順列の個数を考えることで、 $S_N$ の元の個数が $N!$ であることがわかります。 $S_N$ の元 $f$ に対して、 $f$ を次のような形で表示してみましょう。

f=\begin{pmatrix} 1 & 2 & \cdots & N \\ f(1) & f(2) & \cdots & f(N) \end{pmatrix}

これは上に書かれている数を下に書かれている数に移すということを表しています。例えば、 $\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{pmatrix}$ は 1 を 2 に、2 を 4 に、3 を 3 に、4 を 1 に移す写像を表しています。これは全単射なので $S_4$ の元です。

すべての数を動かさない写像、すなわち

\begin{pmatrix} 1 & 2 & \cdots & N \\ 1 & 2 & \cdots & N \end{pmatrix}

も $S_N$ の元です。これを $S_N$ の単位元と呼び、 $\text{id}$ と表すことにします。

$S_N$ の元は $X$ から $X$ への写像なので、合成を考えることができます。例えば $\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{pmatrix}$ を作用させてから、 $\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{pmatrix}$ を作用させると、1 は 2 に移ったあと 3 に移ります。2 は 4 に移った後 1 に移り、3 は 3 に移った後 2 に移り、4 は 1 に移った後 4 に移ります。これを

\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{pmatrix}\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{pmatrix}=\begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 2 & 4 \end{pmatrix}

と表します。(一般的な写像の合成と順序が逆であることに注意してください。写像の合成と合わせる場合もありますが、この記事ではこちらを使います。)

2 つの全単射を合成しても全単射なので、 $S_N$ の 2 つの元を合成したものも $S_N$ の元です。さらに結合法則 $f(gh)=(fg)h$ をみたしています。

また、 $f$ を $S_N$ の元とするとき、 $f$ は全単射なので逆写像 $f^{-1}$ をもち、 $f^{-1}$ も $S_N$ の元となります。

まとめると、 $S_N$ は次のような性質を持ちます。

$f,g\in S_N$ ならば $fg\in S_N$
$f,g,h\in S_N$ ならば $f(gh)=(fg)h$
$\text{id}\in S_N$
$f\in S_N$ ならば $f^{-1}\in S_N$

$S_N$ には群と呼ばれる代数的構造が入るということになります。このことから、 $S_N$ を $N$ 次対称群と呼びます。

$S_N$ の元を順列または置換と呼びます。 $f,g\in S_N$ に対して、合成 $fg$ を $f$ と $g$ の積と呼ぶことにします。以後、 $f\in S_N, x\in X$ に対し $f(x)$ の代わりに $x^f$ と書くことにします (このように書くと $x^{fg}=(x^f)^g$ をみたします)。

問題を 1 つ紹介します。

AtCoder Beginner Contest 142 C - Go to School
$N$ 人の生徒に 1 から $N$ までの番号が 1 つずつ割り振られています。
全ての生徒たちが相異なるタイミングで登校しました。
番号 $i$ の生徒が登校したタイミングで、教室には $A_i$ 人の生徒がいました。
生徒たちの登校した順番を求めてください。

$A$ は順列なので、 $S_N$ の元とみなすことができます。この問題の答えは $A^{-1}$ です。

対称群の生成元

$i$ と $j$ を入れ替える swap 操作のことを互換といい、 $(i,j)$ と表します。互換も対称群の元です。置換を互換の積で表すことを考えます。例えば

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 6 & 4 & 1 & 5 & 2 \end{pmatrix}=(1,4)(3,4)(2,6)

のように、この置換は 3 つの互換の積で表すことができました。実は、 $S_N$ の元はすべて、いくつかの互換の積で表すことができます。まず 1 を互換で所定の位置に動かし、2 を動かし、…と順番にやっていくことで互換の積で表せることがわかります。言い換えると、 $\frac{N(N-1)}{2}$ 個の互換 $(i,j)$ は $S_N$ を生成するということになります。

では次のような問題を考えてみましょう。

$K$ 個の互換 $(a_i,b_i)\in S_N$ が与えられます。これらの互換が $S_N$ を生成するか、すなわち $S_N$ の任意の元はこれらの互換の積として表せるか判定してください。

$1,2,\ldots,N$ を頂点とするグラフを考え、 $a_i,b_i$ を辺で結びます。このグラフが連結でなければ、異なる連結成分に属する 2 数を入れ替えられないので、 $S_N$ を生成しません。

逆にグラフが連結ならば $S_N$ を生成することを示します。適当に全域木をとり、その上に制限して考えます。すると以下の操作を繰り返すことで $\pi\in S_N$ を互換の積で表すことができます。

$x^{\pi}$ がグラフの葉であるような $x$ を 1 つ選ぶ。
$x$ が $x^{\pi}$ に移るように互換をかける。
グラフから頂点 $x^{\pi}$ を削除する。

よって、グラフが連結かどうかを判定すればよいです。

このことから、 $S_N$ は隣接互換 $(1,2),(2,3),\ldots,(N-1,N)$ で生成されることがわかります。これはあみだくじですべての順列を作れるということを表しています。

では次にこのような問題を考えてみましょう。

$N$ 人が一列に並んでいます。 $K$ 種類の操作があり、 $i$ 番目の操作では、前から $a_i$ 番目の人と前から $b_i$ 番目の人を入れ替えることができます。これらの操作を好きな順番で好きな回数行うとき、操作後の人の並び方としてあり得る状態の数は何通りありますか。

数学的には、 $K$ 個の互換 $(a_i,b_i)$ で生成された $S_N$ の部分群の位数を求めよという問題になります。これも上と同様にグラフを作ると、各連結成分上で自由に動かせることになります。連結成分の大きさを $n_1,n_2,\ldots,n_m$ とすると、答えは $n_1!\times n_2!\times\cdots\times n_m!$ です。UnionFind を用いて連結成分の大きさを求めることができます。

では実際の問題を解いてみましょう。

AtCoder Beginner Contest 097 D - Equals
1 から $N$ までの整数を並び替えた順列 $p_1,p_2,\ldots,p_N$ があります。また、1 以上 $N$ 以下の整数のペアが $M$ 個与えられます。これらは $(x_1,y_1),(x_2,y_2),\ldots,(x_M,y_M)$ で表されます。シカの AtCoDeer くんは順列 $p$ に次の操作を好きなだけ行って、 $p_i=i$ となる $i \ (1\le i\le N)$ の数を最大にしようと考えています。

$1\le j\le M$ なる $j$ を選び、 $p_{x_j}$ と $p_{y_j}$ をスワップする。

操作後の $p_i=i$ となる $i$ の数として考えうる最大値を求めてください。

$1,2,\ldots,N$ を頂点とし、 $x_i,y_i$ を辺で結んでできるグラフを考えると、上で見た通り、連結成分上で好きなように動かすことができます。 $p_i$ と $i$ が同じ連結成分上にあれば、 $p_i=i$ となるようにすることができます。

AtCoder Grand Contest 003 C - BBuBBBlesort!
高橋君は、誕生日に長さ $N$ の数列をもらいました。 $i \ (1\le i\le N)$ 番目の要素は整数 $A_i$ です。どの 2 つの要素も、互いに異なります。高橋君はこの数列を単調増加になるように並べ替えたいです。高橋君は超能力者なので、以下の 2 つの操作が任意のタイミングで出来ます。

操作 1: 数列の連続する 2 つの要素を選び、その 2 つの順番を反転する。

操作 2: 数列の連続する 3 つの要素を選び、その 3 つの順番を反転する。

高橋君は操作 2 は好きですが、操作 1 は嫌いです。この 2 種類の操作を使って数列を単調増加になるように並び替えるときの、操作 1 の最小回数を求めてください。

操作 1 は互換 $(i,i+1)$ 、操作 2 は互換 $(i,i+2)$ です。操作 2 だけを行うとき、同様にグラフを考えると、連結成分は ( $N\ge 2$ のとき) 2 つで、それぞれ偶数・奇数に対応します。ゆえに添字が偶数であるもの同士は自由に並べ替えることができ、添字が奇数であるもの同士も自由に並べ替えることができます。添字の偶数・奇数を変える必要があるものは操作 1 を使います。よって、添字の偶数・奇数が入れ替わる個数を数えればよいです。

AtCoder Beginner Contest 233 F - Swap and Sort
$(1,2,\ldots,N)$ を並び替えた長さ $N$ の順列 $P=(P_1,P_2,\ldots,P_N)$ があります。
あなたが可能な操作は $M$ 種類あり、操作 $i$ は「 $P$ の $a_i$ 番目の要素と $P$ の $b_i$ 番目の要素を入れ替える」というものです。
操作を好きな順序で、合計 $5\times10^5$ 回以下行うことによって、 $P$ を昇順に並び替えることはできますか？
できるならば、操作手順を 1 つ教えてください。できないならばその旨を伝えてください。

この問題も連結成分上で好きなように動かせることを用います。構築も上で述べたように、全域木をとって頂点を削除していくことで解けます。

転倒数と交代群

$S_N$ の元が互換の積で表せることをみましたが、互換の個数は一意ではありません。例えば

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 3 & 6 & 4 & 1 & 5 & 2 \end{pmatrix}=(1,4)(3,4)(2,6)=(1,2)(1,6)(2,3)(2,4)(1,2)

のように、3 個の互換の積で表すことも、5 個の互換の積で表すこともできます。このように個数は一意ではありませんが、実は個数の偶奇は一意に定まります。上の例では、常に互換の個数は奇数になります。すなわち偶数個の互換の積で表すことはできないということです。

これを証明してみます。突然ですが、 $f(x_1,\ldots,x_N)=\displaystyle\prod_{i<j}(x_i-x_j)$ という $N$ 変数多項式を考えます。 $\pi\in S_N$ に対して、 $f^{\pi}(x_1,\ldots,x_N)=f(x_{1^{\pi}},\ldots,x_{N^{\pi}})$ とおきます。計算すると、 $\pi$ が互換のときは $f^{\pi}(x_1,\ldots,x_N)=-f(x_1,\ldots,x_N)$ が成り立つことがわかります。ここで、 $\pi$ が $k$ 個の互換の積として表せるとすると、 $f^{\pi}(x_1,\ldots,x_N)=(-1)^kf(x_1,\ldots,x_N)$ となります。一方 $\pi$ が $l$ 個の互換の積としても表せたとすると、 $f^{\pi}(x_1,\ldots,x_N)=(-1)^lf(x_1,\ldots,x_N)$ となります。これより $(-1)^k=(-1)^l$ となり、 $k$ と $l$ の偶奇が等しいことがわかります。従って、置換を互換の積として表すときの互換の個数の偶奇は常に一定であることが示されました。

よって次のような定義ができます。

偶数個の互換の積として表せる置換を偶置換といい、
奇数個の互換の積として表せる置換を奇置換という。

偶置換と偶置換の積は偶置換になります。よって $S_N$ の元のうち偶置換であるもの全体を考えると、これは $S_N$ の部分群となることがわかります。偶置換全体からなる $S_N$ の部分群を $A_N$ と表し、 $N$ 次交代群と呼びます。 $A_N$ の位数 (偶置換の個数) は $\frac12N!$ です。

$i=1,2,\ldots,N$ に対し、 $i$ を $P_i$ に移す置換は偶置換か奇置換か決定してください。

ここで転倒数という概念を導入します。置換 $P$ の転倒数とは、 $i<j$ かつ $P_i>P_j$ となるような組 $(i,j)$ の個数です。転倒数はバブルソートにおける swap の回数と等しくなります。よって、 $P$ は転倒数個の互換の積で表されます。ゆえに転倒数を求めれば、その偶奇をみることで偶置換かどうかがわかります。転倒数は BIT を用いることで計算できます。詳しくは以下の記事などを参照してください。

偶置換に関する問題を解いてみましょう。

AtCoder Beginner Contest 244 D - Swap Hats
1,2,3 の番号がついた 3 人の高橋くんがおり、赤・緑・青の色がついた 3 種類の帽子がそれぞれ 1 つずつあります。
それぞれの高橋くんは帽子を 1 つかぶっており、高橋くん $i$ がはじめにかぶっている帽子の色は文字 $S_i$ で表されます。
これから、以下の操作をちょうど $10^{18}$ 回行います。

3 人の高橋くんのうち 2 人を選ぶ。2 人はお互いのかぶっている帽子を交換する。

$10^{18}$ 回の操作の後、高橋くん $i$ が文字 $T_i$ に対応する色の帽子をかぶっているようにすることはできますか？

入れ替える操作をちょうど $10^{18}$ 回行うことから、偶置換でなければならないことがわかります。逆に $10^{18}$ は十分大きいのですべての偶置換は条件を満たします。

Codeforces Round #598 (Div. 3) F. Equalizing Two Strings
英小文字からなる 2 つの長さ $n$ の文字列 $s,t$ が与えられます。以下の操作を行うことができます。

1 以上 $n$ 以下の整数 $len$ を 1 つ選ぶ。

$s$ の長さ $len$ の連続部分文字列を選び、反転させる。

同時に、 $t$ の長さ $len$ の連続部分文字列を選び、反転させる。

何回か操作を行うことで、 $s,t$ を等しくできるでしょうか。

$t$ の部分文字列を反転させる代わりに $s$ の部分文字列を反転させることにしてもよいです。よって $s$ には長さ $len$ の反転を 2 回行うことになり、これは偶置換です。逆にすべての偶置換をこれらの操作を組み合わせることで実現可能です (略証: $(i,i+1,i+2)=(i+1,i+2)(i,i+1)$ は長さ 2 の反転 2 回で実現可能であり、交代群 $A_N$ はこれらの元で生成されるため)。これを踏まえて問題を解きましょう。

まず出現回数が異なる文字がある場合は不可能です。以下出現回数が等しいとします。等しい文字があるときは可能です。なぜなら、 $s$ を $t$ にするための操作が奇置換のときは、等しい文字を入れ替えるダミーの互換を加えることで偶置換にできるからです。等しい文字がないとします。 $s,t$ の転倒数を計算します (この場合長さが 26 以下なので BIT を用いなくても計算できます)。 $s,t$ を等しくできるための必要十分条件は、 $s,t$ の転倒数の偶奇が一致していることです。

巡回置換

$1,2,\ldots,N$ の順列 $P$ に対して、 $i, P_i, P_{P_i}, P_{P_{P_i}}, \ldots$ という列を考えるとどのようになるでしょうか。

$1,2,\ldots,N$ を頂点とするグラフにおいて、 $i$ から $P_i$ へ有向辺を張ります。すると上の問題は、ある点から出発して辺上を動くとどのように動くかという問題になります。

頂点数は有限個なので、移動を続けると途中で既に通った頂点に出会います。このとき経路は6の字型にはなりません。

なぜなら $P$ は順列 (特に単射) だからです。ゆえに、経路はサイクルになります。通らなかった頂点についても同様に考えることで、サイクルになることがわかります。2 つのサイクルは交わりません。

よって、このグラフはサイクルがいくつか集まったものになります。このことを群論的に表現してみましょう。

$(a_1,a_2,\ldots,a_m)$ を、 $a_1$ を $a_2$ に移し、 $a_2$ を $a_3$ に移し、…、 $a_m$ を $a_1$ に移す置換とします。このような置換を巡回置換といいます。互換 $(i,j)$ は巡回置換の特別なものです。

上で述べたことは、任意の置換が共通文字を含まないいくつかの巡回置換の積として表せるということです。例えば

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 4 & 2 & 5 & 7 & 3 & 8 & 1 & 6 \end{pmatrix} = (1,4,7)(3,5)(6,8)(2)

のようになります。

Codeforces Round #595 (Div. 3) B2. Books Exchange (hard version)
$n$ 人の子供たちがおり、それぞれ本を持っています。毎日の終わりに、 $i$ 番目の子供は持っている本を $p_i$ 番目の子供に渡します。ここで $p$ は $1,2,\ldots,n$ の順列です。子供ごとに、自分の本が自分のところに戻ってくるまでに何日かかるか求めてください。

$i$ 番目の子供が持っていた本は $p_i$ 番目の子供に移り、さらにそれは $p_{p_i}$ 番目の子供に移ります。よって冒頭で述べたシチュエーションと一致しています。

$p$ を巡回置換の積として表すとき、 $i$ 番目の子供に対する答えは、 $i$ を含む巡回置換の長さです。

AtCoder Beginner Contest 175 D - Moving Piece
高橋君は $1,2,\ldots,N$ の番号のついた $N$ マスからなるマス目の上で、コマを使ってゲームを行おうとしています。マス $i$ には整数 $C_i$ が書かれています。また、 $1,2,\ldots,N$ の順列 $P_1,P_2,\ldots,P_N$ が与えられています。
これから高橋君は好きなマスを 1 つ選んでコマを 1 つ置き、1 回以上 $K$ 回以下の好きな回数だけ、次のような方法でコマを移動させます。

1 回の移動では、現在コマがマス $i \ (1\le i\le N)$ にあるなら、コマをマス $P_i$ に移動させる。このとき、スコアに $C_{P_i}$ が加算される。

高橋君のために、ゲーム終了時のスコアとしてあり得る値の最大値を求めてください。(ゲーム開始時のスコアは 0 です。)

これも冒頭のシチュエーションと一致します。よって巡回置換の積に分解して、各巡回置換上で考えればよいことになります。

最初の移動で到達するマスを固定します。このマスを含むサイクルの長さが $L$ だとします。

一周の総和が正のときは回れるだけ回って、残った $((K-1) \bmod{L})+1$ 個について和の最大値を求めます。
一周の総和が 0 以下で $K\ge L$ のときは、1 個以上 $L$ 個以下の和の最大値を求めます。
一周の総和が 0 以下で $K\le L$ のときは、1 個以上 $K$ 個以下の和の最大値を求めます。

これで計算量 $O(N^2)$ で解くことができました。なお、さらに改善するとより良い計算量で解けるようです。

AtCoder Beginner Contest 013 D - 阿弥陀
$N$ 本の縦線と $M$ 本の横線からなるあみだくじがあり、上から $i$ 番目の横線は左から $A_i$ 番目の縦線と $A_i+1$ 番目の縦線を結んでいます。このあみだくじを縦に $D$ 個つなげます。各整数 $k=1,2,\ldots,N$ に対し、左から $k$ 番目の縦線から出発したとき、最終的に左から何番目の縦線に到着するか求めてください。

与えられるあみだくじは対称群 $S_N$ の元とみることができます。よって共通文字を含まない巡回置換の積 $(c_{11},\ldots,c_{1i_1})(c_{21},\ldots,c_{2i_2})\cdots (c_{k1},\ldots,c_{ki_k})$ として表すことができます。あみだくじを $D$ 個連結したものは、これを $D$ 乗した $(c_{11},\ldots,c_{1i_1})^D(c_{21},\ldots,c_{2i_2})^D\cdots (c_{k1},\ldots,c_{ki_k})^D$ となります (一般に置換の積は非可換ですが、これらの巡回置換は共通文字を含まないので積の順番を入れ替えることができます)。

第二回全国統一プログラミング王決定戦予選 C - Swaps
$N$ 要素からなる 2つの整数列 $A_1,\ldots,A_N$ および $B_1,\ldots,B_N$ が与えられます。以下の操作を $N-2$ 回まで (0 回でもよい) 行うことで、1 以上 $N$ 以下のすべての整数 $i$ に対して $A_i\le B_i$ となるようにできるか判定してください。

1 以上 $N$ 以下の相異なる整数 $x,y$ を選び、 $A_x$ の値と $A_y$ の値を入れ替える。

swap を $N-2$ 回まで、という条件が気になります。これについて考えてみましょう。

長さ $m$ の巡回置換 $(i_1,i_2,\ldots,i_m)$ は $m-1$ 個の互換の積 $(i_1,i_2)(i_1,i_3)\cdots (i_1,i_m)$ として表すことができます。よって $S_N$ の元が共通文字を含まない巡回置換 $k$ 個の積として表せ、巡回置換の長さがそれぞれ $l_1,l_2,\ldots,l_k$ であったとすると、これは $(l_1-1)+(l_2-1)+\ldots+(l_k-1)=N-k$ 個の互換の積として表せます。よって、 $N-2$ 回までの swap で長さ $N$ の巡回置換以外をすべて表現できることがわかります。

まず適切に並べ替えておくことで、 $B_1\le B_2\le\cdots\le B_N$ であるとしてよいです。 $A_{p_1}\le A_{p_2}\le\cdots\le A_{p_N}$ となるような置換 $p$ を 1 つとります。このとき $A_{p_i}>B_i$ となるような $i$ が存在すると不可能です。以下 $A_{p_i}\le B_i$ とします。 $p$ が長さ $N$ の巡回置換でなければ、 $p$ を $N-2$ 個以下の互換の積で表せるので、条件を満たします。 $p$ が長さ $N$ の巡回置換のとき、 $p$ は $N-1$ 個の互換の積で表されます。よって、 $N-2$ 回までの swap により $A$ は「ソートされた状態の 1 つ手前」、すなわちソートされた状態に swap を 1 回施したものにできます。少し考えるとこの swap は隣接互換でよいことがわかります。ゆえに $N-1$ 個の隣接互換をすべて考え、条件を満たすようにできるか判定します。 $A_{p_{i+1}}\le B_i$ を判定すればよいです。

演習問題

参考文献

齋藤正彦, 『線型代数入門』, 東京大学出版会, 1966. (線型代数の有名な教科書です。対称群の理論は行列式を扱うときにも登場します)
雪江明彦, 『代数学1 群論入門』, 日本評論社, 2010. (対称群に限らない一般の群論について扱う教科書です。かなり丁寧です)
桂利行, 『代数学I 群と環』, 東京大学出版会, 2004. (群論の教科書です。薄いです)