順列・組合せ | 場合の数と確率統計

1 順列と組合せ

定義 1.1 (順列と組合せ). 異なる $n$ 個から $r$ 個を選んで一列に並べる方法の個数を ${}_nP_r$ と書きます。異なる $n$ 個から順序を区別せずに $r$ 個を選ぶ方法の個数を ${}_nC_r$ と書きます。ただし、 $n,r$ は $0\le r\le n$ を満たす整数とします。

積の法則から順列の公式を導きます。

公式 1.2 (順列の公式).

{}_nP_r=n(n-1)\cdots(n-r+1)=\frac{n!}{(n-r)!}.

証明. 第1番目は $n$ 通り、第2番目は残りの $n-1$ 通りであり、同様に第 $r$ 番目は $n-r+1$ 通りです。積の法則を用いると公式を得ます。▨

選んだ $r$ 個の並べ替えをまとめて数えると、組合せの公式を得ます。

公式 1.3 (組合せの公式).

{}_nC_r=\frac{{}_nP_r}{r!}=\frac{n!}{r!(n-r)!}.

証明. 一つの $r$ 個の組からは $r!$ 通りの順列が得られます。したがって ${}_nP_r=r!\,{}_nC_r$ です。両辺を $r!$ で割ると公式を得ます。▨

公式 1.4 (二項係数の対称性).

{}_nC_r={}_nC_{n-r}.

二項係数の対称性が成り立つのは、選ぶ $r$ 個を決めることと、選ばない $n-r$ 個を決めることが一対一に対応するためです。

2 同じものを含む順列

公式 2.1 (同じものを含む順列). $n$ 個のうち同じ種類のものがそれぞれ $n_1,\ldots,n_k$ 個あり、 $n_1+\cdots+n_k=n$ であるとき、異なる並べ方は

\frac{n!}{n_1!\cdots n_k!}

通りあります。

証明. 一時的にすべてを区別すると $n!$ 通りです。同じ種類の $n_i$ 個につけた印を入れ替える $n_i!$ 通りは同じ並びを表すので、各 $i$ について割ります。▨

例 2.2. 文字列 MISSISSIPPI には M が1個、I が4個、S が4個、P が2個あります。異なる並べ方は

\frac{11!}{4!4!2!}

通りです。

3 円順列

公式 3.1 (円順列). 異なる $n$ 個を円形に並べ、回転によって一致する並びを同一視すると、並べ方は $(n-1)!$ 通りあります。ただし $n\ge1$ とします。

証明. 一つの対象を基準位置へ固定すると、残りの $n-1$ 個を並べる順列と一対一に対応します。鏡映による一致は同一視していないので、さらに2で割りません。▨

4 重複を許す組合せ

公式 4.1 (重複組合せ). $n$ 種類から重複を許して合計 $r$ 個を選ぶ方法は

{}_{n+r-1}C_r

通りあります。ただし $n\ge1,\ r\ge0$ とします。

証明. 各種類を選ぶ個数を $x_1,\ldots,x_n$ とすると、 $x_1+\cdots+x_n=r$ を満たす非負整数解を数えればよいです。 $r$ 個の丸と $n-1$ 本の仕切りを一列に並べる方法に対応するので、全 $n+r-1$ 箇所から丸の $r$ 箇所を選びます。▨

5 例題

レベル1 — 順列の計算

次の値を計算せよ。

解法の型 ${}_{n}\mathrm{P}_{r} = n(n-1)\cdots(n-r+1)$

例 5.1.

{}_{5}\mathrm{P}_{4}

答 $120$

レベル2 — 組合せの計算

次の値を計算せよ。

解法の型 ${}_{n}\mathrm{C}_{r} = {}_{n}\mathrm{P}_{r}/r!$ 。 $r$ が大きければ ${}_{n}\mathrm{C}_{n-r}$ に直すと楽

例 5.2.

{}_{6}\mathrm{C}_{4}

答 $15$

注意 ${}_{6}\mathrm{C}_{2}$ に直すと計算が軽い（ ${}_{n}\mathrm{C}_{r} = {}_{n}\mathrm{C}_{n-r}$ ）

6 演習

問題 6.1. 8人から会長と副会長を1人ずつ選ぶ方法の数と、委員2人を選ぶ方法の数をそれぞれ求めよ。

解答.

会長と副会長は役職が異なるので、選ぶ順序を区別する。公式 1.2により、会長と副会長を選ぶ方法は ${}_8P_2=8\cdot7=56$ 通りである。委員2人には役職の区別がないので、順序を区別しない。公式 1.3により、委員2人を選ぶ方法は ${}_8C_2=56/2!=28$ 通りである。▨

問題 6.2. 文字列 BANANA の6文字を並べ替えてできる、異なる文字列の個数を求めよ。

解答.

BANANA には B が1個、A が3個、N が2個ある。公式 2.1により、異なる並べ方は

\frac{6!}{1!\,3!\,2!}=\frac{720}{12}=60

通りである。▨

問題 6.3. 6人を円卓に並べる方法の数を、回転によって一致する並びを同一視して求めよ。

解答.

公式 3.1を $n=6$ として用いると、並べ方は $(6-1)!=5!=120$ 通りである。▨

問題 6.4. 4種類の菓子から重複を許して7個を選ぶ方法の数を求めよ。ただし、同じ種類の菓子は区別しない。

解答.

公式 4.1を $n=4$ 、 $r=7$ として用いると、選び方は ${}_{4+7-1}C_7={}_{10}C_7={}_{10}C_3=120$ 通りである。▨

レベル1 — 順列の計算

次の値を計算せよ。

解法の型 ${}_{n}\mathrm{P}_{r} = n(n-1)\cdots(n-r+1)$

問題 6.5.

{}_{6}\mathrm{P}_{4}

解答.

答 $360$ ▨

問題 6.6.

{}_{7}\mathrm{P}_{3}

解答.

答 $210$ ▨

レベル2 — 組合せの計算

次の値を計算せよ。

解法の型 ${}_{n}\mathrm{C}_{r} = {}_{n}\mathrm{P}_{r}/r!$ 。 $r$ が大きければ ${}_{n}\mathrm{C}_{n-r}$ に直すと楽

問題 6.7.

{}_{9}\mathrm{C}_{5}

解答.

答 $126$

注意 ${}_{9}\mathrm{C}_{4}$ に直すと計算が軽い（ ${}_{n}\mathrm{C}_{r} = {}_{n}\mathrm{C}_{n-r}$ ）▨

問題 6.8.

{}_{9}\mathrm{C}_{2}

解答.

答 $36$ ▨

§B4.3順列・組合せ

1 順列と組合せ

2 同じものを含む順列

3 円順列

4 重複を許す組合せ

5 例題

6 演習

前提記事