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

В комбинаторной математике, чередующаяся перестановка (или зигзагообразная перестановка ) набора {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, and
• 3, 4, 1, 2 потому что 3 < 4>1 < 2.

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

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

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

Содержание

• 1 Определения
• 2 Теорема Андре
• 3 Связанные целочисленные последовательности
• 4 Явная формула в терминах чисел Стирлинга второго рода
• 5 См. Также
• 6 Цитаты
• 7 Ссылки
• 8 Внешние ссылки

Определения

A перестановка c1,..., c n называется чередующейся, если ее записи попеременно поднимаются и опускаются. Таким образом, каждая запись, кроме первой и последней, должна быть либо больше, либо меньше, чем оба ее соседа. Некоторые авторы используют термин «чередование» только для обозначения перестановок «вверх-вниз», для которых c 1< c2>c3<..., calling the "down-up" permutations that satisfy c1>c2< c3>... под названием «обратное чередование». Другие авторы меняют это соглашение или используют слово «чередование» для обозначения перестановок «вверх-вниз» и «вниз-вверх».

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

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

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

Определение числа A n чередующихся перестановок множества {1,..., n} называется проблемой Андре. Числа A 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, можно показать, что

$2\; A\; n\; +\; 1\; =\; \sum \; k\; =\; 0\; n\; (nk)\; A\; k\; A\; n\; -\; k\; \{\backslash \; displaystyle\; 2A\_\; \{n\; +\; 1\}\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; \{\backslash \; binom\; \{n\}\; \{k\}\}\; A\_\; \{k\}\; A\_\; \{nk\}\}$

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

$A\; (x)\; =\; \sum \; n\; =\; 0\; \infty \; A\; nxnn!\; \{\backslash \; displaystyle\; A\; (x)\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{\backslash \; infty\}\; A\_\; \{n\}\; \{\backslash \; frac\; \{x\; ^\; \{n\}\}\; \{n!\}\}\}$

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

$2\; \sum \; n\; \ge \; 1\; A\; n\; +\; 1\; x\; n\; +\; 1\; (n\; +\; 1)!\; Знак\; равно\; \sum \; N\; \ge \; 1\; \sum \; К\; знак\; равно\; 0\; N\; А\; К\; К!\; А\; п\; -\; к\; (п\; -\; к)!\; xn\; +\; 1\; n\; +\; 1\; знак\; равно\; \int \; (\sum \; К\; \ge \; 0\; A\; kxkk!)\; (\sum \; j\; \ge \; 0\; A\; jxjj!)\; dx\; -\; x\; \{\backslash \; displaystyle\; 2\; \backslash \; sum\; \_\; \{n\; \backslash \; geq\; 1\}\; A\_\; \{n\; +\; 1\}\; \{\backslash \; гидроразрыв\; \{x\; ^\; \{n\; +\; 1\}\}\; \{(n\; +\; 1)!\}\}\; =\; \backslash \; sum\; \_\; \{n\; \backslash \; geq\; 1\}\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; \{\backslash \; frac\; \{A\_\; \{k\}\}\; \{k!\}\}\; \{\backslash \; frac\; \{A\_\; \{nk\}\}\; \{(nk)!\}\}\; \{\backslash \; frac\; \{x\; ^\; \{n\; +\; 1\}\}\; \{n\; +\; 1\}\}\; =\; \backslash \; int\; \backslash \; left\; (\backslash \; sum\; \_\; \{k\; \backslash \; geq\; 0\}\; A\_\; \{k\}\; \{\backslash \; frac\; \{x\; ^\; \{k\}\}\; \{k!\}\}\; \backslash \; right)\; \backslash \; left\; (\backslash \; sum\; \_\; \{j\; \backslash \; geq\; 0\}\; A\_\; \{j\}\; \{\backslash \; frac\; \{x\; ^\; \{j\; \}\}\; \{j!\}\}\; \backslash \; right)\; \backslash ,\; dx-x\}$

где мы заменяем $j\; =\; n\; -\; k\; \{\backslash \; displaystyle\; j\; =\; nk\}$и $xn\; +\; 1\; n\; +\; 1\; знак\; равно\; \int \; xk\; +\; jdx\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{x\; ^\; \{n\; +\; 1\}\}\; \{n\; +\; 1\}\}\; =\; \backslash \; int\; x\; ^\; \{k\; +\; j\}\; \backslash ,\; dx\}$. Это дает интегральное уравнение

