図のような経路において、点Pから出発して点Qを通らずに点Rへ行く最短経路は何通りあるかを求める問題です。

離散数学組み合わせ最短経路場合の数
2025/4/30

1. 問題の内容

図のような経路において、点Pから出発して点Qを通らずに点Rへ行く最短経路は何通りあるかを求める問題です。

2. 解き方の手順

まず、点Pから点Rへ行くすべての最短経路を求めます。次に、点Pから点Qを経由して点Rへ行く最短経路を求めます。最後に、すべての最短経路から点Qを経由する最短経路を引くことで、点Qを通らない最短経路の数を求めます。
点Pから点Rへの最短経路は、右に4回、上に3回進む必要があります。したがって、全経路の数は、7回の移動のうち右に進む4回を選ぶ組み合わせで求められ、(74)=7!4!3!=7×6×53×2×1=35 \binom{7}{4} = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35 通りです。
点Pから点Qへの最短経路は、右に2回、上に1回進む必要があります。したがって、経路の数は、(32)=3!2!1!=3 \binom{3}{2} = \frac{3!}{2!1!} = 3 通りです。
点Qから点Rへの最短経路は、右に2回、上に2回進む必要があります。したがって、経路の数は、(42)=4!2!2!=4×32×1=6 \binom{4}{2} = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6 通りです。
点Pから点Qを経由して点Rへ行く最短経路は、点Pから点Qへの経路数と点Qから点Rへの経路数を掛け合わせることで求められます。したがって、3×6=18 3 \times 6 = 18 通りです。
点Pから点Rへのすべての最短経路から点Qを経由する最短経路を引くと、点Qを通らない最短経路の数が得られます。3518=17 35 - 18 = 17 通りです。

3. 最終的な答え

17通り

「離散数学」の関連問題

$A, B, C$ を空集合ではない集合とし、$A$ と $B$ は対等、つまり $A \sim B$ とする。このとき、以下の2つの命題が正しければ証明し、正しくない場合は反例を挙げよ。 (1) $...

集合論ベキ集合差集合対等全単射証明
2025/7/12

10枚のコインがあり、そのうち9枚は同じ重さで、1枚だけが他の9枚よりも軽い。てんびんを使って、軽いコインを3回以内の比較で見つけ出すことができない方法を、選択肢の中から選ぶ。

パズル論理最適化天秤
2025/7/12

9個の異なる玉を、指定された個数でいくつかの組に分ける場合の数を求める問題です。具体的には以下の4つの場合について考えます。 (1) 4個、3個、2個の3つの組に分ける。 (2) A, B, C の3...

組み合わせ場合の数順列
2025/7/12

5x5のマスに1から5の数字を1つずつ入れ、各マスはビルを表します。矢印の数字は、その方向から見たときに見えるビルの数を示します。同じ列(縦、横)に同じ数字は入りません。

パズル論理マス数字
2025/7/12

5x5のマスに1から5の数字を入れます。各行、各列に同じ数字は入りません。マスの外の数字は、その方向から見たときに見えるビルの数を表します。

パズル論理制約充足数独
2025/7/12

5人の人を、A, B, Cの3つのグループに分ける方法は何通りあるかを求める問題です。ただし、各グループに少なくとも1人は属している必要があります。

組み合わせ場合の数グループ分け
2025/7/11

(1) 5人の人を3つの部屋A, B, Cに入れる方法は何通りあるかを求める問題です。ただし、1人も入らない部屋があっても良いものとします。 (2) 5人の人を3つの組A, B, Cに分ける方法は何通...

組み合わせ場合の数重複組み合わせ
2025/7/11

右図のA地点からB地点へ行く最短経路の総数と、P地点を通ってA地点からB地点へ行く最短経路の総数を求める問題です。

組み合わせ最短経路組み合わせ論
2025/7/11

正方形の頂点に1から4までの番号を振る方法は何通りあるか。ただし、回転させて一致するものは同じとみなす。

組み合わせ順列対称性群論
2025/7/11

男子4人と女子5人がいる。女子と女子の間に必ず男子が入るように、男女交互に一列に並べる方法は何通りあるか。

順列組み合わせ場合の数数え上げ
2025/7/11