Преобразование бустрофедона

В математике — преобразование бустрофедона это процедура, которая отображает одну последовательность в другую. вычисляется с помощью операции «сложения», реализованной так, как если бы треугольный массив заполнялся бустрофедоном Преобразованная последовательность ( зигзагообразным или змеевидным) способом — в отличие от метода «растрового сканирования» пилообразного .

Определение

Преобразование бустрофедона — это числовое преобразование, генерирующее последовательность, которое определяется бинарной операцией, такой как сложение .

В общем, учитывая последовательность: $(a_{0},a_{1},a_{2},\ldots )$ , преобразование бустрофедона дает другую последовательность: $(b_{0},b_{1},b_{2},\ldots )$ , где $b_{0}$ вероятно определяется эквивалентно $a_{0}$ . Саму трансформацию можно визуализировать (или представить) как построенную, заполнив треугольник, как показано на рисунке 1 .

Бустрофедон Треугольник

Чтобы заполнить числовой равнобедренный треугольник ( рис. 1 ), вы начинаете с входной последовательности: $(a_{0},a_{1},a_{2},\ldots )$ и поместите одно значение (из входной последовательности) в каждую строку, используя подход сканирования бустрофедона ( зигзагообразный или змеевидный ).

Верхняя вершина треугольника будет входным значением. $a_{0}$ , эквивалент выходного значения $b_{0}$ , и мы нумеруем эту верхнюю строку как строку 0.

Последующие строки (спускаясь к основанию треугольника) нумеруются последовательно (от 0) целыми числами — пусть $k$ обозначают номер строки, заполняемой в данный момент. Эти строки строятся в соответствии с номером строки ( $k$ ) следующее:

Для всех строк, пронумерованных $k\in \mathbb {N}$ , будет именно $(k+1)$ значения в строке.
Если $k$ $k$ нечетно, то поставьте значение $a_{k}$ $a_{k}$ в правом конце ряда.
- Заполните внутреннюю часть этой строки справа налево, где каждое значение (индекс: $(k,j)$ ) является результатом «сложения» между значениями справа (индекс: $(k,j+1)$ ) и значение в правом верхнем углу (индекс: $(k-1,j+1)$ ).
- Выходное значение $b_{k}$ будет в левом конце нечетной строки (где $k$ это странно ).
Если $k$ $k$ четно, затем поместите входное значение $a_{k}$ $a_{k}$ в левом конце ряда.
- Заполните внутреннюю часть этой строки слева направо, где каждое значение (индекс: $(k,j)$ ) является результатом «сложения» между значением слева от него (индекс: $(k,j-1)$ ) и значение в левом верхнем углу (индекс: $(k-1,j-1)$ ).
- Выходное значение $b_{k}$ будет в правом конце четной строки (где $k$ четный ) .

Обратитесь к стрелкам на рисунке 1 для визуального представления этих операций «сложения».

Для данной конечной входной последовательности: $(a_{0},a_{1},...a_{N})$ , из $N$ значения, будет ровно $N$ ряды в треугольнике такие, что $k$ целое число в диапазоне: $[0,N)$ (эксклюзив). Другими словами, последняя строка $k=N-1$ .

Рекуррентное отношение

Более формальное определение использует рекуррентное отношение . Определите цифры $T_{k,n}$ (при k ≥ n ≥ 0) на

T_{k,0}=a_{k}

T_{k,n}=T_{k,n-1}+T_{k-1,k-n}

{\text{with }}

\quad k,n\in \mathbb {N}

\quad k\geq n>0

.

Тогда преобразованная последовательность определяется формулой $b_{n}=T_{n,n}$ (для $T_{2,2}$ и более высокие показатели).

В соответствии с этим определением обратите внимание на следующие определения значений, выходящих за пределы ограничений (из приведенных выше отношений) на $(k,n)$ пары:

