円順列が (n-1)! になる理由
異なる $r$ 個の要素から成る集合 $\{x_1,x_2,\dots,x_r\}$ を取り出したとき、
その内部で並べる（順序をつける）方法の総数は
$$
r \times (r-1)\times \cdots \times 1 := r!
$$
である。
$r$ を正の整数とする。第$1$位置に置く要素は、集合の中から任意の$1$つを選べるので $r$ 通り。
第$2$位置に置く要素は、残りの $r-1$ 個から任意に選べるので $r-1$ 通り。
同様に、第 $k$ 位置には残りの $r-(k-1)$ 個から選ぶので $r-k+1$ 通り。
最終的に第 $r$ 位置には $r - (r-1) = 1$ 通り しか選択肢がない。
$ $
各段階での選択肢の数は、それ以前に何を選んだかに依らず一定である。
すなわち、第$1$段階で何を選んでも、第$2$段階の選択肢の数は変わらないため、乗法原理より
$$
r \times (r-1)\times (r-2)\times \cdots \times 1
\;=\;r!
$$
が全並べ方の総数となる。
$$ \Box$$
$n$個のものから$r$個を取り出して並べる順列の総数は、
$$
\begin{aligned}
\frac{n!}{(n - r)!}
\end{aligned}
$$
である。ここで、$n$ は全体の要素の数、$r$は選び取る要素の数、$n!$は$n$の階乗を表し、
$$
\begin{aligned}
n! := n \times (n-1) \times (n-2) \times \dots \times 1
\end{aligned}
$$
で定義される。
$n,r$を整数とし、$1 \le r \le n$とする。
$ $
$n$個の異なるものから $r$ 個を順番に選んで並べるとき、
最初に何を選び、次に何を選ぶかというように段階的に考える。
- 第$1$段階
最初の$1$個を選ぶとき、選べるのは $n$ 個のうちのどれかであるから、$n$ 通り - 第$2$段階
次に$1$個選ぶときは、すでに$1$個使っているので、残りは $n - 1$ 個 - 第$3$段階
次に$1$個選ぶときは、すでに$2$個使っているので、残りは $n - 2$ 個
$$ \vdots $$ - 第$r$段階
最後に $r$ 個目を選ぶときは、残りは $n - (r - 1) = n - r + 1$ 個
-よって、これらは連続した選択の段階であり、各段階での場合の数を掛け合わせればよい（乗法原理）。
すなわち、$r$個を順番に選ぶ方法の総数は、
$$
n \times (n - 1) \times (n - 2) \times \cdots \times (n - r + 1)
$$
これを階乗によって表すと、$n!$ の前から $r$ 個だけ掛け合わせたものに等しい。すなわち、
$$
\frac{n!}{(n - r)!}
$$
である。
$$ \Box$$
異なるものを並べる順番付きの組み合わせを順列という。
順列の総数を計算する場合、$n$個のものから$r$個を取り出して並べる順列の総数は、次のように定義される。
$$
\begin{aligned}
{}_{n}P_{r} := \frac{n!}{(n - r)!}
\end{aligned}
$$
ここで、$n$ は全体の要素の数、$r$は選び取る要素の数、$n!$は$n$の階乗を表し、
$$
\begin{aligned}
n! := n \times (n-1) \times (n-2) \times \dots \times 1
\end{aligned}
$$
で定義される。
$ n $ 個の互いに区別可能な元からなる集合 $ S $ に対し、円形に配置することを「配置」と呼び、
配置のうち回転変換によって一致するものを同一視する。
$ $
すなわち、配置 $ (a_1, a_2, \dots, a_n) $ と、任意の $ k \in \{0, 1, \dots, n-1\} $ に対して
$$
(a_1, a_2, \dots, a_n) \sim (a_{1+k \mod n}, a_{2+k \mod n}, \dots, a_{n+k \mod n})
$$
とみなす。このとき、順列の個数は
$$
\frac{n!}{n} = (n-1)!
$$
となる。
$n$を$1$以上の整数とする。
集合 $S$ の元を $n$ 個すべて並べる順列は、通常の（直線上の）順列として
$$
n!
$$
通り存在する。しかし、ここでは「回転によって一致する並べ方を同一視する」ので、以下のように考える。
$ $
直線上で並べた順列 $(a_1, a_2, \dots, a_n)$ を円形に配置するとき、回転によって同じ配置になるものは、
以下のように対応する。
$$
(a_1, a_2, \dots, a_n),
\quad
(a_2, a_3, \dots, a_n, a_1),
\quad
(a_3, a_4, \dots, a_n, a_1, a_2),
\;\dots\;,
\quad
(a_n, a_1, a_2, \dots, a_{n-1})
$$
これは、配置 $ (a_1, a_2, \dots, a_n) $ と、任意の $ k \in \{0, 1, \dots, n-1\} $ に対して
$$
(a_1, a_2, \dots, a_n) \sim (a_{1+k \mod n}, a_{2+k \mod n}, \dots, a_{n+k \mod n})
$$
とみなす事に等しい。
ここで、$\bmod n$ は「$n$ で割った余り」を取ることを意味する。
インデックスが $n$ を超えたら、ぐるっと先頭に戻るために使っている。
$ $
例として $n=5$ で説明すると、$k=2$ のとき
- $1+2=3$
ここで、$3 \bmod 5$ は、$3$ を $5$ で割ると、$0$ 回しか割れなくて余りが $3$ であるから、
$$ 3 \bmod 5 = 3 $$
よって、
$$ a_{1+2\ \bmod\ 5} = a_3 $$ - $4+2=6$
ここで、$6 \bmod 5$ は、$6$ を $5$ で割ると、$1$ 回割れて余りが $1$ であるから、
$$ 6 \bmod 5=1 $$
よって、
$$ a_{4+2\ \bmod\ 5} = a_1 $$
-なので
$$
(a_1,a_2,a_3,a_4,a_5)
\sim
(a_{1+2 \bmod 5}, a_{2+2 \bmod 5}, \dots, a_{5+2 \bmod 5})
\sim
(a_3,a_4,a_5,a_1,a_2)
$$
となり、直観的には、$k$は左へと移動させた回数と見なせる。
ここで、任意の順列 $(a_1,\dots,a_n)$ は、出発点まで巡り着くまでにちょうど $n$ 回の操作が必要である(補足を参照)。
$ $
すなわち、通常の順列の集合を「回転による同値関係」で割ると、
$1$つの同値類（同一視されるクラス）には必ずちょうど $n$ 個の順列が含まれる。
$ $
以上より、順列全体の個数が $n!$ 通りあり、各同値類にちょうど $n$ 個ずつ順列が含まれるので、
円形配置の「代表パターン」（回転で同一視したときのクラス）全体の個数は
$$
\frac{n!}{n} = (n-1)!
$$
となる。
$$ \Box$$
$n$ 個の互いに異なる元 $a_1,\dots,a_n$ があるとする。
添字は $\{1,2,\dots,n\}$ を法 $n$ で見たもの（円周上の番号）とみなす。
$ $
■ 仮定
ある $k$（$1 \le k \le n-1$）について
$$
\text{「k だけ回転させても元の並びと同じになる」}
$$
と仮定する。すなわち、
$$
(a_1,\dots,a_n)
=
(a_{1+k\ \bmod\ n},\dots,a_{n+k\ \bmod\ n})\cdots★
$$
が成り立つと仮定する。
$ $
一般に
$$
(x_1,\dots,x_n) = (y_1,\dots,y_n)
$$
が成り立つとは、「各成分が等しい」という意味なので
$$
x_i = y_i \quad (i=1,\dots,n)
$$
がすべて成り立つ。これを $★$ に適用すると
$$
a_i = a_{i+k\ \bmod\ n} \quad (i=1,\dots,n)
\cdots①
$$
が全ての $i$ について成り立つ。ここで、① に対して $i=1$ の場合に適用すると
$$
a_1 = a_{1+k\ \bmod\ n}\cdots②
$$
が得られる。ここで、$1 \le k \le n-1$ なので $1+k$ は $2,3,\dots,n$ のいずれかである。
$1+k< n$の場合と、$1+k=n$の$2$通りに分けて考える。
- $1+k < n$ の場合
$1 \le k \le n-2$ のときは $1+k$ は
$$ 2 \le 1+k \le n-1 < n $$
なので、$1+k$ を $n$ で割ると、商が$0$となるから、
$$ 1+k = 0 \cdot n + (1+k) $$
となり、余りが $1+k$ となる。したがって
$$ (1+k) \bmod n = 1+k $$
となる。したがって、この場合
$$ a_{1+k\ \bmod\ n} = a_{1+k} $$
であるから ② は $a_1 = a_{1+k}$ という形になる。
$ $ - $1+k = n$ の場合
直ちに、
$$ a_{1+k} = a_n $$
が成り立つ（単に「$1+k$ 番目 = $n$ 番目」なので同じ要素）。
一方で ② から、
$$ a_1 = a_{1+k\ \bmod\ n} $$
である。ここで
$$ 1+k = n = 1\cdot n + 0 $$
なので、通常の整数の剰余としては
$$ (1+k)\ \bmod\ n = n \bmod n = 0 $$
である。ここで、余り $0$ を添字 $n$ と同一視すると、
$$ a_{1+k\ \bmod\ n} = a_n $$
となる。したがって、② から、
$$ a_1 = a_n $$
を得る。
-いずれにせよ、
$$
a_1 = a_j
$$
となる添字 $j$ が存在し、その $j$ は
$$
j = 1+k \in \{2,3,\dots,n\}
$$
なので $j \neq 1$ である。もともとの前提で「$a_1,\dots,a_n$ は互いに異なる」と仮定しており、
$$
i \neq j \quad\Rightarrow\quad a_i \neq a_j
$$
が成り立つ、しかし、いま $1 \neq j$ かつ $a_1 = a_j$ という状況が ② から導かれ、
これは明らかに「互いに異なる」という仮定に反する。
$ $
したがって、そもそもの仮定 $★$ が間違っており、つまり、$1 \le k \le n-1$ の中で、
$$
(a_1,\dots,a_n)
=
(a_{1+k\ \bmod\ n},\dots,a_{n+k\ \bmod\ n})\cdots★
$$
が成り立つことはありえないと結論できる。
$ $
言い換えると、並べ方を $k$ 個だけ回転させて同じ並べ方になるのは
$k=0$（＝全く回転しない）か、 $k$ が $n$ の倍数（＝ちょうど $1$周、$2$周…回して元に戻る） の場合だけ。
$ $
今回考えているのは $1 \le k \le n-1$だから、
「非自明な回転（$0$ でも $1$ 周分でもない回し方）で元の順列に戻ることはない」 という結論になる。
$n$ 個の異なるものを円形に並べたとき、回転によって一致する並べ方を同一視したときの並べ方のことを、
$n$ 個の円順列という。
この記事を高評価した人
この記事に送られたバッジ
投稿者
