問題１：文字列 "nobunaga" の8文字を並び替える場合の数と、'u' の左に少なくとも1つの 'a' がある場合の数を求める。 問題２：南北7本、東西6本の道がある街で、C地点を通らずに以下の経路の最短経路の数を求める。 (1) O地点からA地点を経由してP地点へ行く経路数 (2) O地点からB地点を経由してP地点へ行く経路数 (3) O地点からA地点とB地点の両方を経由してP地点へ行く経路数

1. 問題の内容

問題１：文字列 "nobunaga" の8文字を並び替える場合の数と、'u' の左に少なくとも1つの 'a' がある場合の数を求める。

問題２：南北7本、東西6本の道がある街で、C地点を通らずに以下の経路の最短経路の数を求める。

(1) O地点からA地点を経由してP地点へ行く経路数

(2) O地点からB地点を経由してP地点へ行く経路数

(3) O地点からA地点とB地点の両方を経由してP地点へ行く経路数

2. 解き方の手順

問題１：

(ア) "nobunaga" の8文字の並び替えの総数を計算する。8文字のうち、'n' が2つ、'a' が2つ、'o'、'b'、'u'、'g' がそれぞれ1つずつある。したがって、並び替えの総数は、

$8! / (2! * 2!) = (8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) / (2 * 1 * 2 * 1) = 10080$ 通り。

(イ) 'u' の左に少なくとも1つの 'a' がある場合の数を求める。これは、'u' の左に 'a' がない場合を全体の数から引くことで求めることができる。'u' の左に 'a' がないとは、'u' より左に 'a' がないということなので、'u' を一番左に固定し、残りの文字で並び替える。

'u' を一番左に固定した場合、残りの7文字 ("nobnaga") を並び替える。このとき、'n' が2つ、'a' が2つあるので、並び替えの数は $7! / (2! * 2!) = (7 * 6 * 5 * 4 * 3 * 2 * 1) / (2 * 1 * 2 * 1) = 1260$ 通り。

'u' の左に少なくとも1つの 'a' がある場合の数は、全体の並び替えの数から 'u' が一番左にある場合の数を引くことで求められる。

$10080 - 1260 = 8820$ 通り。

問題２：

(1) OからAまでの最短経路数は $\binom{3+2}{2} = \binom{5}{2} = 10$ 通り。AからPまでの最短経路数は $\binom{2+3}{2} = \binom{5}{2} = 10$ 通り。したがって、OからAを経由してPまでの最短経路数は $10 * 10 = 100$ 通り。

(2) OからBまでの最短経路数は $\binom{4+1}{1} = \binom{5}{1} = 5$ 通り。BからPまでの最短経路数は $\binom{1+4}{1} = \binom{5}{1} = 5$ 通り。したがって、OからBを経由してPまでの最短経路数は $5 * 5 = 25$ 通り。

(3) OからAを経由し、Bを経由してPへ行く最短経路数を求める。OからAへの経路数は $\binom{5}{2}=10$。AからBへはCを通れないので、Aから直接Bへ行くことはできない。OからBへの経路数は$\binom{5}{1}=5$。BからPへの経路数は$\binom{5}{1}=5$。A,B両方を通る経路数は，OからAへ行き，AからPへ行く経路数から，OからAに行き，AからBに寄らずPへ行く経路数と，OからBへ行き，BからPへ行く経路数から，OからAに寄らずBからPへ行く経路数を引けばよい。これは難しいので、別のアプローチを取る。

OからAを経由してBを経由してPへ行く場合、OからAへの経路数は10通り、BからPへの経路数は5通り。

OからAを通ってPへ行く経路は$10\times 10 = 100$通り。

OからBを通ってPへ行く経路は$5\times 5 = 25$通り。

OからA,B両方を通ってPへ行く経路は、OからAへ行きAからBへ行きBからPへ行く経路の数と、OからBへ行きBからAへ行きAからPへ行く経路の数の和。しかし、この経路は最短経路になるとは限らないので、別の考え方が必要。

AとBの両方を通る最短経路は、OからAへ行って、AからBへ行って、BからPへ行くか、OからBへ行って、BからAへ行って、AからPへ行くかのいずれかである。AからBへ行くにはCを通れないので、東に1つ、南に1つ進む方法では到達できない。従って，A,B両方を通る最短経路は存在しない．0通り。

3. 最終的な答え

問題１：

(ア) 10080 通り

(イ) 8820 通り

問題２：

(1) 100 通り

(2) 25 通り

(3) 0 通り