$2\; (A\; (x)\; -\; 1\; -\; x)\; =\; \int \; A\; (x)\; 2\; dx\; -\; x,\; \{\backslash \; displaystyle\; 2\; (A\; (x)\; -1-x)\; =\; \backslash \; int\; A\; (x)\; ^\; \{2\}\; \backslash ,\; dx-x,\}$

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

$A\; (x)\; =\; tan\; \; (\; \pi \; 4\; +\; Икс\; 2)\; знак\; равно\; сек\; \; Икс\; +\; загар\; \; Икс\; \{\backslash \; Displaystyle\; A\; (x)\; =\; \backslash \; загар\; \backslash \; left\; (\{\backslash \; frac\; \{\backslash \; pi\}\; \{4\}\}\; +\; \{\backslash \; frac\; \{x\}\; \{2\}\}\; \backslash \; справа)\; =\; \backslash \; sec\; x\; +\; \backslash \; tan\; x\}$,

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

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

$A\; n\; \sim \; 2\; (2\; \pi )\; n\; +\; 1\; \cdot \; n!.\; \{\backslash \; displaystyle\; A\_\; \{n\}\; \backslash \; sim\; 2\; \backslash \; left\; (\{\backslash \; frac\; \{2\}\; \{\backslash \; pi\}\}\; \backslash \; right)\; ^\; \{n\; +\; 1\}\; \backslash \; cdot\; n!\; \backslash ,.\}$

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

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

$B\; 2\; n\; =\; (-\; 1)\; n\; -\; 1\; 2\; n\; 4\; 2\; n\; -\; 2\; 2\; n\; A\; 2\; n\; -\; 1\; \{\backslash \; displaystyle\; B\_\; \{2n\}\; =\; (-\; 1)\; ^\; \{n\; -1\}\; \{\backslash \; frac\; \{2n\}\; \{4\; ^\; \{2n\}\; -2\; ^\; \{2n\}\}\}\; A\_\; \{2n-1\}\}$

для n>0.

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

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

$E\; (0,\; 0)\; =\; 1\; \{\backslash \; displaystyle\; E\; (0,0)\; =\; 1\}$

$E\; (n,\; 0)\; =\; 0\; for\; n>0\; \{\; \backslash \; displaystyle\; E\; (n,\; 0)\; =\; 0\; \backslash \; qquad\; \{\backslash \; t\_dv\; \{for\}\}\; n>0\}$

$E\; (n,\; k)\; =\; E\; (n,\; k\; -\; 1)\; +\; E\; (n\; -\; 1,\; n\; -\; k)\; \{\backslash \; displaystyle\; E\; (n,\; k)\; =\; E\; (n,\; k-1)\; +\; E\; (n-1,\; nk)\}$.

Зигзагообразное число n равно числу Энтрингера E (n, n).

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

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

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

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

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

$A\; r\; =\; -\; 4\; rar\; \sum \; k\; =\; 1\; r\; (-\; 1)\; k\; S\; (r,\; k)\; k\; +\; 1\; (3\; 4)\; (k)\; \{\backslash \; displaystyle\; A\_\; \{r\}\; =\; -\; \{\backslash \; frac\; \{4\; ^\; \{r\}\}\; \{a\_\; \{r\}\}\}\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{r\}\; \{\backslash \; frac\; \{(-1)\; ^\; \{k\}\; \backslash ,\; S\; (r,\; k)\; \}\; \{k\; +\; 1\}\}\; \backslash \; left\; (\{\backslash \; frac\; \{3\}\; \{4\}\}\; \backslash \; right)\; ^\; \{(k)\}\}$

где

$ar\; =\; \{(-\; 1)\; r\; -\; 1\; 2\; (1\; +\; 2\; -\; r),\; если\; r\; нечетное\; (-\; 1)\; r\; 2,\; если\; r\; четное,\; \{\backslash \; displaystyle\; a\_\; \{r\}\; =\; \{\backslash \; begin\; \{cases\}\; (-\; 1)\; ^\; \{\backslash \; frac\; \{r-1\}\; \{2\}\; \}\; (1\; +\; 2\; ^\; \{-\; r\})\; \{\backslash \; t\_dv\; \{если\; r\; нечетное\}\}\; \backslash \backslash \; (-\; 1)\; ^\; \{\backslash \; frac\; \{r\}\; \{2\}\}\; \{\backslash \; t\_dv\; \{если\; r\; четно\}\}\; \backslash \; end\; \{case\}\},\}$

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

См. Также

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

Citations

Ссылки

• Андре, Дезире (1879), "Développements de séc x et de tang x", 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-е изд.). Cambridge University Press.

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

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