Чередующиеся перестановки Обратно чередующиеся перестановки Количество 2 (2,1) (1,2) 2 3 (2,1,3), (3,1,2) (1,3,2), (2,3,1) 4 4 (2,1,4,3),(3,1,4,2),(3,2,4,1),(4,1,3,2),(4,2,3,1) (1,3,2,4), (1,4,2,3),(2,3,1,4),(2,4,1,3),(3,4,1,2) 10
Чередующаяся перестановка (перестановка down-up; иногда альтернирующая перестановка от или пилообразная перестановка) — перестановка , такая что её члены по очереди возрастают и убывают, начиная с убывания: .
Обратно чередующаяся перестановка (перестановка up-down) — такая, что её члены по очереди возрастают и убывают, начиная с возрастания: .
Иногда условие того, начинается ли чередование с возрастания или убывания, опускают, и оба варианта называют чередующимися перестановками без уточнения.
Симметрии
Чередующиеся перестановки могут быть изображены геометрически как пилообразная кривая (см. рисунок справа). На них существует два биективных отображения — отражение относительно горизонтали или вертикали (см. рисунок слева). При этом горизонтальное отражение не изменяет порядок чередования (с прямого на обратный или наоборот) для нечётной длины, и изменяет для чётной, а вертикальное — всегда изменяет порядок чередования. В частности, число чередующихся и число обратно чередующихся перестановок на одном количестве элементов одинаково.
Количество перестановок Числа чередующихся перестановок на элементах образуют последовательность, начинающуюся c 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, …, см. .
Разбивая чередующиеся или обратно чередующиеся перестановки по положению элемента , можно показать, что эта последовательность удовлетворяет рекуррентному соотношению .
Таким образом, экспоненциальная производящая функция этой последовательности удовлетворяет дифференциальному уравнению
с начальным условием . Из этого можно вывести, что она равна .
Секанс чётен, а тангенс — нечётен, поэтому чётные члены последовательности совпадают с коэффициентами в ряде Тейлора секанса, а нечётные — тангенса, а потому выражаются через числа Бернулли и числа Эйлера соответственно, см. подробности в Тригонометрические функции#Определение тригонометрических функций через ряды.
Ассимптотически последовательность равна . Число справа примерно равно вероятности того, что перестановка чередующаяся.
Числа Энтрингера + Число чередующихся перестановок элементов, начинающихся с 1 2 3 4 5 6 7 2 0 1 1 3 0 1 1 2 4 0 1 2 2 5 5 0 2 4 5 5 16 6 0 5 10 14 16 16 61 7 0 16 32 46 56 61 61 272 Числа Энтрингера () — это числа чередующихся перестановок элементов, начинающихся с . Таким образом, . Кроме того, поскольку к любой обратно чередующейся последовательности можно прибавить в начале , и получить чередующуюся последовательность, , а потому числа чередующихся последовательностей — частный случай чисел Энтрингера.
Числа Энтрингена удовлетворяют рекуррентному соотношению
и потому образуют треугольник наподобие треугольника Паскаля (см. справа). Последовательность, получающаяся при его построчном перечислении с пропуском нулей, — это .
Примечания
Категория:Перестановки Категория:Перечислительная комбинаторика