数学A 場合の数 問題 39 解説

方針・初手

「組に名前が付いているか」で数え方が変わる。

(1)では $A$ 組、$B$ 組、$C$ 組と名前が付いているので、同じ生徒の分け方でも $A$ と $B$ を入れ替えれば別の方法である。

一方、(2)(3)では単に「3つの組」とあるので、組そのものには名前が付いていないものとして数える。また、(4)の $S(n,k)$ は、組に名前を付けずに、どの組にも少なくとも1人が入る分け方の総数である。

解法1

(1)

まず $A$ 組に入る2人を5人から選ぶ。これは

$$ {}_5C_2 $$

通りである。

次に、残った3人から $B$ 組に入る2人を選ぶ。これは

$$ {}_3C_2 $$

通りである。

残った1人は自動的に $C$ 組に入る。したがって、求める方法の数は

$$ {}_5C_2{}_3C_2=10\cdot 3=30 $$

である。

(2)

組に名前が付いていないので、(1)で数えた方法のうち、人数が2人の2組を入れ替えたものは同じ分け方である。

(1)では、2人組を $A$ 組、$B$ 組として区別して数えているため、各分け方を $2!$ 回ずつ数えている。

したがって、求める方法の数は

$$ \frac{30}{2!}=15 $$

である。

別の数え方として、1人組になる生徒を選ぶと $5$ 通りである。残った4人を2人組2つに分ける方法は

$$ \frac{{}_4C_2}{2}=3 $$

通りであるから、

$$ 5\cdot 3=15 $$

としてもよい。

(3)

5人を空でない3組に分けるとき、各組の人数の組合せは

$$ 3,1,1 $$

または

$$ 2,2,1 $$

の2通りである。

まず、人数が $3,1,1$ となる場合を数える。3人組に入る生徒を5人から選べば、残り2人はそれぞれ1人組になる。よって

$$ {}_5C_3=10 $$

通りである。

次に、人数が $2,2,1$ となる場合を数える。これは(2)と同じ状況であるから

$$ 15 $$

通りである。

したがって、求める方法の数は

$$ 10+15=25 $$

である。

(4)

$n+1$ 人の生徒を $k$ 個の空でない組に分ける方法を、特定の1人、たとえば $(n+1)$ 番目の生徒に注目して分類する。

この生徒が1人だけの組を作る場合、残りの $n$ 人は $k-1$ 個の空でない組に分ければよい。したがって、この場合の方法の数は

$$ S(n,k-1) $$

である。

一方、この生徒が1人だけの組を作らない場合を考える。このとき、まず残りの $n$ 人を $k$ 個の空でない組に分ける。これは

$$ S(n,k) $$

通りである。

その後、$(n+1)$ 番目の生徒を、その $k$ 個の組のうちどれか1つに加えればよい。この選び方は $k$ 通りである。したがって、この場合の方法の数は

$$ kS(n,k) $$

である。

以上の2つの場合は重複せず、また $n+1$ 人を $k$ 個の空でない組に分ける方法をすべて尽くしている。よって

$$ S(n+1,k)=S(n,k-1)+kS(n,k) $$

が成り立つ。

解説

この問題では、「組に名前があるかどうか」の区別が最も重要である。

(1)では $A,B,C$ という名前があるため、組を区別して数える。したがって、多項係数

$$ \frac{5!}{2!2!1!} $$

を使ってもよい。

一方、(2)(3)では組に名前がないため、同じ人数の組を入れ替えた重複を割る必要がある。(2)では2人組が2つあるので、$2!$ で割ることになる。

(4)はスターリング数の第二種の漸化式である。新しく追加した1人が「単独の組を作るか」「既存の組に入るか」で分類するのが典型的な考え方である。

答え

(1)

$$ 30 $$

通り。

(2)

$$ 15 $$

通り。

(3)

$$ 25 $$

通り。

(4)

$$ S(n+1,k)=S(n,k-1)+kS(n,k) $$

が成り立つ。