Альтернативная перестановка - Alternating permutation

В комбинаторной математике , переменная перестановка (или зигзагообразная перестановка ) множества {1, 2, 3, ..., п } является перестановкой (размещение) этих чисел таким образом , что каждая запись попеременно больше или меньше предыдущей записи . Например, пять альтернативных перестановок {1, 2, 3, 4} таковы:

1, 3, 2, 4, потому что 1 <3> 2 <4,
1, 4, 2, 3, потому что 1 <4> 2 <3,
2, 3, 1, 4, потому что 2 <3> 1 <4,
2, 4, 1, 3, потому что 2 <4> 1 <3, и
3, 4, 1, 2, потому что 3 <4> 1 <2.

Этот тип перестановки был впервые изучен Дезире Андре в 19 веке.

Разные авторы используют термин чередующаяся перестановка немного по-разному: некоторые требуют, чтобы вторая запись в чередующейся перестановке была больше первой (как в примерах выше), другие требуют, чтобы чередование было обратным (чтобы вторая запись была меньше чем первый, затем третий больше второго и т. д.), в то время как другие называют оба типа по имени чередующаяся перестановка.

Определение числа A _n чередующихся перестановок множества {1, ..., n } называется проблемой Андре . Числа A _п известны как числа Эйлера , числа зигзагообразных или вверх / вниз чисел . Когда n - четное число, A _n известно как секущее число , а если n нечетно, оно известно как тангенциальное число . Эти последние названия появились в результате изучения производящей функции последовательности.

Определения

Перестановка $с 1, ..., с п$ называется чередованием , если ее элементы попеременно поднимаются и опускаются. Таким образом, каждая запись, кроме первой и последней, должна быть больше или меньше, чем оба ее соседа. Некоторые авторы используют термин чередование только для обозначения перестановок «вверх-вниз», для которых $c 1 < c 2 > c 3 <...$ , называя перестановки «вниз-вверх», удовлетворяющие $c 1 > c 2 < c 3 > ...$ по названию обратное чередование . Другие авторы меняют это соглашение или используют слово «чередование» для обозначения перестановок «вверх-вниз» и «вниз-вверх».

Между перестановками «вниз-вверх» и «вверх-вниз» существует простое взаимно-однозначное соответствие : замена каждой записи $c i$ на $n + 1 - c i$ меняет относительный порядок записей.

По соглашению, в любой схеме именования уникальные перестановки длины 0 (перестановка пустого набора ) и 1 (перестановка, состоящая из единственной записи 1) считаются чередующимися.

Теорема Андре

Определение числа A _n чередующихся перестановок множества {1, ..., n } называется проблемой Андре . Числа А _п по - разному известны как числа Эйлера , зигзагообразные числа , вверх / вниз чисел , или некоторых комбинации этих имен. В частности, имя числа Эйлера иногда используется для обозначения близкой последовательности. Первые несколько значений A _n : 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, ... (последовательность A000111 в OEIS ).

Эти числа удовлетворяют простому повторению, аналогичному повторению каталонских чисел : путем разделения набора чередующихся перестановок (как вниз-вверх, так и вверх-вниз) набора {1, 2, 3, ..., n , n + 1} в соответствии с позицией k самой большой записи $n + 1$ , можно показать, что

{\ displaystyle 2A_ {n + 1} = \ sum _ {k = 0} ^ {n} {\ binom {n} {k}} A_ {k} A_ {nk}}

для всех $n \geq 1$ . Андре (1881) использовал эту рекурсию, чтобы получить дифференциальное уравнение, которому удовлетворяет экспоненциальная производящая функция

{\ displaystyle A (x) = \ sum _ {n = 0} ^ {\ infty} A_ {n} {\ frac {x ^ {n}} {n!}}}

для последовательности $A n$ . Фактически повторение дает:

{\ displaystyle 2 \ sum _ {n \ geq 1} A_ {n + 1} {\ frac {x ^ {n + 1}} {(n + 1)!}} = \ sum _ {n \ geq 1} \ sum _ {k = 0} ^ {n} {\ frac {A_ {k}} {k!}} {\ frac {A_ {nk}} {(nk)!}} {\ frac {x ^ {n +1}} {n + 1}} = \ int \ left (\ sum _ {k \ geq 0} A_ {k} {\ frac {x ^ {k}} {k!}} \ Right) \ left ( \ sum _ {j \ geq 0} A_ {j} {\ frac {x ^ {j}} {j!}} \ right) \, dx-x}

