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