Задача 001 — Задачи на Графы

В стране $n \geq 2$ городов, каждые два из которых соединены прямым автобусным сообщением в обе стороны. Сколькими способами можно попасть из города $A$ в другой город $B$ , проехав на автобусе ровно $k$ раз? Маршрут может проходить через любой город (в том числе $A$ и $B$ ), а также использовать любой рейс между городами более одного раза.

Подсказка

Попробуйте доказать по индукции.

Решение

Ответ: $\frac{(n-1)^{k}-(-1)^{k}}{n}$ .

Обозначим через $a_{k}$ количество маршрутов длины $k$ из $A$ в $B$ . Выедем из города $A$ и будем ехать каждый раз в произвольный город. На каждом шаге у нас будет ровно $n-1$ вариант, поэтому всего маршрутов длины $k-1$ выходящих из $A$ , будет ровно $(n-1)^{k-1}$ . Заметим, что каждый такой маршрут либо заканчивается в городе $B$ , либо можно сделать еще один ход в $B$ . Поэтому $(n-1)^{k-1}=a_{k}+a_{k-1}(*)$ . Теперь искомую формулу можно доказать методом математической индукции: базой является $a_{1}=1$ , а переход следует из формулы (*).