この問題は、同じものを含む順列と、最短経路の数を求める問題です。 問題1は、文字列 "nobunaga" の文字を並び替える場合の数と、そのうち 'u' の左に少なくとも1つの 'a' がある場合の数を求めます。 問題2は、与えられた道路網において、指定された地点を経由して、ある地点から別の地点へ最短距離で移動する方法の数を求めます。

1. 問題の内容

この問題は、同じものを含む順列と、最短経路の数を求める問題です。

問題1は、文字列 "nobunaga" の文字を並び替える場合の数と、そのうち 'u' の左に少なくとも1つの 'a' がある場合の数を求めます。

問題2は、与えられた道路網において、指定された地点を経由して、ある地点から別の地点へ最短距離で移動する方法の数を求めます。

2. 解き方の手順

問題1

(ア) "nobunaga"の8文字を並び替える総数を求める。

"n", "o", "b", "u", "g" はそれぞれ1つずつ、"a" は3つである。

したがって、並べ方の総数は、

$\frac{8!}{3!} = \frac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{3 \times 2 \times 1} = 8 \times 7 \times 6 \times 5 \times 4 = 6720$

(イ) 'u' の左に 'a' が少なくとも1つある並べ方を求める。

まず、'u' の左に 'a' がない場合 (つまり 'u' が一番左にある場合) を考え、総数から引く。

'u' を一番左に固定すると、残りの7文字 ("n", "o", "b", "n", "a", "g", "a", "a")を並び替えることになる。

並べ方は、

$\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$

したがって、求める並べ方は、全体の並べ方から 'u' が一番左にある場合を引けば良い。

$6720 - 840 = 5880$

問題2

(1) O地点からA地点まで最短で行く方法は、右に1回、上に2回移動する必要があるため、

$\frac{3!}{1!2!} = \frac{3 \times 2 \times 1}{1 \times 2 \times 1} = 3$ 通り

A地点からP地点まで最短で行く方法は、右に4回、上に3回移動する必要があるため、

$\frac{7!}{4!3!} = \frac{7 \times 6 \times 5 \times 4!}{4! \times 3 \times 2 \times 1} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 7 \times 5 = 35$ 通り

O地点からA地点を通りP地点まで最短で行く方法は、それぞれの移動方法の積になるので、

$3 \times 35 = 105$ 通り

(2) O地点からB地点まで最短で行く方法は、右に3回、上に4回移動する必要があるため、

$\frac{7!}{3!4!} = \frac{7 \times 6 \times 5 \times 4!}{3 \times 2 \times 1 \times 4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 7 \times 5 = 35$ 通り

B地点からP地点まで最短で行く方法は、右に2回、上に1回移動する必要があるため、

$\frac{3!}{2!1!} = \frac{3 \times 2 \times 1}{2 \times 1 \times 1} = 3$ 通り

O地点からB地点を通りP地点まで最短で行く方法は、それぞれの移動方法の積になるので、

$35 \times 3 = 105$ 通り

(3) O地点からA地点を通ってB地点を通ってP地点に行く最短経路は、A地点からB地点に到達することができないため、0通りとなる。最短経路はA,Bを同時に通ることは出来ない。

もし仮にAとBのどちらも経由する必要があるという条件を、同じ道を何度通っても良いという条件で緩和すると話が変わってきます。しかし、問題文が意図するところはA,B両方を最短経路で通ることはできない、と解釈できる。

3. 最終的な答え

問題1

(ア) 6720通り

(イ) 5880通り

問題2

(1) 105通り

(2) 105通り

(3) 0通り