На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П, Р, С. По каждой дороге можно передвигаться только в направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт С, проходящих через пункт Е и при этом не проходящих через пункт М?
Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.
При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.
С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:
А = 1
Г = А = 1
В = А + Г = 2
Б = А + В = 3
Е = Б + В + Г = 6
Л = Е = 6
И = Е = 6
Ж = Е + Л + И = 18
К = Л + Ж = 24
Н = И = 6
П = К = 24
Р = Н = 6
С = К + П + Р = 54
Примечание. Необходимо найти количество различных путей из города А в город С, проходящих через город Е и не проходящих через пункт М.
Ответ: 54.
Приведем другое решение.
Количество путей из города А в город С, проходящих через город М, равно произведению количества путей из города А в город Е и количества путей из города Е в город С, при этом по условию путь из города Е в город С не должен проходить через город М.
Найдем количество путей из города А в город Е:
А = 1
Г = А = 1
В = А + Г = 2
Б = А + В = 3
Е = Б + В + Г = 6
Найдем количество путей из города Е в город С, которые не проходят через город М (при этом Е — исходный пункт):
Е = 1
Л = Е = 1
И = Е = 1
Ж = Е + Л + И =3
К = Л + Ж = 4
Н = И = 1
П = К = 4
Р = Н = 1
С = К + П + Р = 9
Следовательно, количество путей из города А в город С, не проходящих через город М, равно 6 · 9 = 54.