- 表紙
- まとめ
- 具体例
- 理解
数学のまとめノート
「順列」とは
いくつかのものからいくつかを選び順番に並べる並べ方のこと。
階乗
自然数 $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 \leqq r$ を満たす自然数である. なお,
${}_n \mathrm{P}_n = n!$
である.
A. 順列の計算の意味
- $n$ 個のものを並べる順列の総数は $n!$ に一致する
- $n$ 個のものから $r$ 個を選んで並べる順列の総数は ${}_n \mathrm{P}_r$ に一致する
B. さまざまな順列の総数
- 円順列：$n$ 個のものから $r$ 個を選び円形に並べる順列の総数は $\frac{{}_n \mathrm{P}_r}{n}$ である
- 重複順列：$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) $n$ 通りずつ重複する
(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)$ を満たす.
順列の具体例
順列の考え方を応用した並べ方の総数
じゅず順列
$n$ 個の玉でじゅずを作る場合の数$$\frac{(n-1)!}{2}$$
隣リ合う順列
大人が5人・子どもが3人いる。
全員が一列に並ぶ。
子どもが全員隣り合う順列$$(5+1)! \times 3!$$
両端に並ぶ順列
大人が5人・子どもが3人いる。
全員が一列に並ぶ。
端っこは大人が立っておく順列$${}_5 \mathrm{P}_2! \times ((5-2)+3)!$$
プレゼント交換
完全順列に対応する。
$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{array}{cl}
{}_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 r} \\
\end{array}$$
この順番にしっかりと注意しておいてください。
階乗と順列、組合せの公式の条件
何か気にしていないことに気付かないでしょうか？
そうです。$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$ の計算はしていませんが、是非自分で考えてみてください。
ここまで、お読みいただき、ありがとうございます。
