同じものを含む順列と組分け｜高校数学A

学習指導要領数学A (2) 場合の数と確率ア (イ)「具体的な事象を基に順列及び組合せの意味を理解し，順列の総数や組合せの総数を求めること」のうち、同じものを含む順列・組分け・重複組合せ。

0. どういうまとまりか

「区別がつかないもの」が入ると、区別して数えたものを、区別できない分の並べ方で割ることになります。何で割るかがこのノートの中心です。

数えるもの	総数	割る理由
a が $p$ 個、b が $q$ 個、c が $r$ 個の順列	$\frac{n !}{p ! q ! r !}$	同じ文字どうしを入れかえても同じ並び
9 人を 3 人ずつ A、B、C の組に分ける	$_{9} C_{3} \times_{6} C_{3}$	割らない（組に名前がある）
9 人を 3 人ずつ 3 組に分ける	$_{9} C_{3} \times_{6} C_{3} \div 3!$	組の名前を入れかえても同じ分け方
$n$ 種類から重複を許して $r$ 個選ぶ	$_{n + r - 1} C_{r}$	○ $r$ 個と｜ $n - 1$ 本の並べ方

分かれ目は次の 3 つ。

同じものは、その個数の階乗で割る
組に区別がなく、人数が同じ組が $k$ 組あるときだけ $k!$ で割る。人数が違う組は区別がつくので割らない
重複組合せは、仕切り｜の本数が種類の数より 1 少ない

1. 同じものを含む順列と最短経路

根拠: 学習指導要領数学A-(2)-ア-(イ)

同じものを含む順列は、「どの位置に a を置くかを選び、残りの位置からどこに b を置くかを選ぶ」と考えると、組合せでも数えられます。

a が $p$ 個、b が $q$ 個、c が $r$ 個、合わせて $n$ 個（ $p + q + r = n$ ）を 1 列に並べる同じものを含む順列の総数は？

$\frac{n !}{p ! q ! r !}$

全部を区別して並べた $n!$ 通りのうち、a どうし・b どうし・c どうしを入れかえた $p! q! r!$ 通りずつが同じ並びになる。

同じものを含む順列 $\frac{n !}{p ! q ! r !}$ を、組合せで表すと？（ $p + q + r = n$ ）

$_{n} C_{p} \times_{n - p} C_{q}$

$n$ か所から a を置く $p$ か所を選び、残り $n - p$ か所から b を置く $q$ か所を選ぶ。残りには c が入るので、選ぶのは 2 回でよい。

碁盤の目の道を、東へ $m$ 区画、北へ $n$ 区画進む最短経路の数は？

$\frac{( m + n )!}{m ! n !}$ 通り（ $_{m + n} C_{m}$ 通り）

最短経路は「東」 $m$ 個と「北」 $n$ 個を 1 列に並べたものと 1 対 1 に対応する。

最短経路で「点 P を通る」経路の数は、どう数えるか？

（出発点から P までの最短経路の数）×（P から到着点までの最短経路の数）

前半を決め、そのそれぞれについて後半を決めるので積の法則。「P を通らない」経路は、全体から P を通る経路を引く。

2. 組分け

根拠: 学習指導要領数学A-(2)-ア-(イ)

組分けは、まず組に名前がある（A 組、B 組、C 組）として組合せで数え、名前が無いときは名前の付け方の分を割ります。

異なる 9 個を、3 個ずつ A、B、C の 3 つの組 に分ける分け方は？

$_{9} C_{3} \times_{6} C_{3}$ 通り（最後の組は残りで決まる）

A に入る 3 個を選び、残り 6 個から B に入る 3 個を選ぶ。組に名前があるので割らない。

異なるものを、同じ個数ずつ区別のない $k$ 組に分けるとき、区別のある組で数えた数を何で割るか？

$k!$ で割る

区別のない組の分け方 1 つに、組の名前 A、B、C… の付け方が $k!$ 通りずつ対応するから。

異なる 6 個を 3 個・2 個・1 個の 3 組に分けるとき、組に名前がなくても割らなくてよいのはなぜか？

組の個数がすべて違うので、個数で組が区別できるから

$_{6} C_{3} \times_{3} C_{2} = 60$ 通りのまま。組の名前を入れかえると個数が変わってしまい、同じ分け方にならない。

異なる 8 個を 4 個・2 個・2 個の区別のない 3 組に分けるとき、何で割るか？

$2!$ で割る（個数が同じ 2 組の分だけ）

4 個の組は個数で区別できる。区別がつかないのは 2 個ずつの 2 組だけなので、 $3!$ ではなく $2!$ 。

3. 重複組合せ

根拠: 学習指導要領数学A-(2)-ア-(イ)

同じ種類のものを何個選んでもよいとき、選んだもの $r$ 個を○で、種類の境目を｜で表すと、選び方は ○ と｜の並べ方になります。

$n$ 種類のものから、重複を許して $r$ 個選ぶ重複組合せの総数は？

$_{n + r - 1} C_{r}$ 通り

