На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, К, Л, М, Н, П. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город П, проходящих через город Л?
Для нахождения количества путей из города А в город П, проходящих через город Л, надо найти количество путей из города А в город Л, количество путей из города Л в город П, и перемножить получившиеся числа.
Найдем количество путей из А в Л:
А = 1.
Б = А = 1.
Г = А + Б = 2.
Д = А = 1.
В = Б + Г = 3.
Е = Г + Д = 3.
Ж = В + Г + Е = 8.
К = Ж + В = 11.
Л = Ж + К= 19.
Найдем количество путей из Л в П (при этом Л является исходным пунктом):
Л = 1.
М = Л = 1.
П = Л + М = 2.
Тогда количество путей из А в П, проходящих через Л, равно 19 · 2 = 38.