高校数学の順列・組み合わせについて聞かれると「それよく知らないんだよ」と答えていたのですが、「知っていたほうがいいかもな」と思って調べてみました。で、“組み合わせの数”の公式を正確に記述するのはけっこう難しいな、と感じました。
“組み合わせの数”の公式は、群作用の軌道空間の基数（要素の個数）を勘定しているのだ、と解釈してみます。順列・組み合わせより、むしろ群作用の軌道空間のほうがこの記事の主題です。最後の節で、“組み合わせの数”の公式を記述します。$`\newcommand{\u}[1]{\underline{#1}}
\newcommand{\hyp}{\text{－} }
\newcommand{\mrm}[1]{\mathrm{#1} }
\newcommand{\In}{\text{ in } }
\newcommand{\Imp}{\Rightarrow }
\newcommand{\Iff}{\Leftrightarrow }
\newcommand{\card}{\mrm{card} }
`$
内容：
群の例
群 $`G`$ を次のように書きます。
$`\quad G = (\u{G}, *, I, \hyp^{-1})`$
ここで、
- $`\u{G}`$ は、台集合： $`\u{G} \in |{\bf Set}|`$
- $`*`$ は、二項演算： $`(\hyp * \hyp) : \u{G}\times \u{G} \to \u{G} \In {\bf Set}`$
- $`I`$ は、単位元： $`I\in \u{G}`$
- $`\hyp^{-1}`$ は、逆元を対応させる写像： $`(\hyp^{-1}) : \u{G} \to \u{G} \In {\bf Set}`$
これらは、よく知られた法則〈公理〉を満たします。
通常は、群とその台集合を同じ名前で表す“記号の乱用”が使われます。
$`\quad G = (G, *, I, \hyp^{-1})`$
群の具体例として、実数の足し算の群があります。
$`\quad \mrm{A} = ({\bf R}, +, 0, - )`$
最後のマイナス記号は引き算ではなくて、符号を反転した数を対応させる写像です。記号の乱用により、群 $`\mrm{A}`$ とその台集合 $`{\bf R}`$ を同じ名前で表します。
$`\quad {\bf R} = ({\bf R}, +, 0, - )`$
この記事内では、単に $`{\bf R}`$ と書いたら、それは実数の足し算の群です。
もうひとつ群の例 $`\mrm{H}`$ を挙げます。
- 台集合 $`\u{\mrm{H}} := \{s, t, u, e\}`$
- 二項演算は下に演算表
- 単位元は $`e`$
- 逆元も下に
群 $`\mrm{H}`$ の演算表は以下のようです。単位元は省略してます。
| * | s | t | u |
|---|---|---|---|
| s | e | u | t |
| t | u | e | s |
| u | t | s | e |
結合法則 $`(x*y)*z = x*(y*z)`$ は、シラミ潰しチェックでも確認できます。演算表から逆元は自分だ（$`x^{-1} = x`$）と分かります。また、群 $`\mrm{H}`$ が可換群であることもひと目で分かります。
4元の可換群 $`\mrm{H}`$ を記号の乱用を使って書けば：
$`\quad \mrm{H} = (\mrm{H}, *, e, \hyp^{-1})\\
\quad \mrm{H} = \{s, t, u, e\}
`$
群作用の例
群作用の定義は、過去記事「群の作用がナントカ -- おぼえられない」に書いています。が、繰り返し記述します。
$`G = (G, *, I, \hyp^{-1})`$ を群、$`X`$ を集合として、$`\alpha`$ が（$`G`$ の $`X`$ への）左群作用〈left group action〉であるとは次のことです。（$`\u{G}`$ も $`G`$ と書きます。）
- $`\alpha : G\times X \to X \In {\bf Set}`$
- $`\forall g, h\in G.\forall x\in X.\,\alpha(g, \alpha(h, x)) = \alpha(g*h, x)`$
- $`\forall x\in X.\,\alpha(I, x) = x`$
右群作用〈right group action〉も同様に定義できます。
$`\alpha`$ が、$`G`$ の $`X`$ への（左または右の）群作用であることは、次のような言い方もします。全部同じことです。
- $`X`$ は、$`G`$-集合である。
- $`X`$ は、$`G`$-加群である。
- $`\alpha`$ は、群 $`G`$ の表現〈representation〉である。（すぐ下に説明）
$`\alpha : G \times X \to X`$ をカリー化すると次の写像が得られます。
$`\quad \alpha^\cap : G \to \mrm{Map}(X, X) \In {\bf Set}`$
ここで、$`\mrm{Map}(X, X)`$ は集合圏の自己射〈endomorphism〉の集合ですが、結合〈合成〉でモノイドになります。モノイドの可逆元（ここでは双射）だけ考えると群 $`\mrm{Aut}(X)`$ になります。カリー化した写像 $`\alpha^\cap`$ は群の準同型写像だと分かるので、それをあらためて $`\rho`$ と書くと：
$`\quad \rho : G \to \mrm{Aut}(X) \In {\bf Grp}`$
「群の表現」というときは、$`\rho`$ のことを指していることが多いでしょう。とはいえ、$`\rho`$ と $`\alpha`$ は事実上同じです。
群作用の例を挙げます。まず、群 $`{\bf R}`$ の集合 $`{\bf R}^2`$ への作用、“斜め45度”方向への並進〈平行移動 | parallel translation〉 $`\mrm{Tra}`$ です。
$`\mrm{Tra} : {\bf R} \times {\bf R}^2 \to {\bf R}^2\In {\bf Set}\\
\text{For }t\in {\bf R},\, (x, y)\in {\bf R}^2\\
\quad \mrm{Tra}(t, (x, y)) := (x + t, y + t)
`$
次に同じく、群 $`{\bf R}`$ の集合 $`{\bf R}^2`$ への作用ですが、回転〈rotation〉$`\mrm{Rot}`$ は次のようです。
$`\mrm{Rot} : {\bf R} \times {\bf R}^2 \to {\bf R}^2\In {\bf Set}\\
\text{For }t\in {\bf R},\, (x, y)\in {\bf R}^2\\
\quad \mrm{Rot}(t, (x, y)) := (\cos(t)x - \sin(t)y, \sin(t)x + \cos(t)y)
`$
$`t \in {\bf R}`$ に行列を対応させる写像（群の表現）を定義しても、作用 $`\mrm{Rot}`$ を定義するのと同じことです。行列を対応させる写像も同じ名前 $`\mrm{Rot}`$ を使うと：
$`\text{For }t\in {\bf R}\\
\quad \mrm{Rot}(t) := \begin{bmatrix}
\cos(t) & -\sin(t)\\
\sin(t) & \cos(t)
\end{bmatrix}
`$
今度は、群 $`\mrm{H}`$ の集合 $`{\bf R}^2`$ への作用の例です。行列を対応させる写像で定義してみます。以下の $`\mrm{GL}(2)`$ は2行2列可逆行列〈正則行列〉の群で、$`\mrm{Aut}({\bf R}^2)`$ に埋め込まれていると考えます。
$`\mrm{Ref} : \mrm{H} \to \mrm{GL}(2)\\
\quad \mrm{Ref}(s) := \begin{bmatrix}
1 & 0 \\
0 & -1
\end{bmatrix} \\
\quad \mrm{Ref}(t) := \begin{bmatrix}
-1 & 0 \\
0 & 1
\end{bmatrix}\\
\quad \mrm{Ref}(u) := \begin{bmatrix}
-1 & 0 \\
0 & -1
\end{bmatrix}\\
\quad \mrm{Ref}(e) := \begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix}
`$
定義された行列はそれぞれ、(1) x-軸に対する鏡映〈reflection〉、(2) y-軸に対する鏡映、(3) 原点と対称の位置への変換、(4) 何もしない、です。これが、群の表現になっているとは次が成立することです（すべて独立ではなく冗長）。
$`\quad \mrm{Ref}(x*y) = \mrm{Ref}(x)\mrm{Ref}(y)\\
\quad \mrm{Ref}(e) = E = \begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix}\\
\quad \mrm{Ref}(x^{-1}) = \mrm{Ref}(x)^{-1}
`$
群作用の軌道と軌道空間
$`\alpha`$ が群 $`G`$ の集合 $`X`$ への左群作用（右群作用でも同様）だとして、選ばれた $`c\in X`$ に対して次の写像を定義します。
$`\text{For }x\in X\\
\mrm{motion}^\alpha_c : G \to X \In {\bf Set}\\
\quad \mrm{motion}^\alpha_a := \alpha(\hyp, c) =
\lambda\, g\in G.\alpha(g, c)
`$
群が $`{\bf R}`$ の場合、$`t\in {\bf R}`$ を時間だと考えると、$`\mrm{motion}^\alpha_c`$ は、初期値（時刻 0 での値）が $`c \in X`$ である運動を記述します。群作用の軌道〈orbit〉は次のように定義します。
$`\quad \mrm{Orb}^\alpha_c := \mrm{Img}(\mrm{motion}^\alpha_c) =
\{x \in X\mid \exists g\in G.\, x = \mrm{motion}^\alpha_c(g) \}
`$
斜め45度並進の場合は、軌道は直線です。回転の場合の軌道は、原点中心の円周または原点（単元集合）です。$`\mrm{H}`$ の鏡映による表現の場合、軌道は原点の周りの4点、または2点、または原点（単元集合）です。
集合 $`X`$ 上に次の関係 $`\sim_\alpha`$ を定義します。
$`\text{For }x,y\in X\\
\quad x \sim_\alpha y :\Iff \exists g\in G.\, \alpha(g, x) = y
`$
関係 $`\sim_\alpha`$ は、$`X`$ 上の同値関係になります。その同値類は、群作用の軌道と同じことです。$`X`$ は同値関係 $`\sim_\alpha`$ の同値類に分割されますが、これは、$`X`$ が軌道に分割されることと同じことです。商集合 $`X/\!\sim_\alpha`$ を、群作用 $`\alpha`$ の軌道空間〈orbit space〉とも呼びます。商集合に位相や幾何構造があるわけではないですが、語呂がいいので「空間」を使います。
自由な群作用
過去記事「群の作用がナントカ -- おぼえられない」に、群作用の分類が憶えにくい、と書きました。自由な群作用の「自由」は、一般的な用法とは違い「不動点が無い〈fixed-point free〉」のことです。群作用 $`\alpha`$ が自由〈free〉なら、単位元以外の群元（群 $`G`$ の要素）の作用は不動点を持ちません。自由であることは次のように書けます*1。
$`\quad \forall g\in G.(\, g \ne I \Imp \forall x\in X.\, \alpha(g, x) \ne x \,)
`$
$`\alpha`$ が自由な群作用のとき、$`\mrm{motion}^\alpha_c`$ は、$`c \in X`$ に関わらず単射になります。これを示してみます。記法を簡略にするため、左群作用をドット（$`\cdot`$）で書きます。$`g\cdot c = g'\cdot c`$ を仮定して、$`g = g'`$ が出ればOKです。
次の計算（等式の同値変形）ができます。
$`\quad g\cdot c = g'\cdot c\\
\quad g'^{-1} \cdot ( g\cdot c) = g'^{-1} \cdot (g'\cdot c)\\
\quad (g'^{-1} * g)\cdot c = (g'^{-1} * g' ) \cdot c\\
\quad (g'^{-1} * g)\cdot c = e \cdot c\\
\quad (g'^{-1} * g)\cdot c = c
`$
$`h := g'^{-1} * g`$ と置くと、$`c`$ に対して次が成立します。
$`\quad h\cdot c = c`$
$`h`$ は不動点 $`c`$ を持つので、作用の自由性から単位元です。$`h = g'^{-1} * g = I`$ から $`g = g'`$ が出ます。これで次が示せました。
$`\quad \forall g\in G.(\, g \ne I \Imp \forall x\in X.\, g \cdot x \ne x \,)\\
\quad \Imp\\
\quad \forall c\in X.\forall g\in G.(\, g\cdot c = g'\cdot c \Imp g = g' \,)
`$
逆に、$`\mrm{motion}^\alpha_c`$ が $`c \in X`$ に関わらず単射ならば、$`\alpha`$ は自由な作用になります。仮定である“$`\mrm{motion}^\alpha_c`$ が単射なこと”は次のように書けます（「群作用の自由性：「論理式で書いてくれ」の続き」のせん断写像〈shear map〉の単射性と同じ命題です）。
$`\quad \forall g, g'\in G.(\, \mrm{motion}^\alpha_c(g) = \mrm{motion}^\alpha_c(g') \Imp g = g' \,)`$
$`c`$ を $`x`$ にリネームして（気分の問題）総称限量して、$`\mrm{motion}`$ を定義により展開すれば：
$`\quad \forall x\in X.\forall g, g'\in G.(\, g \cdot x = g'\cdot x \Imp g = g' \,)`$
これを仮定するなら、$`g' = I`$ と置いて、次が出ます。
$`\quad \forall x\in X.\forall g \in G.(\, g \cdot x = x \Imp g = I \,)`$
これは自由性の定義です。次が示せました。
$`\quad \forall x\in X.\forall g, g'\in G.(\, g \cdot x = g'\cdot x \Imp g = g' \,)\\
\quad \Imp\\
\quad \forall x\in X.\forall g \in G.(\, g \cdot x = x \Imp g = I \,)
`$
先の例で、単位元〈ゼロ〉以外の斜め45度並進は不動点を持たないので自由な作用です。回転は自由ではありません。例えば、360度〈$`2\pi`$〉回転は平面のどの点も不動点になります。90度回転でも原点は不動点になっています。$`\mrm{H}`$ の作用のときも、x-軸鏡映ならx-軸が不動点、y-軸鏡映ならy-軸が不動点、原点対称なら原点が不動点です。したがって自由な作用ではありません。
$`\alpha`$ が自由な群作用なら、すべての軌道 $`\mrm{Orb}^\alpha_c \subseteq X`$ が $`G`$ と（集合として）同型です。集合 $`X`$ は、（集合としての）$`G`$ のコピー達に分割されます。
軌道空間の基数
$`\alpha`$ は、群 $`G`$ の集合 $`X`$ への（左または右）作用だとします。さらに次を仮定します。
- $`\alpha`$ の軌道はすべて、（集合として）$`G`$ と同型である。
- $`G`$ も $`X`$ も有限である。
有限集合の基数〈cardinality〉（要素の個数）は自然数だとして、$`\mrm{card}(\hyp)`$ と書くことにします。群作用 $`\alpha`$ の軌道空間は $`X/_\alpha G`$ と書きます（通常は、$`\alpha`$ は省略します）。
集合 $`X`$ は軌道（$`X/_\alpha G`$ の要素）の直和となるので、次のように書けます。
$`\quad X \cong \sum_{S \in X/_\alpha G} S`$
これから、基数に関しては次が言えます。
$`\quad \mrm{card}(X) = \sum_{S \in X/_\alpha G} \card(S)`$
どの $`S`$（軌道）に関しても $`\mrm{card}(S) = \mrm{card}(G)`$（仮定より）なので、
$`\quad \mrm{card}(X) = \sum_{S \in X/_\alpha G} \card(G) = \mrm{card}(X/_\alpha G) \times \card(G)`$
$`\mrm{card}(X)`$ と $`\mrm{card}(G)`$ が分かっているときに、軌道空間の基数を求める公式は次のようになります。
$`\quad \mrm{card}(X/_\alpha G) = \frac{\mrm{card}(X)}{\card(G)}`$
順列と組み合わせ
自然数 $`n`$ に対して、$`\bar{n}`$ は次の意味です。
$`\quad \bar{n} := \{k \in {\bf N} \mid k \le n\}`$
“順列の数”と“組み合わせの数”は次のように定義します。
$`\quad {_n P_r} := \card(\mrm{InjMap}( \bar{r}, \bar{n} ) ) \\
\quad {_n C_r} := \card(\mrm{Pow}_r (\bar{n}) )
`$
ここで、$`\mrm{InjMap}(\hyp, \hyp)`$ は単射写像〈injective map〉の集合です。$`\mrm{Pow}_r (\hyp)`$ は、基数が $`r`$ である部分集合の集合です（下）。
$`\text{For }X\in |{\bf Set}|\\
\text{For }r\in {\bf N}\\
\quad \mrm{Pow}_r (X) := \{S\in \mrm{Pow}(X) \mid \card(S) = r \}`$
$`\mrm{Aut}(\bar{r})`$ は、双射 $`\sigma : \bar{r} \to \bar{r} \In {\bf Set}`$ からなる群です。双射写像〈bijective map〉の集合を $`\mrm{BijMap}(\hyp, \hyp)`$ として、次のように書けます。
$`\quad \mrm{Aut}(\bar{r}) = (\mrm{BijMap}(\bar{r}, \bar{r}), ;, \mrm{id}_{\bar{r}}, \hyp^{-1})`$
ここで、$`;`$ は図式順の関数結合〈関数合成〉の演算子記号です。記号の乱用を使うので、群 $`\mrm{Aut}(\bar{r})`$ と台集合 $`\mrm{BijMap}(\bar{r}, \bar{r})`$ をどちらも $`\mrm{Aut}(\bar{r})`$ と書きます。
$`\sigma \in \mrm{Aut}(\bar{r})`$ と $`f\in \mrm{InjMap}(\bar{r}, \bar{n})`$ があると、$`\sigma`$ を $`f`$ にプレ結合することができます。このプレ結合を、群の左作用だと考えます。つまり、群の左作用 $`\alpha`$ を次のように定義します。
$`\text{For }\sigma \in \mrm{Aut}(\bar{r})\\
\text{For }f \in \mrm{InjMap}(\bar{r}, \bar{n})\\
\quad \alpha(\sigma, f) := \sigma\,; f
`$
群 $`\mrm{Aut}(\bar{r})`$ の集合 $`\mrm{InjMap}(\bar{r}, \bar{n})`$ への左作用 $`\alpha`$ は、自由な作用であることはすぐ分かります。したがって、作用の軌道はすべて $`\mrm{Aut}(\bar{r})`$ と同型です。これは、前節の“公式”が適用できるセッティングです。軌道空間の基数は次のように求められます。
$`\quad \mrm{card}(\mrm{InjMap}(\bar{r}, \bar{n})/_\alpha \mrm{Aut}(\bar{r})) = \frac{\mrm{card}(\mrm{InjMap}(\bar{r}, \bar{n}))}{\card(\mrm{Aut}(\bar{r}))}`$
次の事実を考慮します。
$`\quad \mrm{Pow}_r(\bar{n}) \cong \mrm{InjMap}(\bar{r}, \bar{n})/_\alpha \mrm{Aut}(\bar{r}) \In {\bf Set}\\
\quad \mrm{Aut}(\bar{r}) \cong \mrm{InjMap}(\bar{r}, \bar{r}) \In {\bf Set}
`$
すると、次の等式が得られます。
$`\quad {_n C_r} = \frac{ {_n P_r} }{ {_r P_r } }`$
*1:作用が自由であることの定義を解釈するので四苦八苦したことは、「んもう、どっちなんだよ？ 論理式で書いてくれ」、「群作用の自由性：「論理式で書いてくれ」の続き」に書いてあります。
