道順を求める順列

質問

順列がとても苦手です。
なんとか教科書や参考書をみて解いているのですが、
それでも良く解らない問題があったので質問させていただきます。

縦に6つ、横に5つの道路があります。（長方形のようになっていて、中に縦と横がひいてある感じです)
1番左の道路の1番上のところをA、
左から2番目の道路の上から2番目をP、
右から3番目の道路の下から2番目をQ、
1番右の道路の1番下のところをBとします。
AからPまたはQを通りBに行く最短の道順はいくつあるでしょう。

説明が下手でとても解りにくいかと思います・・・。すみません；

AからBに行く最短の道順の求め方はわかります。
縦の線をn、横の線をeなどとおいてと
nは4本、横は5本で

9!/4!5!

として解くことはできます。

ですが、上記に記載した問題はどうしても解けません。
AからPの道順を求め、PからBの道順を求め・・・など
色々とやってみたのですが解けませんでした。

大変わかりにくい質問のしかただとは思っているのですが、
どなたか教えてくださるととても助かります；
考え方、アドバイスなどなんでも結構ですのでどうかよろしくおねがいします。

回答No.1

pocopeco · ベストアンサー

まずは最短ルートのパターンを考えましょう。
1）P、Q両方通るパターン
2）Pだけ通り、Qは通らないパターン
3）Qだけ通り、Pは通らないパターン
4）PもQも通らないパターン
1）は簡単ですが、2～4は難しいですね。タイプ分け失敗。

次は、
1）P、Q通るパターン
2）Pを通るパターン
3）Qを通るパターン
4）その他

ここで、今、注目すべきものは、PまたはQを通るパターン。
つまり、Pだけ通る場合、Qだけ通る場合、P、Q両方通る場合です。

でも、Pだけ、Qだけというパターンを考えるのは難しいので、
Pだけ通る場合とは、（Pを通る）－（PQ両方）
Qだけ通る場合とは、（Qを通る）－（PQ両方）

(Pだけ)＋(Qだけ)+(両方)
＝｛（Pを通る）－（PQ両方）｝＋｛（Qを通る）－（PQ両方）｝＋（PQ両方）

お礼

パターンわけをしていくと良いのですね。
私の場合PとQ両方通るパターンを忘れて計算していました；
細かく説明したくださりありがとうございました。
とてもわかりやすかったです。

回答No.4

kumipapa

解法は皆さんのアドバイスにお任せするとして・・・。
「色々とやってみた」のであれば、それを具体的に示してみればいかが？途中で断念したならば、その途中までを。

他の方々の解法を参考にされることも大切ですが、自分の考えのどこに誤りがあったのかを知ることも時として大切ですし、また、それが分らないままでは気持ちが悪くないですか？

お礼

ご指摘ありがとうございます。
kumipapaさんのおっしゃることは正しいと思います。
私も自分の計算を途中まで書けばよかったかと思っております。
そうしたらもっと私がどこを解っていないのか皆さんに伝わりますね；

私はここで質問するとき、皆さんのアドバイスや解法を読みながら
自分が紙に書いた計算を見比べて間違っている場所を調べたりしていました。
参考にしながらも一応自分の誤りも探すようにしています。

今後は少しでも自分の考えを書いてから質問するよう気をつけたいと思います；
ありがとうございました。

回答No.3

ujitaka

次の３つの場合を計算すればいいと思います。
(1)A→P→B（AからPを通りBへ行く）
(2)A→Q→B（AからQを通りBへ行く）
(3)A→P→Q→B（AからP、Qを通りBへ行く）
この場合をそれぞれ計算し、
(1)＋(2)－(3)を計算する。（(3)はダブって数えてしまって部分を引いています）

お礼

とっても解りやすく説明してくださり、
ありがとうございました。
A→P→Q→Bの場合を計算していませんでした；
(3)の場合を引いたら無事に解くことができました。
ありがとうございました。

回答No.2

Quattro99

そのやり方でよいのでは？

AからPを通ってBに行く最短の道順は、(AからPへ行く最短の道順)*(PからBへ行く最短の道順)です。
同様にAからQを通ってBへ行く最短の道順も同様に求まります。
しかし、これらを足すとAからP、Qの両方を通ってBへ行く最短の道順をだぶって数えていることになりますから、それを引きます。
それは(AからPへ行く最短の道順)*(PからQへ行く最短の道順)*(QからBへ行く最短の道順)です。

お礼

やり方の基本はあっていたのですか。
PとQ両方を通っていく道順を引いていなかったみたいです；
参考意見ありがとうございました。