Перебор случаев

Пусть на первом месте стоит число Заметим, что если то числа стоят в нашей перестановке в порядке убывания (если двигаться слева направо). Действительно, по условию левее числа должно стоять левее или то есть левее или то есть и т. д. Аналогично при числа стоят в порядке возрастания, так как левее должно быть левее — число и т. д. Следовательно, любая из рассматриваемых перестановок однозначно задаётся набором мест, занимаемых числами (таких мест может вообще не быть, если то есть для перестановки Количество этих наборов равно количеству подмножеств множества из элемента — всех мест, кроме первого, то есть По числу элементов подмножества однозначно определяется число стоящее на первом месте.