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

Boustrophedon transform - Wikipedia

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

Определение

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

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

Вообще говоря, учитывая последовательность: , преобразование бустрофедона дает другую последовательность: , куда вероятно определяется как эквивалент . Сама трансформация в целом может быть визуализирована (или представлена) как построенная путем заполнения треугольника, как показано на Рисунок 1.

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

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

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

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

  • Для всех строк пронумерованы , точно будет значения в строке.
  • Если нечетное, тогда поместите значение в правом конце ряда.
    • Заполните внутреннюю часть этой строки справа налево, где каждое значение (index: ) является результатом "сложения" значений справа (индекс: ) и значение вверху справа (индекс: ).
    • Выходное значение будет в левом конце нечетной строки (где является странный).
  • Если четно, тогда введите входное значение в левом конце ряда.
    • Заполните внутреннюю часть этой строки слева направо, где каждое значение (index: ) является результатом "сложения" значения слева от него (индекс: ) и значение в верхнем левом углу (индекс: ).
    • Выходное значение будет в правом конце четного ряда (где является четное).

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

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

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

Более формальное определение использует отношение повторения. Определите числа k ≥ п ≥ 0) по

.

Тогда преобразованная последовательность определяется как (за и более высокие показатели).

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

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

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

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

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

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

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

В евклидовом () Алгебра для вещественных () -значные скаляры, бустрофедон преобразовал Настоящий-ценить (бп) относится к входному значению, (ап), в качестве:

,

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

,

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

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

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

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

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

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

  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/BoustrophedonTransform.html
  • Миллар, Джессика; 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.