5. На рисунке изображена решётка 4 × 4. а) Сколько в этом графе кратчайших путей из вершины A в вершину B? б) Сколько из них проходит через точку D?

Каждый кратчайший путь из A в B состоит из 4 шагов вправо и 4 шагов вверх.

а) Нужно выбрать, на каких 4 из 8 шагов идти вправо:

\(\binom{8}{4}=70\).

б) Точка D находится на расстоянии 2 шагов вправо и 2 шагов вверх от A. Число кратчайших путей из A в D равно \(\binom{4}{2}=6\). От D до B также нужно сделать 2 шага вправо и 2 шага вверх, поэтому таких путей тоже 6.

По правилу умножения число кратчайших путей через D равно \(6\cdot6=36\).

Ответ: а) 70 путей; б) 36 путей.