${\begin{aligned}T_{0,0}\,{\overset {\Delta }{=}}&\,a_{0}\,{\overset {\Delta }{=}}\,b_{0}\\\\T_{k,0}\,{\overset {\Delta }{=}}&\,a_{k}\,\iff k\,{\text{is even}}\\T_{k,0}\,{\overset {\Delta }{=}}&\,b_{k}\,\iff k\,{\text{is odd}}\\\\T_{0,k}\,{\overset {\Delta }{=}}&\,b_{k}\,\iff k\,{\text{is even}}\\T_{0,k}\,{\overset {\Delta }{=}}&\,a_{k}\,\iff k\,{\text{is odd}}\\\end{aligned}}$

Особые случаи

В случае a ₀ = 1, a _n = 0 ( n > 0) получившийся треугольник называется треугольником Зейделя – Энтрингера – Арнольда. ^[1] и цифры $T_{k,n}$ называются номерами Entringer (последовательность A008281 в OEIS ).

В этом случае числа в преобразованной последовательности b _n называются числами Эйлера вверх/вниз. ^[2] Это последовательность A000111 в Электронной энциклопедии целочисленных последовательностей . Они подсчитывают количество чередующихся перестановок букв n и связаны с числами Эйлера и числами Бернулли .

Алгебраическое определение(я)

Опираясь на геометрический дизайн преобразования бустрофедона, алгебраические определения отношений из входных значений ( $a_{i}$ ) для вывода значений ( $b_{i}$ ) могут быть определены для разных алгебр («числовые области»).

Евклидовы (реальные) значения

В Евклиде ( $\mathbb {E} ^{n}$ ) Алгебра на самом деле ( $\mathbb {R} ^{1}$ )-значные скаляры, преобразованное бустрофедоном Real -value $(b n)$ связано с входным значением $(a n)$ следующим образом:

${\begin{aligned}b_{n}&=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}E_{n-k}\\\end{aligned}}$ ,

с обратной зависимостью (вход от вывода), определяемой как:

${\begin{aligned}a_{n}&=\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}b_{k}E_{n-k}\end{aligned}}$ ,

где $(En секущие)$ последовательность чисел «вверх/вниз», также известная как — или касательные числа. ^[3]

Экспоненциальная производящая функция

Экспоненциальная производящая функция последовательности ( an _{выражением} ) определяется

EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.

Экспоненциальная производящая функция преобразования бустрофедона ( b _n ) связана с функцией исходной последовательности ( an _{соотношением} )

EG(b_{n};x)=(\sec x+\tan x)\,EG(a_{n};x).

Экспоненциальная производящая функция единичной последовательности равна 1, так что число чисел вверх/вниз равно sec x + tan x .

Ссылки

^ Вайсштейн, Эрик В. «Треугольник Зейделя-Энтрингера-Арнольда». Из MathWorld — веб-ресурса Wolfram. http://mathworld.wolfram.com/Seidel-Entringer-ArnoldTriangle.html
^ Вайсштейн, Эрик В. «Эйлерово число». Из MathWorld — веб-ресурса Wolfram. http://mathworld.wolfram.com/EulerianNumber.html
^ Вайсштейн, Эрик В. «Преобразование бустрофедона». Из MathWorld — веб-ресурса Wolfram. http://mathworld.wolfram.com/BoustropedonTransform.html

Миллар, Джессика; Слоан, Нью-Джерси; Янг, Нил Э. (1996). «Новая операция над последовательностями: преобразование Буструфедона». Журнал комбинаторной теории, серия А. 76 (1): 44–54. arXiv : math.CO/0205218 . дои : 10.1006/jcta.1996.0087 . S2CID 15637402 .
Вайсштейн, Эрик В. (2002). CRC Краткая математическая энциклопедия, второе издание . Чепмен и Холл/CRC. п. 273. ИСБН 1-58488-347-2 .

[1] Вайсштейн, Эрик В. «Треугольник Зейделя-Энтрингера-Арнольда». Из MathWorld — веб-ресурса Wolfram. http://mathworld.wolfram.com/Seidel-Entringer-ArnoldTriangle.html

[2] Вайсштейн, Эрик В. «Эйлерово число». Из MathWorld — веб-ресурса Wolfram. http://mathworld.wolfram.com/EulerianNumber.html

[3] Вайсштейн, Эрик В. «Преобразование бустрофедона». Из MathWorld — веб-ресурса Wolfram. http://mathworld.wolfram.com/BoustropedonTransform.html

[1]

[2]

[3]