順列と組合せの違いは?公式は暗記ではなく意味で理解する

本記事はスキルチェックリストの[データサイエンス力 No.1]「順列や組合せを式 nPr, nCr を用いて計算できる」に対応しています。

順列と組み合わせの違い

あなたがミニカーのマニアだったとしましょう。
お気に入りのコレクションの中からいくつかを厳選して、順番に棚に並べていきます。このときの並べ方のパターンを順列といいます。

順列のイメージ

そして、このコレクションの中にはもう飽きてしまったものもあります。それらは箱に詰め込んで奥にしまっておきましょうか。箱に詰めるので順番は関係ありません。大事なのは何を選んで箱に入れるかです。この選び方のことを組み合わせといいます。

組み合わせのイメージ

順列は「並べ方」、組み合わせは「選び方」です

ロボ千代

順列の計算

では、実際に順列の計算をしてみましょう。

A,B,Cという3つのアルファベットから2つを選んで、順に並べます。
この並べ方(順列)はいくつあるでしょうか?

1番目に並べるアルファベットはAかBかCの3パターンです。

1番目にAを選んだ場合、2番目に選べるのはBかCの2パターンです。

1番目にBを選んだ場合、2番目に選べるのはAかCの2パターンです。

1番目にCを選んだ場合、2番目に選べるのはAかBの2パターンです。

つまり、3パターンのそれぞれに2パターンずつ並べ方があるので、3×2で合計6パターンあるといえます。

次にこれをもう少し一般的にあらわしてみましょう。

ロボ千代

n個の中からr個を選んで並べる順列を数式で
$${}_n P_r$$
と表します。Pは順列の英語である「パーミュテーション(Permutation)」の頭文字です。

このとき、順列の数がいくつになるか計算してみましょう。

1個めの選び方はn通り、2個めの選び方はn-1通り、3個めの選び方はn-2通り…と考えていくと、最後のr個めの選び方はn-(r-1)通りとなります。

よって、順列は

$${}_n P_r=n\times(n-1)\times…\times(n-(r-1))$$

と計算することができます。

階乗で順列を表す
先ほどの順列の式ですが「階乗」を使ってもっと簡潔に表すこともできますので、その表現も学んでおきましょう。

「階乗」とは1からある整数まで1ずつ増やしながらかけ合わせたものを指します。
例えば、「5の階乗」ならば、
$$1\times2\times3\times4\times5$$
となります。

なお、自然数nの階乗を数式で
$$n!$$と表します。

この階乗をうまく使えるように
$${}_n P_r=n\times(n-1)\times…\times(n-(r-1))$$
の式を変形していくのです。

順列の式をよく見ると、nから始まって、1ずつ減らしながらかけ合わせていますね。
これをr個で止めずに最後の1個までかけ合わせてみましょう。まさに「nの階乗」となりますよね。
つまり、$$(n-r)\times(n-r-1)\times…\times3\times2\times1$$を元の式の分母と分子にかけてあげれば、階乗をうまく使えそうです。

\begin{eqnarray}
{}_n P_r&=&n\times(n-1)\times…\times(n-r+1) \\
&=&\frac{n\times(n-1)\times…\times(n-r+1)\color{red}{\times(n-r)\times(n-r-1)\times…\times3\times2\times1}}{\color{red}{(n-r)\times(n-r-1)\times…\times3\times2\times1}} \\
&=&\frac{n!}{(n-r)!}
\end{eqnarray}

アイ

とってもスッキリしたわ

ちなみに、n個の中からn個を選んで並べる順列を考えてみると、
これは$$n\times(n-1)\times(n-2)\times…\times3\times2\times1$$
となりますね。つまり、これはnの階乗そのままです。

よって、
$${}_n P_n=n!$$
となります。

組み合わせの計算

「順列」の次は「組み合わせ」です。

n個の中からr個を選ぶ選び方(組み合わせ)を数式で
$${}_n C_r$$
と表します。Cは組み合わせの英語である「コンビネーション(Combination)」の頭文字です。

A,B,Cという3つのアルファベットから2つを選びます。この選び方(組み合わせ)はいくつあるでしょうか?

突然ですがここで順列のことを思い出してください。

順列は手順を分解して考えると、「3つのうちから2つを選ぶ」×「選んだ2つを順番に並べる」ということだとわかります。

そして、組み合わせというのは「3つのうちから2つ選ぶ」ことですね。

ということは、

$${}_3 P_2={}_3 C_2×(選んだ2つを順番に並べる)$$
が成り立ちます。

「選んだ2つを順番に並べる」というのは、少しくどい言い方をすると「2つのうち2つを選んで並べる順列」のことですね。
よって、
$${}_3 P_2={}_3 C_2\times{}_2 P_2$$
が成り立ちます。

アイ

順列と組み合わせにはこんな関係性があるのね

今は組み合わせを求めたいので、「組み合わせ」を左辺に持ってきて式変形します。

$${}_3 C_2=\frac{{}_3 P_2}{{}_2 P_2}=\frac{3\times2}{2\times1}=3$$

よって、組み合わせは3通りとなります。

では、先ほどの組み合わせを求める式を、n個の中からr個を選ぶ組み合わせとして一般化してみましょう。

順列と組み合わせの関係

左辺に組み合わせを持っていくと、

$${}_n C_r=\frac{{}_n P_r}{{}_r P_r}=\frac{{}_n P_r}{r!}$$

さらに、\({}_n P_r\)を階乗を使って表してすっきりさせてみます。

$${}_n C_r=\frac{\frac{n!}{(n-r)!}}{r!}=\frac{n!}{r!(n-r)!}$$

おなじみの組み合わせの公式になりましたね。

順列と組み合わせの公式のまとめ

順列:n個の中からr個を選んで並べるときの並べ方
$${}_n P_r=\frac{n!}{(n-r)!}$$
組み合わせ:n個の中からr個を選ぶときの選び方
$${}_n C_r=\frac{{}_n P_r}{r!}=\frac{n!}{r!(n-r)!}$$

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です