○ $r$ 個と仕切り｜ $n - 1$ 本の、合わせて $n + r - 1$ か所から○の位置 $r$ か所を選ぶ。

重複組合せを○と｜で表すとき、仕切り｜は何本使うか？（ $n$ 種類から選ぶ）

$n - 1$ 本

3 種類を分ける境目は 2 本。仕切りを $n$ 本にすると、1 つ多い数を数えてしまう。

方程式 $x + y + z = r$ の 0 以上の整数解の組 $(x, y, z)$ の個数は？

$_{r + 2} C_{2}$ 個

○ $r$ 個と｜2 本の並べ方。1 つ目の仕切りの前の○の数が $x$ 、仕切りの間が $y$ 、後ろが $z$ 。

「どの種類も少なくとも 1 個は選ぶ」重複組合せは、どう数えるか？

先に各種類を 1 個ずつ選んでおき、残りを重複組合せで選ぶ

$n$ 種類から $r$ 個で各 1 個以上なら、残り $r - n$ 個を $n$ 種類から選ぶので $_{r - 1} C_{r - n}$ 通り。

練習問題

問 1　A、A、B、B、B、C の 6 文字を 1 列に並べる並べ方は何通りか。

60 通り

方針　1 列に並べるので順番は区別するが、A どうし・B どうしは区別がつかない。そこで、いったん 6 文字を全部区別して並べた数を求め、同じ文字どうしを入れかえただけの並び（見た目が同じになる分）の数で割る。

6 文字を全部区別して並べると、 $6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720$ 通り
A の 2 個を入れかえても同じ並びで、その入れかえ方は $2! = 2$ 通り。B の 3 個の入れかえ方は $3! = 6$ 通り。C は 1 個なので $1! = 1$ 通り
見た目が同じ並び 1 つにつき、 $2 \times 6 \times 1 = 12$ 通りずつを重ねて数えている。
割る。 $\frac{6 !}{2 ! 3 ! 1 !} = \frac{720}{12} = 60$

別解（組合せで数える）：6 か所から A を置く 2 か所を選んで $_{6} C_{2} = 15$ 通り、残り 4 か所から B を置く 3 か所を選んで $_{4} C_{3} = 4$ 通り。C は残りの 1 か所に入るので、 $15 \times 4 = 60$ 。

問 2　碁盤の目の道で、地点 S から東へ 5 区画、北へ 4 区画離れた地点 G まで最短経路で行く。点 P は S から東へ 2 区画、北へ 1 区画の交差点である。
(1) 最短経路は全部で何通りか。(2) P を通る経路は何通りか。(3) P を通らない経路は何通りか。

(1) 126 通り　(2) 60 通り　(3) 66 通り

方針　最短経路は、東へ 1 区画進むことを「東」、北へ 1 区画進むことを「北」と書くと、「東」5 個と「北」4 個を 1 列に並べたものと 1 対 1 に対応する。だから同じものを含む順列で数える。「P を通る」は前半（S から P）と後半（P から G）を続けて決めるので掛け、「P を通らない」は全体から引く。

(1) 「東」5 個と「北」4 個、合わせて $5 + 4 = 9$ 個の並べ方を求める。 $\frac{9 !}{5 ! 4 !} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = 126$ 通り
(2) S から P までは「東」2 個と「北」1 個の並べ方。 $\frac{3 !}{2 ! 1 !} = \frac{6}{2} = 3$ 通り
P から G までに進む区画を求める。東へ $5 - 2 = 3$ 区画、北へ $4 - 1 = 3$ 区画
P から G までは「東」3 個と「北」3 個の並べ方。 $\frac{6 !}{3 ! 3 !} = \frac{720}{36} = 20$ 通り
前半のそれぞれについて後半があるので掛ける。 $3 \times 20 = 60$ 通り
(3) 経路は「P を通る」か「P を通らない」かのどちらかなので、全体から引く。 $126 - 60 = 66$ 通り

問 3　6 人を 2 人ずつ 3 つの組に分ける。
(1) 組を A、B、C と区別するとき、分け方は何通りか。(2) 組を区別しないとき、分け方は何通りか。

(1) 90 通り　(2) 15 通り

方針　組分けは、まず組に名前がある（A、B、C）として、「A に入る人を選び、残りから B に入る人を選ぶ」と組合せで数える。組を区別しないときは、3 組とも同じ人数で見分けがつかないので、名前の付け方の数 $3!$ で割る。

(1) 6 人から A に入る 2 人を選ぶ。 $_{6} C_{2} = \frac{6 \times 5}{2 \times 1} = 15$ 通り
残り $6 - 2 = 4$ 人から B に入る 2 人を選ぶ。 $_{4} C_{2} = \frac{4 \times 3}{2 \times 1} = 6$ 通り
最後に残った 2 人が C に入る（1 通り）ので、 $15 \times 6 = 90$ 通り
(2) 組を区別しない分け方 1 つに対して、3 つの組に A、B、C の名前を付ける方法が $3! = 6$ 通りある。つまり (1) の 90 通りは、同じ分け方を 6 回ずつ数えている。
割る。 $90 \div 6 = 15$ 通り

