В математике , то бустрофедон преобразование представляет собой процедуру , которая отображает одну последовательность в другую. Трансформировала последовательность вычисляются с помощью сложения «» операций, реализована как при заполнении треугольного массива в бустрофедоне ( зигзагообразный - или серпентин-подобные) способ, в отличие от «Растрового сканирования» пилообразной -как способ.
Определение
Преобразование бустрофедона - это числовое преобразование, генерирующее последовательность, которое определяется операцией «сложения» .
Вообще говоря, учитывая последовательность: , преобразование бустрофедона дает другую последовательность: , где вероятно определяется как эквивалент . Сама трансформация в целом может быть визуализирована (или представлена) как построенная путем заполнения треугольника, как показано на рисунке 1 .
Бустрофедонский треугольник
Чтобы заполнить числовой равнобедренный треугольник ( рис. 1 ), вы начинаете с входной последовательности:, и поместите одно значение (из входной последовательности) в каждую строку, используя метод сканирования бустрофедоном ( зигзагообразным или змеевидным ).
Верхняя вершина треугольника будет входным значением , эквивалент выходному значению , и мы нумеруем эту верхнюю строку как строку 0.
Последующие строки (вплоть до основания треугольника) нумеруются последовательно (от 0) целыми числами - пусть обозначают номер строки, которая в данный момент заполняется. Эти строки строятся в соответствии с номером строки () следующим образом:
- Для всех строк пронумерованы , точно будет значения в строке.
- Если является нечетным, тогда поместите значение в правом конце ряда.
- Заполните внутреннюю часть этой строки справа налево, где каждое значение (index: ) является результатом "сложения" значений справа (индекс: ) и значение вверху справа (индекс: ).
- Выходное значение будет в левом конце нечетной строки (где это нечетное ).
- Если четное, затем введите входное значение в левом конце ряда.
- Заполните внутреннюю часть этой строки слева направо, где каждое значение (index: ) является результатом "сложения" значения слева от него (индекс: ) и значение в верхнем левом углу (индекс: ).
- Выходное значение будет в правом конце четного ряда (где это даже ).
Обратитесь к стрелкам на рисунке 1 для визуального представления этих операций «сложения».
Для заданной конечной входной последовательности: , из значений, будет ровно строки в треугольнике, такие что является целым числом в диапазоне: (эксклюзив). Другими словами, последняя строка.
Отношение повторения
Более формальное определение использует отношение рекуррентности . Определите числа(при k ≥ n ≥ 0) на
- .
Тогда преобразованная последовательность определяется как (для и более высокие показатели).
В соответствии с этим определением обратите внимание на следующие определения значений вне ограничений (из отношения выше) на пары:
Особые случаи
В случае a 0 = 1, a n = 0 ( n > 0) полученный треугольник называется треугольником Зейделя – Энтрингера – Арнольда [1], а числаназываются номерами Entringer (последовательность A008281 в OEIS ).
В этом случае числа в преобразованной последовательности b n называются числами Эйлера вверх / вниз. [2] Это последовательность A000111 из Он-лайн энциклопедии целочисленных последовательностей . Это перечисление число чередующихся перестановок на п букв и связаны с числами Эйлера и чисел Бернулли .
Алгебраическое определение (я)
Основываясь на геометрическом дизайне преобразования бустрофедона, алгебраические определения отношения на основе входных значений () для вывода значений () можно определить для разных алгебр («числовых областей»).
Евклидовы (действительные) значения
В евклидовом () Алгебра для вещественных () -значные скаляры, преобразованное бустрофедоном Действительное -значение ( b n ) связано с входным значением ( a n ) следующим образом:
,
с обратной зависимостью (вход от выхода), определяемой как:
,
где ( E n ) - последовательность чисел «вверх / вниз», также известная как секущие или касательные числа. [3]
Экспоненциальная производящая функция
Экспоненциальная производящая функция последовательности ( п ) определяется
Экспоненциальная производящая функция преобразования бустрофедона ( b n ) связана с производящей функцией исходной последовательности ( a n ) соотношением
Экспоненциальная производящая функция единичной последовательности равна 1, так что из чисел вверх / вниз это sec x + tan x .
Рекомендации
- ^ Вайсштейн, Эрик В. "Треугольник Зайделя-Энтринджера-Арнольда". Из MathWorld - веб-ресурса Wolfram. http://mathworld.wolfram.com/Seidel-Entringer-ArnoldTriangle.html
- ^ Вайсштейн, Эрик В. «Число Эйлера». Из MathWorld - веб-ресурса Wolfram. http://mathworld.wolfram.com/EulerianNumber.html
- ^ Weisstein, Eric W. "бустрофедон Transform." Из MathWorld - веб-ресурса Wolfram. http://mathworld.wolfram.com/BoustrophedonTransform.html
- Миллар, Джессика; Слоан, штат Нью-Джерси; Янг, Нил Э. (1996). «Новая операция над последовательностями: преобразование Буструпэдона». Журнал комбинаторной теории, Серия А . 76 (1): 44–54. arXiv : math.CO/0205218 . DOI : 10,1006 / jcta.1996.0087 .
- Вайсштейн, Эрик В. (2002). CRC Краткая энциклопедия математики, второе издание . Чепмен и Холл / CRC. п. 273. ISBN. 1-58488-347-2.