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

В комбинаторной математике , переменная перестановка (или зигзагообразная перестановка ) множества {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 веке. ^[1]

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

Определение числа 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}$ ${\frac {x^{n+1}}{n+1}}=\int x^{k+j}\,dx$

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

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

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

,

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

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

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

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

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

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 могут быть определены рекурсивно следующим образом: ^[3]

E(0,0)=1

E(n,0)=0\qquad {\mbox{for }}n>0

E(n,k)=E(n,k-1)+E(n-1,n-k)

.

Число 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 ).

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

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

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)}

куда

a_{r}={\begin{cases}(-1)^{\frac {r-1}{2}}(1+2^{-r})&{\mbox{if r is odd}}\\(-1)^{\frac {r}{2}}&{\mbox{if r is even}}\end{cases}},

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

Смотрите также

Самая длинная чередующаяся подпоследовательность
Преобразование Бустрофедона
Забор (математика) , частично упорядоченный набор, который имеет чередующиеся перестановки как его линейные расширения

Цитаты

^ Джессика Миллар, NJA Sloane, Нил Э. Янг, "Новая операция по последовательностям: Boustrouphedon Transform" Журнал комбинаторной теории, Серия А76 (1): 44-54 (1996)
^ Стэнли, Ричард П. (2010), «Обзор чередующихся перестановок», Комбинаторика и графики , Современная математика, 531 , Провиденс, Род-Айленд: Американское математическое общество, стр. 165–196, arXiv : 0912.4240 , doi : 10.1090 / conm / 531/10466 , Руководство по ремонту 2757798
^ Weisstein, Eric W. "Энтрингер номер." Материал из MathWorld - веб-ресурса Wolfram. http://mathworld.wolfram.com/EntringerNumber.html
^ Мендес, Энтони (2007). «Заметка о чередующихся перестановках». Американский математический ежемесячник . 114 (5): 437–440. DOI : 10.1080 / 00029890.2007.11920432 . JSTOR 27642223 .
^ Мезо, Иштван; Рамирес, Хосе Л. (2019). «Г-переменные перестановки». Aequationes Mathematicae . DOI : 10.1007 / s00010-019-00658-5 .

использованная литература

Андре, Дезире (1879), «Развитие секций и танцев» , Comptes rendus de l'Académie des Sciences , 88 : 965–967..

Андре, Дезире (1881 г.), «Sur les permutations alternées» (PDF) , Journal de mathématiques pures et appliquées , 3e série, 7 : 167–184^{[ постоянная мертвая ссылка ]} .

Стэнли, Ричард П. (2011). Перечислительная комбинаторика . Vol. I (2-е изд.). Издательство Кембриджского университета . |volume=имеет дополнительный текст ( справка )

внешние ссылки

Вайсштейн, Эрик В. «Альтернативная перестановка» . MathWorld .
Росс Танг, «Явная формула для зигзагообразных чисел Эйлера (числа вверх / вниз) из степенных рядов» Простая явная формула для A _n .
"Обзор чередующихся перестановок" , препринт Ричарда П. Стэнли

[1] Джессика Миллар, NJA Sloane, Нил Э. Янг, "Новая операция по последовательностям: Boustrouphedon Transform" Журнал комбинаторной теории, Серия А76 (1): 44-54 (1996)

[2] Стэнли, Ричард П. (2010), «Обзор чередующихся перестановок», Комбинаторика и графики , Современная математика, 531 , Провиденс, Род-Айленд: Американское математическое общество, стр. 165–196, arXiv : 0912.4240 , doi : 10.1090 / conm / 531/10466 , Руководство по ремонту 2757798

[3] Weisstein, Eric W. "Энтрингер номер." Материал из MathWorld - веб-ресурса Wolfram. http://mathworld.wolfram.com/EntringerNumber.html

[4] Мендес, Энтони (2007). «Заметка о чередующихся перестановках». Американский математический ежемесячник . 114 (5): 437–440. DOI : 10.1080 / 00029890.2007.11920432 . JSTOR 27642223 .

[5] Мезо, Иштван; Рамирес, Хосе Л. (2019). «Г-переменные перестановки». Aequationes Mathematicae . DOI : 10.1007 / s00010-019-00658-5 .

[1]