На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П, Р, С, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т, проходящих через город Б?
Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.
При этом, если путь не должен проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город, наоборот, обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.
С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
А = 1.
Б = А = 1.
Г = Б = 1.
В = Б + Г = 2.
Е = Г = 1.
Ж = В + Г + Е = 4.
К = Ж = 4.
Л = Ж + К= 8.
Н = Е + Ж = 5.
М = Л + Ж + Н = 17.
П = К + Л + М = 29.
Р = П + К = 33.
С = П = 29.
Т = Р + С + П = 91.
Примечание. Необходимо найти количество различных путей из города А в город Т, проходящих через город Б.
Ответ: 91.
Примечание.
Количество путей из города А в город Т, проходящих через город Б, равно произведению количества путей из города А до города Б и количества путей из города Б в город Т. Из города А в город Б ведет только один путь. Следовательно, количество путей из города А в город Т, проходящих через город Б, равно количеству путей из города Б в город Т, при этом город А и пути из него, ведущие в другие города, можно не учитывать.