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

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

Определение

Бустрофедонное преобразование: Исходная последовательность показана синим цветом. Добавляем числа, как показано стрелками, считываем полученную последовательность с противоположных позиций в строках (последовательность показана красным цветом, [math]\displaystyle{ b_0 = a_0 }[/math]).

Если дана последовательность [math]\displaystyle{ (a_0, a_1, a_2, \ldots) }[/math], бустрофедонное преобразование даёт другую последовательность, [math]\displaystyle{ (b_0, b_1, b_2, \ldots) }[/math], которая строится путём заполнения треугольника как показано на рисунке справа. Нумерация строк в треугольнике начинается с 0 и строки заполняются последовательно. Пусть k означает номер заполняемой строки.

Если k нечётно, помещаем число [math]\displaystyle{ a_k }[/math] в правую позицию строки и заполняем строку справа налево, записывая каждое новое значение как сумму чисел справа и справа выше. Если k чётно, записываем число [math]\displaystyle{ a_k }[/math] в начале строки (слева) и заполняем строку слева направо, записывая каждое новое значение как сумму чисел слева и слева выше.

Если определить [math]\displaystyle{ b_0 = a_0 }[/math], числа [math]\displaystyle{ b_k | k \gt 0 }[/math], образующие результирующую последовательность, можно найти слева (в начале) нечётных строк и справа (в конце) чётных, то есть в противоположных позициях числам исходной последовательности [math]\displaystyle{ a_k }[/math].

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

Более формальное определение использует рекуррентную формулу. Определим числа [math]\displaystyle{ T_{k,n} }[/math] (with [math]\displaystyle{ k \geqslant n \geqslant 0 }[/math]) следующим образом

[math]\displaystyle{ T_{k,0} = a_k }[/math] для [math]\displaystyle{ k \geqslant 0, }[/math]

[math]\displaystyle{ T_{k,n} = T_{k,n-1} + T_{k-1,k-n} }[/math] для [math]\displaystyle{ k \geqslant n \gt 0. }[/math]

Тогда результирующая последовательность определяется как [math]\displaystyle{ b_n = T_{n,n} }[/math].

В случае a₀ = 1, a_n = 0 (n > 0) получающийся треугольник называется треугольником Зайделя — Энтрингера — Арнольда, а числа [math]\displaystyle{ T_{k,n} }[/math] называются числами Энтрингера (последовательность A008281 в OEIS). В этом случае числа результирующей последовательности b_n называются пилообразными (up/down) числами Эйлера. Это последовательность A000111 в «Энциклопедии целочисленных последовательностей». Последовательность содержит число чередующихся перестановок n букв и связана с числами Эйлера и числами Бернулли.

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

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

[math]\displaystyle{ EG(a_n;x)=\sum _{n=0}^{\infty} a_n \frac{x^n}{n!}. }[/math]

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

[math]\displaystyle{ EG(b_n;x) = (\sec x + \tan x) \, EG(a_n;x). }[/math]

Экспоненциальная производящая функция последовательности единиц равна 1, так что пилообразные (up/down) числа равны sec x + tan x.