Задача
На листе бумаги нанесена сетка изnгоризонтальных иnвертикальных прямых. Сколько различных замкнутых 2n-звенных ломаных можно провести по линиям сетки так, чтобы каждая ломаная проходила по всем горизонтальным и всем вертикальным прямым?
Решение
Зададим на каждой такой ломаной направление обхода. Ясно, что если мы посчитаем количество ориентированных таким образом ломаных, то каждую неориентированную ломаную мы посчитаем дважды. Для каждой ориентированной ломаной занумеруем её стороны по направлению обхода, начиная со стороны, лежащей на крайней слева вертикальной прямой. Тем самым каждая ориентированная ломаная однозначно задается указанием порядка, в котором она проходит поnгоризонтальным прямым и по оставшимся n– 1 вертикальным прямым. Значит, количество ориентированных ломаных – n!(n– 1)!, а неориентированных – в два раза меньше.
Ответ
½ n!(n – 1)!.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь