${\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

Чередующаяся перестановка ( перестановка 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 }$ .

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

Симметрии

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

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

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

Разбивая чередующиеся или обратно чередующиеся перестановки по положению элемента ${\displaystyle 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}$ . Из этого можно вывести, что она равна ${\displaystyle A(x)=\mathrm {tg} x+\sec x}$ .

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

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

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

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

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

Число ${\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}}$

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

Примечания