Русская Википедия:Чередующаяся перестановка
| <math>n</math> | Чередующиеся перестановки | Обратно чередующиеся перестановки | Количество <math>A_n</math> |
|---|---|---|---|
| 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; иногда альтернирующая перестановка от Шаблон:Lang-en или пилообразная перестановка) — перестановка <math>a</math>, такая что её члены по очереди возрастают и убывают, начиная с убывания:
- <math>a_1 > a_2 < a_3 > a_4 < \ldots</math>.
Обратно чередующаяся перестановка (перестановка up-down) <math>a</math> — такая, что её члены по очереди возрастают и убывают, начиная с возрастания:
- <math>a_1 < a_2 > a_3 < a_4 > \ldots</math>.
Иногда условие того, начинается ли чередование с возрастания или убывания, опускают, и оба варианта называют чередующимися перестановками без уточнения.
Симметрии
Чередующиеся перестановки могут быть изображены геометрически как пилообразная кривая (см. рисунок справа). На них существует два биективных отображения — отражение относительно горизонтали или вертикали. При этом горизонтальное отражение переводит чередующиеся в чередующиеся для нечётной длины и в обратно чередующиеся для чётной, а вертикальное — всегда в обратно чередующиеся. В частности, число чередующихся и число обратно чередующихся перестановок на одном количестве элементов одинаково[2].
Количество перестановок
Числа <math>A_n</math> чередующихся перестановок на <math>n</math> элементах образуют последовательность, начинающуюся c 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, …, см. Шаблон:OEIS.
Разбивая чередующиеся или обратно чередующиеся перестановки по положению элемента <math>1</math>, можно показать, что эта последовательность удовлетворяет рекуррентному соотношению[1]
- <math>2A_{n+1} = \sum_{i=0}^n \binom{n}{i} A_{i} A_{n-i}</math>.
Таким образом, экспоненциальная производящая функция <math>A(x)=\sum_{n \ge 0} A_n x^n/n!</math> этой последовательности удовлетворяет дифференциальному уравнению
- <math>2A'(x) = 1 + (A(x))^2</math>
с начальным условием <math>A(0)=1</math>[3]. Из этого можно вывести, что она равна <math>A(x)=\mathrm{tg} x + \sec x</math>[1].
Секанс чётен, а тангенс — нечётен, поэтому чётные члены последовательности совпадают с коэффициентами в ряде Тейлора секанса, а нечётные — тангенса, а потому выражаются через числа Бернулли и числа Эйлера соответственно, см. подробности в Тригонометрические функции#Определение тригонометрических функций через ряды.
Ассимптотически последовательность <math>A_n</math> равна
- <math>\frac{A_n}{n!} \simeq 2 \left( \frac{2}{\pi} \right)^{n+1}</math>.
Число справа примерно равно вероятности того, что перестановка чередующаяся[4].
Числа Энтрингера
| <math>{}_{n} \! \diagdown \!\! {}^{k}</math> | 1 | 2 | 3 | 4 | 5 | 6 | 7 | <math>A_n</math> |
| 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) — это числа <math>A_{n,k}</math> чередующихся перестановок <math>n</math> элементов, начинающихся с <math>k</math>. Таким образом,
- <math>A_n = \sum_{k=1}^{n} A_{n,k}</math>.
Кроме того, поскольку к любой обратно чередующейся последовательности можно прибавить в начале <math>(n+1)</math>, и получить чередующуюся последовательность,
- <math>A_{n+1, n+1} = A_n</math>,
а потому числа чередующихся последовательностей — частный случай чисел Энтрингера.
Числа Энтрингена удовлетворяют рекуррентному соотношению
- <math>A_{n,k} = A_{n,k-1} + A_{n-1,n-k+1}</math>
и потому образуют треугольник наподобие треугольника Паскаля (см. справа). Последовательность, получающаяся при его построчном перечислении с пропуском нулей, — это Шаблон:OEIS[5].
Примечания
