Пусть 
— количество путей, ведущих из 
в 
— количество путей, ведущих из в 
— количество путей, ведущих из 
в 
Тогда
Очевидно, 
Подсчет количества 
путей из в основывается на следующем правиле. Правило сложения.
Пусть дан ориентированный граф, не содержащий циклов,
и из вершины 
этого графа выходит 
ребра 
которые ведут соответственно в вершины 
и 
Пусть далее из вершины 
в вершину 
ведет 
путей, из вершины в вершину ведет 
путей, из вершины 
в вершину ведет 
путей. Пусть 
— количество путей из вершины в вершину 
Тогда Это правило, естественно, может быть переформулировано для любого
количества ребер, выходящих из данной вершины.
Имея в виду это правило, построим такую таблицу:
 |  |  | |  |  |  |  |  |  |  |  |
| Вершина | |  |  |  |  |  |  |  |  |  | |
| Куда выход |  | | | | |  | |  | |  |  |
| К-во путей | | | | | | | | | | | |
Во второй строке перечислены вершины, в третьей для каждой вершины
указано, куда ведут ребра, выходящие из этой вершины. В четвертой строке
будем записывать количество путей из каждой вершины в вершину 
эти
количества будем вычислять, пользуясь правилом сложения. Из самой вершины
есть ровно один путь в себя — это «пустой путь». Порядок обработки вершин определяется следующим правилом: к моменту
обработки вершины должно быть известно количество путей для всех вершин,
куда из данной вершины ведут ребра. Порядок, в котором вершины указаны в
таблице, этому правилу соответствует. Обратите внимание на то, что вершина должна быть обработана раньше, чем вершина 
Заполняя таблицу слева направо, пользуясь правилом сложения, получим:
| | | | | | | | | | | |
| Вершина | | | | | | | | | | | |
| Куда выход | | | | | | | | | | | |
| К-во путей | | | | | | | | | | |  |
Таким образом, 
По формуле 
