Олимпиадная задача: Перестановки чисел с соседними значениями — 8-10 класс, комбинаторика

Пусть на первом месте стоит число k. Заметим, что если  k > 1,  то числа  k – 1,  k – 2, ..., 1  стоят в нашей перестановке в порядке убывания (если двигаться слева направо). Действительно, по условию левее числа 1 должно стоять 2, левее 2 – 1 или 3, то есть 3,  левее 3 – 2 или 4, то есть 4 и т. д. Аналогично, при  k < N  числа  k + 1,  k + 2,  ...,  N  стоят в порядке возрастания, так как левее N должно быть  N – 1,  левее  N – 1  – число  N – 2  и т. д. Следовательно, любая из рассматриваемых перестановок однозначно задаётся набором мест, занимаемых числами  1, 2, ...,  k – 1  (таких мест может вообще не быть, если  k = 1,  то есть для перестановки  1, 2, ..., N).  Количество этих наборов равно количеству подмножеств множества из  N – 1  элемента – всех мест, кроме первого, то есть 2^N–1. По числу элементов подмножества однозначно определяется число k, стоящее на первом месте.