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

Определение

Если дана последовательность ${\displaystyle (a_{0},a_{1},a_{2},\ldots )}$ , бустрофедонное преобразование даёт другую последовательность, ${\displaystyle (b_{0},b_{1},b_{2},\ldots )}$ , которая строится путём заполнения треугольника как показано на рисунке справа. Нумерация строк в треугольнике начинается с 0 и строки заполняются последовательно. Пусть k означает номер заполняемой строки.

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

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

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

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

${\displaystyle T_{k,0}=a_{k}}$ для ${\displaystyle k\geqslant 0,}$

${\displaystyle T_{k,n}=T_{k,n-1}+T_{k-1,k-n}}$ для ${\displaystyle k\geqslant n>0.}$

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

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

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

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

${\displaystyle EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.}$

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

${\displaystyle EG(b_{n};x)=(\sec x+\tan x)\,EG(a_{n};x).}$

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

Примечания

Литература