この問題は、組合せの問題、最短経路の問題、組分けの問題、順列の問題から構成されています。具体的には、以下の問題があります。 (1) 8個のリンゴを3人に配る方法の総数を求めます (もらわない人がいても良い)。 (2) 方程式 $x+y+z=9$ を満たす自然数の組 $(x, y, z)$ の総数を求めます。 (3) 図における点Pから点Qへの最短経路の数を求めます。 (4) (3)の最短経路のうち、RS間を通るものの数を求めます。 (5) 9人の生徒を3人ずつA, B, Cの3組に組分けする方法の数を求めます。 (6) 9人の生徒を3人ずつ3組に組分けする方法の数を求めます。 (7) 9人の生徒を2組A, Bに組分けする方法の数を求めます。 (8) "sleeper"の7文字を並べ替えてできる文字列の数を求めます。 (9) "sleeper"の7文字を並べ替えてできる文字列のうち、両端にeが存在しないような文字列の数を求めます。

1. 問題の内容

この問題は、組合せの問題、最短経路の問題、組分けの問題、順列の問題から構成されています。具体的には、以下の問題があります。

(1) 8個のリンゴを3人に配る方法の総数を求めます (もらわない人がいても良い)。

(2) 方程式 $x+y+z=9$ を満たす自然数の組 $(x, y, z)$ の総数を求めます。

(3) 図における点Pから点Qへの最短経路の数を求めます。

(4) (3)の最短経路のうち、RS間を通るものの数を求めます。

(5) 9人の生徒を3人ずつA, B, Cの3組に組分けする方法の数を求めます。

(6) 9人の生徒を3人ずつ3組に組分けする方法の数を求めます。

(7) 9人の生徒を2組A, Bに組分けする方法の数を求めます。

(8) "sleeper"の7文字を並べ替えてできる文字列の数を求めます。

(9) "sleeper"の7文字を並べ替えてできる文字列のうち、両端にeが存在しないような文字列の数を求めます。

2. 解き方の手順

(1) リンゴを配る問題

これは重複組合せの問題です。3人にリンゴを配るので、$x+y+z = 8$を満たす非負整数の組$(x, y, z)$の個数を求めます。

これは、$_{8+3-1}C_{3-1} = _{10}C_2 = \frac{10 \times 9}{2 \times 1} = 45$通りです。

(2) 方程式を満たす自然数の組を求める問題

$x+y+z = 9$を満たす自然数の組$(x, y, z)$の個数を求めます。

$x'=x-1, y'=y-1, z'=z-1$とおくと、$x', y', z'$は非負の整数であり、$x'+1+y'+1+z'+1 = 9$となるので、$x'+y'+z' = 6$を満たす非負整数の組$(x', y', z')$の個数を求めれば良いです。

これは重複組合せの問題なので、$_{6+3-1}C_{3-1} = _8C_2 = \frac{8 \times 7}{2 \times 1} = 28$通りです。

(3) 最短経路を求める問題

PからQまでの最短経路は、右に4回、下に3回移動する必要があります。

したがって、最短経路の総数は$_{4+3}C_4 = _7C_4 = _7C_3 = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$通りです。

(4) RS間を通る最短経路を求める問題

PからRまでの最短経路は右に2回、下に1回移動する必要があります。その経路数は$_{2+1}C_2 = _3C_2 = 3$通り。

SからQまでの最短経路は右に1回、下に2回移動する必要があります。その経路数は$_{1+2}C_1 = _3C_1 = 3$通り。

RからSへの最短経路は1通り。

したがって、PからRを通ってSを通ってQへ行く最短経路の数は、$3 \times 1 \times 3 = 9$通りです。

(5) 3人ずつの組分け

9人から3人を選び、A組とする。残りの6人から3人を選び、B組とする。残りの3人をC組とする。

したがって、組分けの方法は、$_9C_3 \times _6C_3 \times _3C_3 = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} \times \frac{6 \times 5 \times 4}{3 \times 2 \times 1} \times 1 = 84 \times 20 = 1680$通りです。

(6) 3人ずつの組分け(組の区別なし)

(5)で求めた1680通りは、組にA,B,Cの区別がある場合の数です。組の区別がない場合、3つの組の並び順を考慮する必要がなくなるので、3!で割る必要があります。

$1680 / 3! = 1680 / 6 = 280$通りです。

(7) 2組に組分け

9人を2つの組に分ける。組Aに入る人数を$k$人とすると、$k$は1から8の整数値を取ります。

A組の人数が$k$人の時、B組の人数は$9-k$人です。A組の選び方は$_9C_k$通り。ただし、組Aと組Bの区別はないので、2で割る必要がある。

しかし、A組とB組に区別がある場合、$k$が1から8まで動く時の組分けを計算します。

$\sum_{k=1}^{8} {_9C_k} = {_9C_1} + {_9C_2} + ... + {_9C_8}$

二項定理より、$2^9 = \sum_{k=0}^{9} {_9C_k}$であるから、

$\sum_{k=1}^{8} {_9C_k} = 2^9 - {_9C_0} - {_9C_9} = 512 - 1 - 1 = 510$通り。

(8) 文字列の数

sleeperの7文字のうち、eが3つ、l, p, r, s がそれぞれ1つです。

したがって、可能な文字列の数は$\frac{7!}{3!} = \frac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{3 \times 2 \times 1} = 7 \times 6 \times 5 \times 4 = 840$通りです。

(9) 両端にeがない文字列の数

まず、両端にeが来る文字列の数を求めます。

両端にeが来る場合、残りの5文字はe, l, p, r, sです。これらの並べ方は$\frac{5!}{1!} = 120$通りです。

両端にeが少なくとも1つ来る文字列の数を求めます。

1. 左端がeの場合: 左端をeで固定し、残りの6文字を並べる。残りの6文字は、e, e, l, p, r, sなので、並べ方は$\frac{6!}{2!} = 360$通り。

2. 右端がeの場合: 同様に360通り。

3. 両端がeの場合：120通り。

したがって、両端に少なくとも１つeがある文字列は、360 + 360 - 120 = 600通り。

両端にeがない文字列の数は、840 - 600 = 240通りです。

別の考え方：

sleeperの文字で、両端にeが来ないようにするには、両端はl, p, r, sのどれかでなければなりません。

両端の選び方は$4 \times 3 = 12$通り。残りの5文字はe, e, e, 残りの2つです。

3つのeと、l, p, r, s のうち残り２文字の並び順。残りの5つの文字の並び方。

残った５つの場所に入れるのは、e, e, e, 残った2つの文字。

残りの5つ文字は$\frac{5!}{3!} = 20$通り

したがって、両端にeがない文字列は、$12 \times 20 = 240$通りです。

3. 最終的な答え

(1) 45通り

(2) 28通り

(3) 35通り

(4) 9通り

(5) 1680通り

(6) 280通り

(7) 510通り

(8) 840通り

(9) 240通り