где мы подставляем и . Это дает интегральное уравнение ${\ displaystyle j = nk}$ ${\ displaystyle {\ frac {x ^ {n + 1}} {n + 1}} = \ int x ^ {k + j} \, dx}$

{\ Displaystyle 2 (A (x) -1-x) = \ int A (x) ^ {2} \, dx-x,}

который после дифференцирования становится . Это дифференциальное уравнение можно решить путем разделения переменных (с использованием начального условия ) и упростить, используя формулу касательного полуугла , что дает окончательный результат ${\ displaystyle 2 {\ frac {dA} {dx}} - 2 = A ^ {2} -1}$ ${\ Displaystyle А (0) = А_ {0} / 0! = 1}$

{\ displaystyle A (x) = \ tan \ left ({\ frac {\ pi} {4}} + {\ frac {x} {2}} \ right) = \ sec x + \ tan x}

,

сумма секущих и касательных функций. Этот результат известен как теорема Андре .

Из теоремы Андре следует, что радиус сходимости ряда $A (x)$ равен $π$ / 2. Это позволяет вычислить асимптотическое разложение

{\ displaystyle A_ {n} \ sim 2 \ left ({\ frac {2} {\ pi}} \ right) ^ {n + 1} \ cdot n! \ ,.}

Связанные целочисленные последовательности

Зигзагообразные числа с нечетным индексом (т. Е. Касательные числа) тесно связаны с числами Бернулли . Связь задается формулой

{\ Displaystyle B_ {2n} = (- 1) ^ {n-1} {\ frac {2n} {4 ^ {2n} -2 ^ {2n}}} A_ {2n-1}}

для n > 0.

Если Z _n обозначает количество перестановок {1, ..., n }, которые идут вверх-вниз или вниз-вверх (или и то, и другое, для n <2), то из приведенного выше спаривания следует, что Z _n = 2 A _n для n ≥ 2. Первые несколько значений Z _n : 1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, ... (последовательность A001250 в OEIS ).

Зигзагообразные числа Эйлера связаны с числами Entringer, из которых можно вычислить зигзагообразные числа. Числа Entringer могут быть определены рекурсивно следующим образом:

{\ Displaystyle E (0,0) = 1}

{\ Displaystyle Е (п, 0) = 0 \ qquad {\ mbox {for}} п> 0}

{\ Displaystyle Е (п, к) = Е (п, к-1) + Е (п-1, нк)}

.

Число n- ^го зигзага равно числу Entringer E ( n , n ).

Числа ₂_п с четными индексами называется секущий номер или зиг номер : поскольку секущая функция даже и тангенс нечетно , то из теоремы Андре выше , что они являются Числителями в ряде Маклорены в $сек$ $х$ . Первые несколько значений: 1, 1, 5, 61, 1385, 50521, ... (последовательность A000364 в OEIS ).

Секущие числа связаны со знаковыми числами Эйлера (коэффициентами Тейлора гиперболического секанса) формулой E _{2 n} = (−1) ⁿ A _{2 n} . ( E _n = 0, если n нечетное.)

Соответственно числа A _{2 n +1} с нечетными индексами называются касательными числами или числами zag . Первые несколько значений: 1, 2, 16, 272, 7936, ... (последовательность A000182 в OEIS ).

Явная формула в терминах чисел Стирлинга второго рода

Связь зигзагообразных чисел Эйлера с числами Эйлера и числами Бернулли может быть использована для доказательства следующего

{\ displaystyle A_ {r} = - {\ frac {4 ^ {r}} {a_ {r}}} \ sum _ {k = 1} ^ {r} {\ frac {(-1) ^ {k} \, S (r, k)} {k + 1}} \ left ({\ frac {3} {4}} \ right) ^ {(k)}}

куда

{\ displaystyle a_ {r} = {\ begin {cases} (- 1) ^ {\ frac {r-1} {2}} (1 + 2 ^ {- r}) & {\ mbox {если r нечетное }} \\ (- 1) ^ {\ frac {r} {2}} & {\ mbox {если r четное}} \ end {cases}},}

${\ Displaystyle (х) ^ {(п)} = (х) (х + 1) \ cdots (х + п-1)}$ обозначает возрастающий факториал и обозначает числа Стирлинга второго рода . ${\ Displaystyle S (г, к)}$