- 目次
- 理解
- コード
- まとめ
【理解】順列の数学的解説
階乗と順列の定義と意味について
$n! := n \cdot (n-1) \cdot \cdots \cdot 2 \cdot 1$
定義（階乗）
自然数 $n$ に対して, $n$ の階乗 $n!$ を
$n! = n \cdot (n-1) \cdot \cdots \cdot 2 \cdot 1$
と定める.
また, $0!=1$ と定める.
たとえば,
$1!$ $=1$,
$2!$ $=2 \cdot 1$ $=2$,
$3!$ $=3 \cdot 2 \cdot 1$ $=6$
です。
$\displaystyle {}_n \mathrm{P}_r := \frac{n!}{(n-r)!}$
定義（順列）
自然数 $n$ と $r$ $(1 \leqq r \leqq n)$ に対して, 順列 ${}_n\mathrm{P}_r$ を
$\begin{aligned}
{}_n\mathrm{P}_r &= \frac{n!}{(n-r)!} \\
&= n \cdot (n-1) \cdot \cdots \cdot (n-r+1)
\end{aligned}$
と定める.
たとえば,
${}_5\mathrm{P}_1$ $=5$,
${}_5\mathrm{P}_2$ $=5 \cdot 4$ $=20$,
${}_5\mathrm{P}_3$ $=5 \cdot 4 \cdot 3$ $=60$
です。
Column. 階乗 $n!$ と順列 ${}_n\mathrm{P}_r$ の意味
※ $0! = 1$
※ ${}_n\mathrm{P}_n = n!$
※ ${}_n\mathrm{P}_0 = 1$
階乗、順列と組合せで $0!$, ${}_n\mathrm{P}_0$, ${}_n\mathrm{C}_0$ がナゼ 1 であるのかを確かめましょう。
順列の計算記号と組合せの計算記号の考え方を、「順列と組合せ」の意味を通して理解すること、文字の定義域として許される値を正確にきちっと整理する、が目標です。
階乗と順列、組合せの意味が分かる！
階乗と順列、組合せの定義式と意味
場合の数の単元は、並べたり選んだりする単元です。何を並べたり選んだりするかによって単位が変わります。今回は「人」を並べたり選んだりすることに統一します。
階乗（factorial）
階乗とは、$n \geqq 1$ としたときの、
$$n! = n \times (n-1) \times \cdots \times 2 \times 1$$
のことです。
中学校で学ぶ樹形図の考え方を思い出せば、$n!$ は、
$n$人の人物が並ぶときの並び方の総数
という意味になります。
$$n! = n \times (n-1) \times \cdots \times 2 \times 1$$
順列（permutation）
順列とは、次のように並べることを言います。
何人かの中から、数人選び、並べること
これが順列の意味です。
この並べ方を計算式にしましょう。
$n$ 人の中から、$r$ 人を選び並べる場合の数を求めるときは、
$$\frac{n!}{(n-r)!}$$
という計算になります。この計算式は ${}_n {\mathrm P}_r$ という記号で表します。
また、これは次のようにもなります。
$$n \times (n-1) \times \cdots \times (n-r+1)$$
$${}_n {\mathrm P}_r = \frac{n!}{(n-r)!}=n \times (n-1) \times \cdots \times (n-r+1)$$
組合せ（Combination）
組合せとは、次のように選ぶことを言います。
何人かの中から、数人選ぶこと
これが組合せの意味です。
この選び方を計算式にしましょう。
$n$ 人の中から、$r$ 人選ぶことの場合の数を求めるときは、
$$\frac{n!}{(n-r)! \times r!} = \frac{{}_n{\mathrm P}_r}{r!}$$
という計算になります。この計算式は ${}_n {\mathrm C}_r$ という記号で表します。
また、これは次のようにもなります。
$$\frac{n \times (n-1) \times \cdots \times (n-r+1)}{1 \times 2 \times \cdots r}$$
$$\begin{aligned}
{}_n {\mathrm C}_r & \displaystyle = \frac{{}_n{\mathrm P}_r}{r!} \\
& \displaystyle =\frac{n!}{(n-r)! \times r!} \\
& \displaystyle =\frac{n \times (n-1) \times \cdots \times (n-r+1)}{1 \times 2 \times \cdots \times r} \\
\end{aligned}$$
この順番にしっかりと注意しておいてください。
階乗と順列、組合せの定義式の条件の注意
何か気にしていないことに気付かないでしょうか？
そうです。$n$ と $r$ の条件を決めていません。階乗の式は、$1 \leqq n$ の自然数と定めましたが、他の式はどうでしょうか？
全ての式を俯瞰して、条件を吟味しましょう。
- 全ての公式に、$n!$ がある→全ての公式で $1 \leqq n$ である
- 順列の公式は、$r=n$であると、分母に $0!$ が現れる→ $r < n$ が必要である（この時点では、なんと ${}_n {\mathrm P}_n$ の計算は定義式から導けない！）
- 組合せの公式は、$r=n$ や $r=0$ であると、分母に $0!$ が現れる→ $0 < r <n$ が必要である（この時点では、なんと ${}_n {\mathrm C}_n$ の計算は定義式から導けない！）
実は、この段階では、$0!$ や ${}_n {\mathrm P}_n$, ${}_n {\mathrm P}_0$ , ${}_n {\mathrm C}_n$, ${}_n {\mathrm C}_0$ の値は定義の公式から導くことができません。
これでは困りますね。。←なぜ、困るでしょうか？
例えば、${}_n {\mathrm C}_n$ という $n$ 人全員を選ぶ計算が同じ式で出来ません。
${}_n {\mathrm P}_n$ と $n!$ の意味
公式の意味を考えて、$0! = 1$ 等を作っていきましょう。
まず、${}_n {\mathrm P}_n$ と $0!$ からです。
順列の公式は、$1 \leqq n$ かつ $1\leqq r < n$ のとき、
$${}_n {\mathrm P}_r = \frac{n!}{(n-r)!}$$
でした。
$r=n$ のとき $\displaystyle {}_n {\mathrm P}_n = \frac{n!}{0!}$ となってしまいます。
${}_n {\mathrm P}_n$の数式を計算するのではなく、「意味」を使います。
$n$ 人の中から $n$ 人を選び、並べる総数
$n!$ の意味も同じく次の意味でした。
$n$人の人物が並ぶときの並び方の総数
この意味に沿うように数式の値を決めます！
${}_n {\mathrm P}_n$ と $n!$ は同じものだから、$$n! = \frac{n!}{0!}$$ です。
この式から、$0! = 1$ と定めないと、整合性が保てないことになります。
$0 \leqq n$ のときの $n!$ と、$1 \leqq n$ と $1 \leqq r \leqq n$ のときの ${}_n {\mathrm P}_r$ を定めることができました。
意味も理屈も何も矛盾しないようにするためには、数式の中に登場する $0!$ を $1$ と解釈することが必要になります。
$0! = 1$ という式は「ゼロとビックリマークとイチ」という数字の関係ばかり見ていると全く理解できない式です。ただ、「順列の意味」を見てあげると完璧な数式と見えるようになります。
${}_n {\mathrm P}_0$ の意味
$0!=1$という式を手に入れました。$r=0$ として、${}_n {\mathrm P}_0$ を考えましょう。
$${}_n {\mathrm P}_0 = \frac{n!}{(n-0)!} = \frac{n!}{n!} = 1$$
となり、なんの疑問もなく計算できます。だから、${}_n {\mathrm P}_0=1$ です。
次に、${}_n {\mathrm P}_0=1$ の意味を考えます。
そもそも ${}_n {\mathrm P}_0=1$ に意味なんてあるのでしょうか？
$n$ 人の中から、誰も選ばずに、並べる場合の数の総数は「1」通り
つまり、何も選ばないという場合の1通りが ${}_n {\mathrm P}_0$ の計算結果と合致しています。
${}_n {\mathrm P}_0$ は「計算的」にも「順列の意味的」にも「1」が妥当と分かりました。
$1 \leqq n$ と $0 \leqq r \leqq n$ のときの ${}_n {\mathrm P}_r$ を定めることができました。
${}_n {\mathrm C}_n$ と ${}_n {\mathrm C}_0$ との意味
$0! = 1$ を使って、${}_n {\mathrm C}_n$ の値も ${}_n {\mathrm C}_0$ の値も計算しましょう。
ただし、$1 \leqq n$ かつ $0 < r < n$ でした。
$${}_n {\mathrm C}_n = \frac{n!}{n!(n-n)!} = \frac{n!}{n! \times 0!} = 1$$
$${}_n {\mathrm C}_0 = \frac{n!}{0!(n-0)!} = \frac{n!}{0! \times n!} = 1$$
すなわち、${}_n {\mathrm C}_n = {}_n {\mathrm C}_0 =1$ が得られます。
これより、組合せの ${}_n {\mathrm C}_r$ も、$1 \leqq n$ で $0 \leqq r \leqq n$ のときに定めることができました。
さて、この計算結果は、組合せの意味と合致しているでしょうか？
$n$ 人の中から $n$ 人を選ぶことは、全員を選ぶという意味で「1」通りだけ
したがって、${}_n {\mathrm C}_n$ の計算結果と、組合せは合致しています。
$n$ 人の中から $0$ 人を選ぶことは、誰も選ばないという意味で「1」通りだけ
こちらも、${}_n {\mathrm C}_0$ の計算結果と、組合せは合致しています。
階乗と順列、組合せの意味と計算のまとめ
階乗の $0! = 1$ という式は、計算で自動的に求まるのではありません。
階乗や順列、組合せの公式は、元来の意味を合わせて考慮することで、${}_n {\mathrm P}_r$ も ${}_n {\mathrm C}_r$ も便利な公式になるのです。
不思議な式ですが、意味と数式の整合性を保つことから、$0! = 1$ が決まります。
$0!=1$ が自然な式としか思えなくなります。
今回は、$n=0$ のときの、${}_0 {\mathrm P}_0$ と ${}_0 {\mathrm C}_0$ の計算はしていませんが、是非自分で考えてみてください。
ここまで、お読みいただき、ありがとうございます。
応用的な並べ方について
$n$ 個のものから $r$ 個を選び円形に並べる順列の総数
$\displaystyle \frac{{}_n \mathrm{P}_r}{r}$ (通り)
円形に並べる順列の総数を計算する式を求めてみよう。
命題
$n$ 個のものから $r$ 個を選び円形に並べる順列の総数は
$\displaystyle \frac{{}_n\mathrm{P}_r}{r}$
である. 特に, $n$ 個のものをすべて円形に並べる順列の総数は
$(n-1)!$
となる.
理屈.
$n$ 個のものから $r$ 個を選び一列に並べる順列の総数は ${}_n\mathrm{P}_r$ 通りであった.
ある $r$ 個のものを $x_1$, $x_2$, $\ldots$, $x_r$ とする. この $r$ 個が $x_1 x_ 2 \cdots x_{r-1}x_r$ の順番に一列に並んでいたとすると, 以下の $r$ 通りの並び方
$\begin{aligned}
& x_1 x_ 2 \cdots x_{r-1}x_r \\
& x_2 x_ 3 \cdots x_r x_1 \\
& x_3 x_ 4 \cdots x_1 x_2 \\
& \vdots \\
& x_r x_ 1 \cdots x_{r-2}x_{r-1}
\end{aligned}$
は, 円形に並び変えたときにすべて同じ並び方になる.
すなわち, 一列に並べる順列の総数${}_n\mathrm{P}_r$ のうち, 円形に並び替えたときに同じ並び方になるものが $r$ 通りずつ存在することが分かる
したがって, $n$ 個のものから $r$ 個を選び円形に並べる順列の総数は
$\displaystyle \frac{{}_n\mathrm{P}_r}{r}$
である.
なお, $r=n$ のときは, ${}_n\mathrm{P}_r = n!$ であるから, $n$ 個のものをすべて円形に並べる順列の総数は
$\displaystyle \frac{n!}{n}$ $=(n-1)!$
となる.
$5$ 人のうち, $3$ 人が円形に並ぶ順列の総数は,
${}_5\mathrm{P}_3 \div 3$ $=20$
通りです。
もし, $5$ 人全員が円形に並ぶ場合は,
$4!$ $=24$
通りです。
$n$ 種類のものを同じものの重複を許して $r$ 個並べる順列の総数
$n^r$ (通り)
重複を許して（同じものを利用してもよい）並べる順列の総数を計算する式を求めてみよう。
命題
$n$ 種類のものを同じものの重複を許して $r$ 個並べる順列の総数は
$n^r$
である.
理屈.
1つ目の選び方は $n$ 通りである. 2つ目の選び方も $n$ 通りである. 任意の番号の位置の選び方も $n$ 通りである.
ゆえに, $r$ 個の並べ方は
$n \times \cdots \times n$ ($r$ 個の積)
$=n^r$
通りである.
$5$ 色のクレヨンがあって, $3$ か所に色を塗る塗り方は,
$5^3$ $=125$
通りです。
$n$ 個のうち $s$ 個, $t$ 個, $\cdots$ が同じもので, これらをすべて並べる順列の総数
$\displaystyle \frac{n!}{s! \cdot t! \cdots}$ (通り)
同じものを含む順列の総数を計算する式を求めてみよう。
命題
$n$ 個のうち, $s$ 個, $t$ 個, $\cdots$ ずつ同じものあるとする. これらすべてを並べる順列の総数は
$\displaystyle \frac{n!}{s! \cdot t! \cdot \cdots}$
である.
理屈.
すべて異なる $n$ 個のものを一列に並べる順列の総数は $n!$ 通りであった.
この任意の並べ方のうち, $x_1$, $x_2$, $\ldots$, $x_s$ 番目の$s$ 箇所に着目する.
$n-s$ 箇所のものは並べ変えずに, この $s$ 箇所のものだけを並べ変えるとすると, その並べ変え方の総数は $s!$ 通りである.
$x_1$, $x_2$, $\ldots$, $x_s$ 番目にあるものが同じものであった場合, この $s!$ 通りの並び替えを行ったとしても $n$ 個の並び方は同じままである.
つまり, 異なるもの $n$ 個のうち, $s$ 個を同じものとすると, 各並び方に対して $s!$ 通りずつ同じ並び方が重複することになる.
ゆえに, $n$ 個のうち $s$ 個が同じものであるときの順列の総数は $\displaystyle \frac{n!}{s!}$ 通りであると分かる.
さらに, 残りの $n-s$ 個の中に他の同じものが存在する場合は, 上記の考え方を繰り返すことで, $n$ 個のうち, $s$ 個, $t$ 個, $\cdots$ ずつ同じものある場合の順列の総数が
$\displaystyle \frac{n!}{s! \cdot t! \cdot \cdots}$
と分かる.
$a$, $a$, $a$, $b$, $b$, $c$ の $6$ 個を並べる順列の総数は
$\displaystyle \frac{6!}{3! \cdot 2! \cdot 1!}$ $=60$
通りです。
（準備中）完全順列：$n$ 個のものを, $k$ 番目のものを $k$ 番目以外に並べるときの順列の総数
$\displaystyle n!\sum_{k=0}^n\frac{(-1)^k}{k!}$ (通り)
$n$ 個のものを, $k$ 番目のものを $k$ 番目以外に並べるときの順列の総数は
$\displaystyle n! - \sum_{k=1}^n (-1)^{k+1} {}_n \mathrm{C}_{k}(n-k)!$ $\displaystyle =n!\sum_{k=0}^n\frac{(-1)^k}{k!}$
である
具体的な並べ方について
$n$ 人のうち $x$ 人が隣り合う指定がある順列の総数
$x! \times (n-x+1)!$ (通り)
［例］大人が5人と子どもが3人いる。
全員が一列に並ぶうち, 子どもが全員隣り合う順列の総数は
$3! \times (5+1)!$ (通り)
である。
$n$ 人のうち $x$ 人のうちの $2$ 人が両端に並ぶ指定がある順列の総数
${}_x\mathrm{P}_2 \times (n-2)!$ (通り)
［例］大人が5人と子どもが3人いる。
全員が一列に並ぶうち, 端っこは大人が立っておく順列の総数は
${}_5 \mathrm{P}_2 \times ((5+3)-2)!$
である。
$n$ 個の玉でできる数珠の総数（じゅず順列）
$\displaystyle\frac{(n-1)!}{2}$ (通り)
$n$ 個の玉を円の形につなぐ総数は円順列なので $(n-1)!$ である。
「数珠」は表裏にすることもできる。
裏返す回転をする軸を基準で線対称な２つの数珠は表裏で同じ数珠になる。
ゆえに, 裏表で2つずつ同じ数珠の重複ができるので,
じゅずを作る場合の数は $\displaystyle \frac{(n-1)!}{2}$ 通りになる。
プレゼント🎁の交換の仕方の総数
プレゼント交換では、自分が用意したプレゼントを誰にも渡せなければ寂しいので、完全順列で考える。
【コード】Pythonで順列の計算
階乗math.factorial()の出力
順列math.perm()の出力
階乗と順列の値をPythonで計算してみよう。
階乗と順列の値
数学の関数を利用するためにmathモジュールを利用する。
階乗はmath.factorial()関数を利用する。$n!$ を計算する場合は, factorial(n)とする。
順列はmath.perm()関数を利用する。${}_n \mathrm{P}_r$ を計算する場合は, perm(n, r)とする。
Pythonコード入力例. $5!$ と ${}_{10} \mathrm{P}_4$ の値を出力する。
import math
print(math.factorial(5))
print(math.perm(10,4))
まとめノート
「順列」とは
いくつかのものからいくつかを選び順番に並べる並べ方のこと。
階乗
自然数 $n$ について
$n! = n \cdot (n-1) \cdots 2 \cdot 1$
とする
定義
$\displaystyle {}_n \mathrm{P}_r = \frac{n!}{(n-r)!}$
$= n \cdot (n-1) \cdots (n-r+1)$.
ただし, $n$ と $r$ は $n \geqq r$ を満たす自然数である. なお,
${}_n \mathrm{P}_n = n!$
である.
A. 順列の計算の意味
- $n$ 個のものを並べる順列の総数は $n!$ に一致する
- $n$ 個のものから $r$ 個を選んで並べる順列の総数は ${}_n \mathrm{P}_r$ に一致する
B. さまざまな順列の総数
- 円順列：$n$ 個のものから $r$ 個を選び円形に並べる順列の総数は $\frac{{}_n \mathrm{P}_r}{r}$ である
- 重複順列：$n$ 種類のものを同じものの重複を許して $r$ 個並べる順列の総数は ${}_n \Pi_r = n^r$ である
- 同じものを含む順列：$n$ 個のうち $s$ 個, $t$ 個, $\cdots$ が同じもので, これらをすべて並べる順列の総数は $\frac{n!}{s! \cdot t! \cdots}$ である
- 完全順列：$n$ 個のものを, $k$ 番目のものを $k$ 番目以外に並べるときの順列の総数は $\displaystyle n! - \sum_{k=1}^n (-1)^{k+1} {}_n \mathrm{C}_{k}(n-k)!$ $\displaystyle =n!\sum_{k=0}^n\frac{(-1)^k}{k!}$ である
ポイント解説
注意
$n! = {}_n \mathrm{P}_n = n!/0!$ より
$0! = 1$
で, ${}_n \mathrm{P}_0 = n!/n!=1$ より
${}_n \mathrm{P}_0=1$
.
A
樹形図を計算で数え上げる；$3!$ の例
B
(1) $r$ 通りずつ重複する
(2) $r$ 箇所それぞれ $n$ 種類ずつ選択できる；
(3) $s!$ や $r!$ 通りずつ重複する
(4) 余事象は「どこかは固定される」であり $\displaystyle \sum_{k=1}^n (-1)^{k+1} {}_n \mathrm{C}_{k}(n-k)!$ で求まる；
発展
ガンマ関数 $\Gamma(x)$ は $n \in \mathbb{N}$ のとき, $\Gamma(n+1)=n!$ であり, 階乗の拡張である. なお, $\Gamma(x+1) = x \Gamma(x)$ を満たす.
