Чередующаяся перестановка

$n$	Чередующиеся перестановки	Обратно чередующиеся перестановки	Количество $2A_n$
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

Геометрическое изображение всех чередующихся перестановок пяти элементов. Перестановки лексикографически упорядочены — от (1,3,2,5,4) (сверху слева) до (4,5,2,3,1) (снизу справа).

Чередующаяся перестановка (перестановка down-up; иногда альтернирующая перестановка от Шаблон:Lang-en или пилообразная перестановка) — перестановка $a$, такая что её члены по очереди возрастают и убывают, начиная с убывания:

$a_1>a_2<a_3>a_4<\dots$.

Обратно чередующаяся перестановка (перестановка up-down) $a$ — такая, что её члены по очереди возрастают и убывают, начиная с возрастания:

$a_1<a_2>a_3<a_4>\dots$.

Иногда условие того, начинается ли чередование с возрастания или убывания, опускают, и оба варианта называют чередующимися перестановками без уточнения.

Симметрии

Горизонтальное и вертикальное отражения чередующихся (красных) и обратно чередующихся (синих) перестановок.

Чередующиеся перестановки могут быть изображены геометрически как пилообразная кривая (см. рисунок справа). На них существует два биективных отображения — отражение относительно горизонтали или вертикали (см. рисунок слева). При этом горизонтальное отражение не изменяет порядок чередования (с прямого на обратный или наоборот) для нечётной длины, и изменяет для чётной, а вертикальное — всегда изменяет порядок чередования. В частности, число чередующихся и число обратно чередующихся перестановок на одном количестве элементов одинаково.

Количество перестановок

Числа $A_n$ чередующихся перестановок на $n$ элементах образуют последовательность, начинающуюся c 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, …, см. Шаблон:OEIS.

Разбивая чередующиеся или обратно чередующиеся перестановки по положению элемента $1$, можно показать, что эта последовательность удовлетворяет рекуррентному соотношению

$2A_{n+1}=\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})A_i{A}_{n-i}$.

Таким образом, экспоненциальная производящая функция $A(x)=\sum _{n\ge 0}{A}_n{x}^n/n!$ этой последовательности удовлетворяет дифференциальному уравнению

$2A^{\prime }(x)=1+(A(x){)}^2$

с начальным условием $A(0)=1$. Из этого можно вывести, что она равна $A(x)=\mathrm{t}\mathrm{g}x+\sec x$.

Секанс чётен, а тангенс — нечётен, поэтому чётные члены последовательности совпадают с коэффициентами в ряде Тейлора секанса, а нечётные — тангенса, а потому выражаются через числа Бернулли и числа Эйлера соответственно, см. подробности в Тригонометрические функции#Определение тригонометрических функций через ряды.

Ассимптотически последовательность $A_n$ равна

$\frac{A_n}{n!}\simeq 2{\left(\frac{2}{\pi }\right)}^{n+1}$.

Число справа примерно равно вероятности того, что перестановка чередующаяся.

Числа Энтрингера

Число $A_{n,k}$ чередующихся перестановок $n$ элементов, начинающихся с $k$

${}_n╲{}^k$	1	2	3	4	5	6	7	$A_n$
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

Числа Энтрингера (Шаблон:Lang-en) — это числа $A_{n,k}$ чередующихся перестановок $n$ элементов, начинающихся с $k$. Таким образом,

$A_n=\sum _{k=1}^n{A}_{n,k}$.

Кроме того, поскольку к любой обратно чередующейся последовательности можно прибавить в начале $(n+1)$, и получить чередующуюся последовательность,

$A_{n+1,n+1}=A_n$,

а потому числа чередующихся последовательностей — частный случай чисел Энтрингера.

Числа Энтрингена удовлетворяют рекуррентному соотношению

$A_{n,k}=A_{n,k-1}+A_{n-1,n-k+1}$

и потому образуют треугольник наподобие треугольника Паскаля (см. справа). Последовательность, получающаяся при его построчном перечислении с пропуском нулей, — это Шаблон:OEIS.