Попеременная перестановка

Не путать с чередующейся группой .

В комбинаторной математике попеременная перестановка (или зигзагообразная перестановка ) набора {1, 2, 3,..., n } — это перестановка (расположение) этих чисел так, что каждая запись попеременно больше или меньше предыдущей записи. . Например, пять чередующихся перестановок {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 } называется проблемой Андре . Числа An _, известны как числа Эйлера зигзагообразные числа или числа вверх/вниз . Когда n четно, число An _n называется секущим числом , а если нечетное , оно называется касательным числом . Эти последние названия возникли в результате изучения производящей функции последовательности.

Определения

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

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

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

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

Зигзагообразные числа у Бернулли (1742 г.), Opera Omnia vol. 4, с. 105

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

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

$2A_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}A_{k}A_{n-k}$

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

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

последовательности An _для . Фактически, повторение дает:

$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_{n-k}}{(n-k)!}}{\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$

куда мы подставляем $j=n-k$ и ${\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. Это позволяет вычислить асимптотическое разложение

$A_{n}\sim 2\left({\frac {2}{\pi }}\right)^{n+1}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 An _{равны 1, 1, 2, 4, 10, 32 ,} для n ≥ 2. Первые несколько значений Z _n 122, 544, 2770, 15872, 101042, ... (последовательность A001250 в OEIS ).

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

$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)$.

Затем ​ ^й номер зигзага равен номеру Энтрингера E ( n , n ).

Числа A _{2 n} с четными индексами называются секущими числами или зиг-числами : поскольку секущая функция четная , а тангенс нечетная , из приведенной выше теоремы Андре следует, что они являются числителями ряда Маклорена для sec x . Первые несколько значений — 1, 1, 5, 61, 1385, 50521, ... (последовательность A000364 в OEIS ).

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

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

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

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

$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)$ обозначает числа Стирлинга второго рода .

См. также

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

Ссылки

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

• Андре, Дезире (1881), «О знакопеременных перестановках» (PDF) , Журнал чистой и прикладной математики , 3-я серия, 7 : 167–184, заархивировано из оригинала (PDF) 22 ноября 2021 г.

• Генри, Филипп; Ваннер, Герхард (2019). «Зигзаги с Бюрги, Бернулли, Эйлером и треугольником Зейделя – Энтрингера – Арнольда». Элементы математики . 74 (4): 141–168. дои : 10.4171/EM/393 . .

• Стэнли, Ричард П. (2011). Перечислительная комбинаторика . Том. Я (2-е изд.). Издательство Кембриджского университета .

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

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