На рисунке представлена схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н. По каждой дороге можно передвигаться только в направлении, указанном стрелкой. Определите количество различных путей, которые начинаются в пункте Н, заканчиваются в пункте А и проходят через любой пункт не более одного раза.
Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.
Посчитаем последовательно количество путей до каждого из городов:
Н = 1.
М = Н = 1.
И = М = 1.
Ж = И = 1.
Е = М + Ж = 2.
Л = М + Е = 3.
К = Л = 3.
Д = К + Л + Е = 8.
А = Д = 8.
Количество различных путей, которые начинаются в пункте Н, заканчиваются в пункте А и проходят через любой пункт не более одного раза равно 8.