2. На рисунке 11 показано дерево. Рассмотрите цепи, соединяющие начальную вершину S с концевыми. Сколько таких цепей имеют длину 2; длину 3; длину 4? а), б).

Длина цепи — это число рёбер от вершины S до концевой вершины.

а) На расстоянии 2 от S находятся 4 концевые вершины: две в левой ветви и две непосредственно под правой вершиной первого уровня. На расстоянии 3 находятся 2 концевые вершины; на расстоянии 4 концевых вершин нет.

б) На расстоянии 2 от S находятся 3 концевые вершины. На расстоянии 3 — 3 концевые вершины: одна в левой ветви и две в правой. На расстоянии 4 — 4 концевые вершины: по две в каждой из этих ветвей.

Ответ: а) длины 2 — 4 цепи, длины 3 — 2 цепи, длины 4 — 0 цепей; б) длины 2 — 3 цепи, длины 3 — 3 цепи, длины 4 — 4 цепи.