確かめ：6 人のうちの 1 人に注目すると、その相手の選び方は 5 通り。残り 4 人のうちの 1 人に注目すると、その相手は 3 通り。最後の 2 人は自動的に組になるので、 $5 \times 3 = 15$ 通り。

問 4　8 人を 4 人、2 人、2 人の 3 つの組に分ける（組に名前はない）。分け方は何通りか。

210 通り

方針　まず組に名前をつけた（4 人の組、2 人の組その 1、2 人の組その 2）として組合せで数え、そのあと区別のつかない組の分だけ割る。区別がつかないのは人数が同じ組どうしだけなので、割る数は 2 人の組 2 つを入れかえる $2!$ である。

8 人から 4 人の組に入る人を選ぶ。 $_{8} C_{4} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70$ 通り
残り $8 - 4 = 4$ 人から、1 つ目の 2 人の組に入る人を選ぶ。 $_{4} C_{2} = \frac{4 \times 3}{2 \times 1} = 6$ 通り。最後に残った 2 人が 2 つ目の 2 人の組になる。
掛ける。 $70 \times 6 = 420$ 通り（2 人の組に「1 つ目」「2 つ目」の区別をつけた数）
実際には 2 人の組どうしは区別がつかず、入れかえた $2! = 2$ 通りずつが同じ分け方なので割る。 $420 \div 2 = 210$ 通り

ここで間違えやすい　3 組あるからと $3! = 6$ で割って 70 通りにしない。4 人の組は人数で見分けがつくので、2 人の組と入れかわることはない。

問 5　りんご、みかん、かきの 3 種類の果物から合わせて 6 個を買う（同じ種類をいくつ買ってもよい）。
(1) 買わない種類があってもよいとき、買い方は何通りか。(2) どの種類も少なくとも 1 個買うとき、買い方は何通りか。

(1) 28 通り　(2) 10 通り

方針　買う順番は関係なく（組合せ）、同じ種類を何個買ってもよいので重複組合せ。買う果物を○、種類の境目を仕切り｜で表すと、買い方は○と｜の並べ方と 1 対 1 に対応する。(2) の「どの種類も少なくとも 1 個」は、先に 1 個ずつ買っておき、残りを自由に選ぶ問題に直す。

(1) 買う 6 個を○ 6 個で表す。3 種類を分ける仕切り｜は $3 - 1 = 2$ 本。たとえば ○○｜○○○｜○ は、りんご 2 個・みかん 3 個・かき 1 個を表す。
○と｜を合わせた $6 + 2 = 8$ か所から、｜を置く 2 か所を選べば並べ方が 1 つ決まる。 $_{8} C_{2} = \frac{8 \times 7}{2 \times 1} = 28$ 通り
(2) 先に 3 種類を 1 個ずつ買う。残りは $6 - 3 = 3$ 個で、これはどの種類から選んでもよい。
残り 3 個を 3 種類から重複を許して選ぶ。○ 3 個と｜2 本で、合わせて $3 + 2 = 5$ か所
その 5 か所から｜を置く 2 か所を選ぶ。 $_{5} C_{2} = \frac{5 \times 4}{2 \times 1} = 10$ 通り

ここで間違えやすい　仕切りを種類の数と同じ 3 本にしない（3 種類の境目は 2 本）。また、重複順列の $3^{6}$ にもしない。それは 6 個を買う順番まで区別した数である。

問 6　方程式 $x + y + z = 10$ を満たす正の整数の組 $(x, y, z)$ はいくつあるか。

36 個

方針　0 以上の整数解なら、○と仕切り｜の並べ方（重複組合せ）で数えられる。この問題は正の整数、つまり「どれも 1 以上」なので、先に $x$ 、 $y$ 、 $z$ に 1 ずつ配っておき、残りを 0 以上で分ける問題に直す。

$x = x^{'} + 1$ 、 $y = y^{'} + 1$ 、 $z = z^{'} + 1$ とおく。 $x$ 、 $y$ 、 $z$ が正の整数であることは、 $x^{'}$ 、 $y^{'}$ 、 $z^{'}$ が 0 以上の整数であることと同じ。
もとの方程式に代入する。 $(x^{'} + 1) + (y^{'} + 1) + (z^{'} + 1) = 10$
左辺の $1 + 1 + 1 = 3$ を右辺に移項すると、 $10 - 3 = 7$ なので、 $x^{'} + y^{'} + z^{'} = 7$
この 0 以上の整数解は、○ 7 個と｜2 本の並べ方と 1 対 1 に対応する。並べる場所は $7 + 2 = 9$ か所
その 9 か所から｜を置く 2 か所を選ぶ。 $_{9} C_{2} = \frac{9 \times 8}{2 \times 1} = 36$ 個

別解：○を 10 個並べ、○と○の間の $10 - 1 = 9$ か所から仕切りを入れる 2 か所を選ぶ。間にしか入れないので、どの部分にも○が 1 個以上入る。これも $_{9} C_{2} = 36$ 個。