Условие
Найдите количество перестановок
a
1, a
2, ... , a
10
чисел 1,2,...,10, таких, что
a
i+1 не меньше, чем a
i-1
(для i=1,2,...,9).
Подсказка
Можно закодировать нужные перестановки,
например, таким образом:
каждое a
i, i=1,2,...,9, пометим значком "+",
если a
i+1>a
i, и значком "-",
если a
i+1=a
i-1.
Докажите, что перестановка однозначно восстанавливается по
своему "коду".
Решение
После каждого числа в перестановке, о которой идет речь в условии,
следует либо большее его число, либо на единицу меньшее.
Каждое a
i, i=1,2,...,9, пометим значком "+",
если a
i+1>a
i, и значком "-",
если a
i+1=a
i-1.
Итак, каждой перестановке сопоставлена строка из 9 символов "+"
и "-". Ясно, что количество таких строк равно 2
9=512
(для каждого из 9 символов в строке имеется две возможности
- быть плюсом или минусом).
Осталось теперь показать, что это соответствие взаимно однозначное,
т.е. по строке из плюсов и минусов перестановка восстанавливается
однозначно.
В самом деле, пусть вначале в строке записано n
1
минусов (возможно, n
1=0), а затем стоит плюс,
затем n
2 минусов, затем плюс, и т.д.
Тогда перестановка должна начинаться с группы из n
1+1
чисел, идущих подряд по убыванию, после которых следует новая
группа из n
2+1 чисел, идущих подряд по убыванию, и т.д.
При этом первое число из второй группы должно быть больше
последнего числа из первой группы. Поскольку в первую и вторую группы
входят различные числа, это означает, что каждое из чисел второй группы
больше каждого из чисел первой группы.
Аналогичным образом, каждое из чисел третьей группы
больше каждого из чисел второй группы и т.д.
Приведенные выше рассуждения дают возможность восстановить
перестановку однозначно
(при этом мы пользуемся тем, что каждое из чисел 1,2,...,10
должно встретиться в перестановке); перестановка имеет вид:
n
1+1, n
1, ... , 1, n
1+n
2+2,
n
1+n
2+1, ... , n
1+2, ...
(Числа в перестановке расположены "лесенками" длин
n
1+1, n
2+1, ... идущих подряд по убыванию чисел.)
Ответ
2
9=512.
Источники и прецеденты использования
