場合の数
ある事柄が起こりうるすべての場合について数え上げたときの総数
順列・組合せの定義
順列
いくつかのものの中から必要な数を取って並べたとき、順番まで考慮する場合の数
$$
{}_n\mathrm{P}_r = \frac{n!}{(n-r)!}
$$
組合せ
いくつかのものの中から必要な数を取って並べたとき、順番を考慮しない場合の数
$$
{}_n\mathrm{C}_r = \frac{_n\mathrm{P}_r}{r!}
$$
定義に対するイメージの掴み方
${}_4\mathrm{P}_3$ および ${}_4\mathrm{C}_3$ の場合の例を示します。
4つの英字ABCDから3つ選び順番を考慮して並べたときの場合の数を考える。
1文字目の選び方は4通り、2文字目はさきほど選んだ文字は使えないことから3通り、と繰り返し考えていくと
| 文字の位置 | 選べる文字 | パターン数 |
|---|---|---|
| 1文字目 | ABCD | 4 |
| 2文字目 | BCD(Aを選んだ場合) | 3 |
| 3文字目 | CD(A -> Bと選んだ場合) | 2 |
となる。
上記から選び方はそれぞれ4通り、3通り、2通りとなっているので $4\times3\times2$ として $24$ 。
これを順列の公式に当てはめて考えてみると
$$
{}_4\mathrm{P}_3 = \frac{4!}{(4-3)!} = \frac{4\times3\times2\times1}{1} = 24
$$
$\times1$や分母の$1$が気になると思うがこれは公式を階乗の記号で表すための便宜である。 $4\times3\times2$が求めているものだが、これを階乗の記号で表すために分母で打ち消している。
たとえば${}_4\mathrm{P}_2$であれば、1文字目の選び方は4通り、2文字目は3通りとなる。これを階乗の記号で表す場合は下記となる。
$$
{}_4\mathrm{P}_2 = \frac{4!}{(4-2)!} = \frac{4\times3\times2\times1}{2\times1} = 12
$$
これで公式とイメージが紐づいたと思う。
また、順番を考えなくて良い場合は ${}_4\mathrm{C}_3$ となる。このイメージを掴むためには順番を考慮した場合について考えるとよい。この場合は一つの選び方、たとえばABCを選んだとすると次のように6パターンあることがわかる。
- ABC
- ACB
- BAC
- BCA
- CAB
- CBA
したがって順番を考慮すると選び方1つに対し6パターンあると考えられる。これはさきほどの順列の結果を6で割ってやれば良いということである。 $24\div6$ で $4$ となる。
公式に当てはめてみると
$$
{}_4\mathrm{C}_3 = \frac{{}_4\mathrm{P}_3}{3!} = \frac{24}{3\times2\times1} = 4
$$
として確認できた
組合せの公式
$$\begin{aligned}
{}_n\mathrm{C}_r &= {}_n\mathrm{C}_{n-r}
&\quad&\llap{(1)}
\\
{}_n\mathrm{C}_r &= {}_{n-1}\mathrm{C}_{r} + {}_{n-1}\mathrm{C}_{r-1}
&\llap{(2)}
\\
r{}_n\mathrm{C}_r &= n{}_{n-1}\mathrm{C}_{r-1}
&\llap{(3)}
\end{aligned}$$
$(1)$ の証明
$$\begin{aligned}
{}_n\mathrm{C}_r &= \frac{n!}{(n-r)!r!}
\\
&= \frac{n!}{r!(n-r)!}
\\
&= \frac{{}_n\mathrm{P}_r}{(n-r)!}
\\
&= \frac{{}_n\mathrm{P}_{n-(n-r)}}{(n-r)!}
\\
&= {}_n\mathrm{C}_{n-r}
\end{aligned}$$
$(2)$ の証明
$$\begin{aligned}
{}_{n-1}\mathrm{C}_{r} + {}_{n-1}\mathrm{C}_{r-1} &= \frac{(n-1)!}{\{(n-1)-r\}!r!} + \frac{(n-1)!}{\{(n-1)-(r-1)\}!(r-1)!}
\\
&= \frac{(n-1)!}{(n-1-r)!r!} + \frac{(n-1)!}{(n-1-r+1)!(r-1)!}
\\
&= \frac{(n-1)!}{(n-r-1)!r!} + \frac{(n-1)!}{(n-r)!(r-1)!}
\\
&= \frac{{\color{red}(n-r)}(n-1)!}{{\color{red}(n-r)}(n-r-1)!r!} + \frac{(n-1)!{\color{red}r}}{(n-r)!(r-1)!{\color{red}r}}
\\
&= \frac{(n-r)(n-1)!}{{\color{red}(n-r)!}r!} + \frac{(n-1)!r}{(n-r)!{\color{red}r!}}
\\
&= \frac{(n-r)(n-1)! + (n-1)!r}{(n-r)!r!}
\\
&= \frac{(n-1)!\left\{(n-r) + r\right\}}{(n-r)!r!}
\\
&= \frac{(n-1)!n}{(n-r)!r!}
\\
&= \frac{n!}{(n-r)!r!}
\\
&= {}_n\mathrm{C}_r
\end{aligned}$$
$(3)$ の証明
$$\begin{aligned}
r{}_n\mathrm{C}_r &= r\frac{n!}{(n-r)!r!}
\\
&= \frac{n!{\color{red}r}}{(n-r)!{\color{red}(r-1)!r}}
\\
&= \frac{n!}{(n-r)!(r-1)!}
\\
&= \frac{{\color{red}n(n-1)!}}{(n-r)!(r-1)!}
\\
&= n\frac{(n-1)!}{(n-r{\color{red}-1+1})!(r-1)!}
\\
&= n\frac{(n-1)!}{(n-1-r+1)!(r-1)!}
\\
&= n\frac{(n-1)!}{\{n-1{\color{red}-(r-1)}\}!(r-1)!}
\\
&= n{}_{n-1}\mathrm{C}_{r-1}
\end{aligned}$$
