Улитка должна проползти вдоль линий клетчатой бумаги путь длины 2n, начав и кончив свой путь в данном узле. Сколько возможных различных маршрутов у улитки?
Эта задача была давным-давно на Московской математической олимпиаде. А ко мне впервые попала из какого-то листка по комбинаторике. И решил я тогда её не так красиво, как написано ниже.
Ответ: ((2n)!/n!^2)^2=C(2n,n)^2.
Здесь C(m,k) - количество способов выбрать k предметов из m различных предметов.
Решение. При любом таком маршруте число ходов вверх равно числу ходов вниз, а число ходов вправо равно числу ходов влево. Выпишем на один лист бумаги номера ходов, ведущих вправо или вверх, а на другой — номера ходов, ведущих влево или вверх. На каждом листе будет выписано ровно n номеров. По каждой паре таких наборов маршрут однозначно восстанавливается (например, если номер входит в оба набора, то ему соответствует ход вверх). Этот маршрут замкнутый, поскольку число ходов вправо равно числу ходов влево. (оба они дополняют число ходов вверх до n), а число ходов вверх равно числу ходов вниз (вычитая из общего числа 2n ходов число ходов вправо, влево и вверх, мы, с одной стороны, получим число ходов вниз, а с другой стороны, — число ходов вверх). Итак, число маршрутов равно числу пар наборов из n номеров.
