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

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

ОпределениеПравить

 

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

Если дана последовательность $(a_0,a_1,a_2,\dots <!--\; \dots \; -->)$$(a_{0},a_{1},a_{2},\ldots )$ , бустрофедонное преобразование даёт другую последовательность, $(b_0,b_1,b_2,\dots <!--\; \dots \; -->)$$(b_{0},b_{1},b_{2},\ldots )$ , которая строится путём заполнения треугольника как показано на рисунке справа. Нумерация строк в треугольнике начинается с 0 и строки заполняются последовательно. Пусть k означает номер заполняемой строки.

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

Если определить $b_0=a_0$$b_{0}=a_{0}$ , числа $b_k|k>0$$b_{k}|k>0$ , образующие результирующую последовательность, можно найти слева (в начале) нечётных строк и справа (в конце) чётных, то есть в противоположных позициях числам исходной последовательности $a_k$$a_{k}$ .

Рекуррентные отношенияПравить

Более формальное определение использует рекуррентную формулу. Определим числа $T_{k,n}$$T_{k,n}$  (with $k⩾<!--\; ⩾\; -->n⩾<!--\; ⩾\; -->0$$k\geqslant n\geqslant 0$ ) следующим образом

$T_{k,0}=a_k$$T_{k,0}=a_{k}$  для $k⩾<!--\; ⩾\; -->0,$$k\geqslant 0,$ 

$T_{k,n}=T_{k,n-<!--\; -\; -->1}+T_{k-<!--\; -\; -->1,k-<!--\; -\; -->n}$$T_{k,n}=T_{k,n-1}+T_{k-1,k-n}$  для $k⩾<!--\; ⩾\; -->n>0.$$k\geqslant n>0.$ 

Тогда результирующая последовательность определяется как $b_n=T_{n,n}$$b_{n}=T_{n,n}$ .

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

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

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

$EG(a_n;x)=\underset{n=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{a}_n\frac{x^n}{n!}.$$EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.$ 

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

$EG(b_n;x)=(\sec <!--\; \; -->x+\tan <!--\; \; -->x)EG(a_n;x).$$EG(b_{n};x)=(\sec x+\tan x)\,EG(a_{n};x).$ 

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