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

Эта статья о перестановках, элементы которых по очереди возрастают и убывают; о перестановках, в которых элементы по очереди чётны и нечётны см. Меандровая перестановка.

$n$$n$	Чередующиеся перестановки	Обратно чередующиеся перестановки	Количество $A_n$$A_{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 или пилообразная перестановка) — перестановка $a$$a$, такая что её члены по очереди возрастают и убывают, начиная с убывания:

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

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

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

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

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

СимметрииПравить

 

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

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

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

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

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

$2A_{n+1}=\underset{i=0}{\overset{n}{\sum <!--\; \sum \; -->}}(\genfrac{}{}{0ex}{}{n}{i})A_i{A}_{n-<!--\; -\; -->i}$$2A_{n+1}=\sum _{i=0}^{n}{\binom {n}{i}}A_{i}A_{n-i}$ .

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

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

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

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

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

$\frac{A_n}{n!}\simeq <!--\; \simeq \; -->2{\left(\frac{2}{\mathrm{\pi <!--\; \pi \; -->}}\right)}^{n+1}$${\frac {A_{n}}{n!}}\simeq 2\left({\frac {2}{\pi }}\right)^{n+1}$ .

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

Числа ЭнтрингераПравить

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

${}_n\mathrm{╲<!--\; ╲\; -->}{}^k$${}_{n}\!\diagdown \!\!{}^{k}$	1	2	3	4	5	6	7	$A_n$$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) — это числа $A_{n,k}$$A_{n,k}$  чередующихся перестановок $n$$n$  элементов, начинающихся с $k$$k$ . Таким образом,

$A_n=\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}{A}_{n,k}$$A_{n}=\sum _{k=1}^{n}A_{n,k}$ .

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

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

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

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

$A_{n,k}=A_{n,k-<!--\; -\; -->1}+A_{n-<!--\; -\; -->1,n-<!--\; -\; -->k+1}$$A_{n,k}=A_{n,k-1}+A_{n-1,n-k+1}$ 

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