WikiDer > Преобразование Бустрофедона - Википедия

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

Определение

В преобразование бустрофедона числовое преобразование, генерирующее последовательность, которое определяется "добавление" операция.

Рисунок 1. Преобразование бустрофедона: начните с исходной последовательности (синего цвета), затем добавьте числа, как указано стрелками, и, наконец, прочтите преобразованную последовательность с другой стороны (красная, с ${ displaystyle b_ {0} = a_ {0}}$).

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

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

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

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

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

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

См. Стрелки на Рисунок 1 для наглядного представления этих операций "сложения".

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

Отношение рецидива

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

${ displaystyle T_ {k, 0} = a_ {k}}$

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

${ displaystyle { text {with}}}$

${ displaystyle quad k, п in mathbb {N}}$

${ Displaystyle четырехъядерный к GEQ п> 0}$.

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

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

${ displaystyle { begin {align} T_ {0,0} , { overset { Delta} {=}} & , a_ {0} , { overset { Delta} {=}} , b_ {0} T_ {k, 0} , { overset { Delta} {=}} & , a_ {k} , iff k , { text {четное}} T_ {k, 0} , { overset { Delta} {=}} & , b_ {k} , iff k , { text {is odd}} T_ {0, k} , { overset { Delta} {=}} & , b_ {k} , iff k , { text {четное}} T_ {0, k} , { overset { Delta} {=}} & , a_ {k} , iff k , { text {нечетное}} конец {выровнено}}}$

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

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

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

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

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

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

В евклидовом (${ displaystyle mathbb {E} ^ {n}}$) Алгебра для вещественных (${ Displaystyle mathbb {R} ^ {1}}$) -значные скаляры, бустрофедон преобразовал Настоящий-ценить (б_п) относится к входному значению, (а_п), в качестве:

${ displaystyle { begin {align} b_ {n} & = sum _ {k = 0} ^ {n} { binom {n} {k}} a_ {k} E_ {nk} end { выровнен}}}$,

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

${ displaystyle { begin {align} a_ {n} & = sum _ {k = 0} ^ {n} (- 1) ^ {nk} { binom {n} {k}} b_ {k} E_ {нк} конец {выровнено}}}$,

куда (E_п) представляет собой последовательность чисел "вверх / вниз", также известную как секущий или же касательная числа.^[3]

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

В экспоненциальная производящая функция последовательности (а_п) определяется

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

Экспоненциальная производящая функция преобразования бустрофедона (б_п) связана с исходной последовательностью (а_п) к

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

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

Рекомендации

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