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

${\displaystyle n}$	Чередующиеся перестановки	Обратно чередующиеся перестановки	Количество ${\displaystyle 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] (перестановка down-up; иногда альтернирующая перестановка от англ. alternating permutation или пилообразная перестановка) — перестановка ${\displaystyle a}$, такая что её члены по очереди возрастают и убывают, начиная с убывания:

${\displaystyle a_{1}>a_{2}<a_{3}>a_{4}<\ldots }$.

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

${\displaystyle a_{1}<a_{2}>a_{3}<a_{4}>\ldots }$.

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

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

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

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

${\displaystyle 2A_{n+1}=\sum _{i=0}^{n}{\binom {n}{i}}A_{i}A_{n-i}}$.

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

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

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

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

Ассимптотически последовательность ${\displaystyle A_{n}}$ равна

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

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

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

${\displaystyle {}_{n}\!\diagdown \!\!{}^{k}}$	1	2	3	4	5	6	7	${\displaystyle 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

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

${\displaystyle A_{n}=\sum _{k=1}^{n}A_{n,k}}$.

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

${\displaystyle A_{n+1,n+1}=A_{n}}$,

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

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

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

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