Количество различных путей из A в G

Будем считать количество путей, заканчивающихся в каждой вершине. Вершина G достигается из D, E и F.

1. В D ведёт один путь: A → D.
2. В C ведут два пути: A → C и A → D → C.
3. В B ведёт один путь: A → B.
4. В E ведут пять путей: напрямую из A, через D, через C (два пути до C) и через B. Итого 1 + 1 + 2 + 1 = 5.
5. В F ведут шесть путей: через B (один путь) и через E (пять путей). Итого 1 + 5 = 6.
6. В G ведут пути через D, E и F: 1 + 5 + 6 = 12.

Ответ: 12 путей.