В одной из клеток бесконечной клетчатой бумаги находится робот, которому могут быть отданы следующие команды:
• вверх (робот перемещается на соседнюю клетку сверху);
• вниз (робот перемещается на соседнюю клетку снизу);
• влево (робот перемещается на соседнюю клетку слева);
• вправо (робот перемещается на соседнюю клетку справа).
Если, например, робот выполнит последовательность из четырех команд (вверх, вправо, вниз, влево), то он, очевидно, вернется в исходное положение, т.е. окажется в той же клетке, из которой начал движение. Сколько существует всего различных последовательностей из 4 команд, возвращающих робота в исходное положение?
Выбрать какое-нибудь направление и рассмотреть все возможные случаи в зависимости от того, сколько команд на движение именно в эту сторону может быть отдано роботу. А случаев таких будет три.
Для краткости команду влево будем обозначать Л, вправо – П, вверх – В, вниз – Н. Чтобы робот вернулся в исходное положение необходимо и достаточно, чтобы ему было отдано команд Л столько же, сколько и команд П, а команд В – столько же, сколько и Н. Пусть k –количество команд Л в последовательности. Подсчитаем количество искомых последовательностей для k от 0 до 2.
• k=0. Последовательность состоит только из команд В и Н. Так как их поровну, то на 2 местах из 4 должна быть команда В, а на оставшихся двух – Н. Выбрать 2 места из 4 можно способами. Следовательно, ;
• k=1. Каждая из команд Л, П, В, Н встречается в последовательности ровно 1 раз. Число перестановок из 4 элементов равно 4!. Поэтому ;
• k=2. Здесь две Л, две П и нет команд В и Н. Две команды Л можно разместить способами. Значит .
Таким образом, искомое число последовательностей равно .