AからBまでの最短経路のうち、PもQも通らない経路は何通りあるか。

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

1. 問題の内容

AからBまでの最短経路のうち、PもQも通らない経路は何通りあるか。

2. 解き方の手順

* AからBまでの最短経路の総数を求める。
AからBまでは、右に6回、下に2回移動する必要がある。したがって、最短経路の総数は、8回の移動のうち右に移動する6回を選ぶ組み合わせの数で計算できる。
\binom{8}{6} = \frac{8!}{6!2!} = \frac{8 \times 7}{2 \times 1} = 28
よって、AからBまでの最短経路は28通りである。
* AからBまでの最短経路のうち、Pを通る経路の数を求める。
AからPまでの最短経路の数は (31)=3\binom{3}{1} = 3通りである。
PからBまでの最短経路の数は (55)=(50)=1\binom{5}{5} = \binom{5}{0} = 1通りである。
したがって、Pを通る最短経路は 3×(55)=3×1=33 \times \binom{5}{5} = 3 \times 1 = 3通りである。
* AからBまでの最短経路のうち、Qを通る経路の数を求める。
AからQまでの最短経路の数は (53)=5!3!2!=5×42×1=10\binom{5}{3} = \frac{5!}{3!2!} = \frac{5 \times 4}{2 \times 1} = 10通りである。
QからBまでの最短経路の数は (33)=1\binom{3}{3} = 1通りである。
したがって、Qを通る最短経路は 10×1=1010 \times 1 = 10通りである。
* AからBまでの最短経路のうち、PとQの両方を通る経路の数を求める。
AからPまでの最短経路の数は (31)=3\binom{3}{1} = 3通りである。
PからQまでの最短経路の数は (22)=1\binom{2}{2} = 1通りである。
QからBまでの最短経路の数は (33)=1\binom{3}{3} = 1通りである。
したがって、PとQの両方を通る最短経路は 3×1×1=33 \times 1 \times 1 = 3通りである。
* PまたはQを通る経路の数を求める。
PまたはQを通る経路の数は、Pを通る経路の数 + Qを通る経路の数 - PとQの両方を通る経路の数で計算できる。
3+103=103 + 10 - 3 = 10通り
* PもQも通らない経路の数を求める。
PもQも通らない経路の数は、AからBまでの最短経路の総数 - PまたはQを通る経路の数で計算できる。
2810=1828 - 10 = 18通り

3. 最終的な答え

18通り

「離散数学」の関連問題

与えられた図形を一筆書きする方法が何通りあるかを求める問題です。図形は、横棒の両端にそれぞれ2つのループと3つのループが繋がった形をしています。

グラフ理論一筆書き組み合わせ
2025/7/4

与えられた6つの文字G, A, K, K, O, Uについて、以下の問題を解きます。 (1) 6つの文字全てを一列に並べる並べ方は何通りあるか。 (2) 6つの文字を辞書式順に並べたとき、100番目の...

順列重複順列辞書式順
2025/7/4

9枚の合同な正方形の木片があり、そのうち5枚が赤色、4枚が青色です。これらの木片を図のように3x3の正方形になるように並べて1枚の板を作ります。 (1) 回転によって一致する配色を同じとみなすとき、板...

組み合わせ群論ポリアの定理Burnsideの補題対称性
2025/7/4

右のような道路がある町において、以下の条件でPからQまで最短経路で行く方法が何通りあるかを求める問題です。 (1) PからQまで行く (2) PからRを通ってQまで行く (3) Pから×印の箇所は通ら...

組み合わせ最短経路場合の数順列
2025/7/3

右図のような道のある町で、最短の道順について、以下の問いに答える問題です。 (1) PからQまで行く道順は何通りあるか。 (2) PからRを通ってQまで行く道順は何通りあるか。 (3) Pから×印の箇...

組み合わせ場合の数最短経路
2025/7/3

(1) 10人がA, Bの2部屋に入る方法は何通りあるか。ただし、全員が1つの部屋に入ってもよい。 (2) 10人が2つのグループA, Bに分かれる方法は何通りあるか。 (3) 10人が2つのグループ...

組み合わせ場合の数二項定理
2025/7/3

SHIKENの6文字を並び替えてできる文字列を、辞書式順序で並べます。EHIKNSを1番目とするとき、以下の問いに答えます。 (1) 140番目の文字列を求めます。 (2) SHIKENは何番目の文字...

順列組み合わせ辞書式順序
2025/7/3

「J.A.P.A.N.E.S.E」の8文字を使ってできる順列について、以下の問いに答える問題です。 (1) 異なる並べ方は何通りあるか。 (2) JはPより左側にあり、かつPはNより左側にあるような並...

順列組み合わせ場合の数重複順列
2025/7/3

集合 $\{1, 2, 3, 4, 5, 6, 7\}$ の部分集合の個数を求めよ。

集合部分集合組み合わせ
2025/7/3

happinessという9文字の文字列について、以下の2つの場合の数を求めます。 (ア) 同じ文字が常に隣り合う並べ方の場合の数 (イ) 'p'は隣り合うが、's'は隣り合わない並べ方の場合の数

順列組み合わせ文字列場合の数
2025/7/3