Введение
Математическое преобразование последовательностей
В математике преобразование бустрофедона — это процедура, отображающая одну последовательность в другую. Преобразованная последовательность вычисляется посредством операции "сложения", реализованной как заполнение треугольного массива в бустрофедоновой (зигзагообразной или змеевидной) манере — в отличие от "растрового сканирования", напоминающего пилу.
In mathematics, the boustrophedon transform is a procedure which maps one sequence to another. The transformed sequence is computed by an "addition" operation, implemented as if filling a triangular array in a boustrophedon (zigzag or serpentine like) manner—as opposed to a "Raster Scan" sawtooth like manner.
Определение
Трансформация бустрофедона — это числовое преобразование, генерирующее последовательность, которое определяется бинарной операцией, такой как сложение. В общем случае, для заданной последовательности: , трансформация бустрофедона выдает другую последовательность: , где вероятно определяется как . Всю трансформацию можно представить (или вообразить) как построенную путем заполнения треугольника, как показано на рисунке 1.
Треугольник бустрофедона
Для заполнения числового равнобедренного треугольника (рисунок 1) вы начинаете с входной последовательности , и помещаете одно значение (из входной последовательности) в каждую строку, используя подход сканирования бустрофедоном (зигзагообразный или серпентинный). Верхняя вершина треугольника будет входным значением , эквивалентным выходному значению , и мы нумеруем эту верхнюю строку как строку 0. Последующие строки (вниз к основанию треугольника) нумеруются последовательно (от 0) целыми числами – пусть обозначает номер строки, которая в данный момент заполняется. Эти строки строятся в соответствии с номером строки следующим образом: для всех строк, пронумерованных , в строке будет ровно значений. Если нечетное, то поместите значение на правый конец строки. Заполните внутреннюю часть этой строки справа налево, где каждое значение (индекс: ) является результатом "сложения" между значением справа (индекс: ) и значением сверху справа (индекс: ). Выходное значение будет находиться на левом конце нечетной строки (где нечетное). Если четное, то поместите входное значение на левый конец строки. Заполните внутреннюю часть этой строки слева направо, где каждое значение (индекс: ) является результатом "сложения" между значением слева (индекс: ) и значением сверху слева (индекс: ). Выходное значение будет находиться на правом конце четной строки (где четное). Обратитесь к стрелкам на рисунке 1 для визуального представления этих операций "сложения". Для заданной, конечной входной последовательности: , состоящей из значений, в треугольнике будет ровно строк, таких, что – это целое число в диапазоне: (не включительно). Другими словами, последний ряд – это .
For all rows, numbered , there will be exactly values in the row. If is odd, then put the value on the right hand end of the row. Fill out the interior of this row from right to left, where each value (index: ) is the result of "addition" between the value to right (index: ) and the value to the upper right (index: ). The output value will be on the left hand end of an odd row (where is odd). If is even, then put the input value on the left hand end of the row. Fill out the interior of this row from left to right, where each value (index: ) is the result of "addition" between the value to its left (index: ) and the value to its upper left (index: ). The output value will be on the right hand end of an even row (where is even). Refer to the arrows in Figure 1 for a visual representation of these "addition" operations. For a given, finite input sequence: , of values, there will be exactly rows in the triangle, such that is an integer in the range: (exclusive). In other words, the last row is .
Особые случаи
В случае a0 = 1, an = 0 (n > 0), полученный треугольник называется треугольником Зейделя — Энтрингера — Арнольда, а числа называются числами Энтрингера. В этом случае числа в преобразованной последовательности bn называются числами Эйлера вверх/вниз. Это последовательность A000111 в Онлайн энциклопедии целых последовательностей. Они перечисляют количество чередующихся перестановок из n элементов и связаны с числами Эйлера и числами Бернулли.
In this case the numbers in the transformed sequence bn are called the Euler up/down numbers. This is sequence A000111 on the On Line Encyclopedia of Integer Sequences. These enumerate the number of alternating permutations on n letters and are related to the Euler numbers and the Bernoulli numbers.
Алгебраическое определение
Основываясь на геометрической структуре преобразования бустрофедон, можно определить алгебраические определения связи между входными и выходными значениями для различных алгебр ("числовых областей").