Олимпиадная задача: Перестановки чисел с соседними значениями — 8-10 класс, комбинаторика
Задача
Числа 1, 2, 3, ..., N записываются в строчку в таком порядке, что если где-то (не на первом месте) записано число i, то где-то слева от него встретится хотя бы одно из чисел i + 1 и i – 1. Сколькими способами это можно сделать?
Решение
Пусть на первом месте стоит число 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 элемента – всех мест, кроме первого, то есть 2N–1. По числу элементов подмножества однозначно определяется число k, стоящее на первом месте.
Ответ
2N–1 способами.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь