Бустрофедон трансформируется
Математическое преобразование последовательностей

В математике преобразование бустрофедона — это процедура, которая отображает одну последовательность в другую. Преобразованная последовательность вычисляется с помощью операции «сложения», реализованной так, как если бы заполнялся треугольный массив в бустрофедонном ( зигзагообразном или змеевидном) стиле — в отличие от пилообразного « Растрового сканирования» .

Определение

Преобразование бустрофедона — это числовое преобразование, генерирующее последовательность, которое определяется бинарной операцией, такой как сложение .

Рисунок 1. Преобразование бустрофедона: начните с исходной последовательности (синего цвета), затем добавьте числа, как указано стрелками, и, наконец, считайте преобразованную последовательность с другой стороны (красного цвета, с ). б 0 = а 0 {\displaystyle b_{0}=a_{0}}

Вообще говоря, если задана последовательность: , преобразование бустрофедона дает другую последовательность: , где , вероятно, определено эквивалентно . Полноту самого преобразования можно визуализировать (или представить) как построенную путем заполнения треугольника, как показано на рисунке 1 . ( а 0 , а 1 , а 2 , … ) {\displaystyle (a_{0},a_{1},a_{2},\ldots )} ( б 0 , б 1 , б 2 , … ) {\displaystyle (b_{0},b_{1},b_{2},\ldots )} б 0 {\displaystyle b_{0}} а 0 {\displaystyle а_{0}}

Треугольник Бустрофедон

Чтобы заполнить числовой равнобедренный треугольник ( рисунок 1 ), вы начинаете с входной последовательности и помещаете одно значение (из входной последовательности) в каждую строку, используя подход сканирования бустрофедона ( зигзагообразный или змеевидный). ( а 0 , а 1 , а 2 , … ) {\displaystyle (a_{0},a_{1},a_{2},\ldots )}

Верхняя вершина треугольника будет входным значением , эквивалентным выходному значению , и мы нумеруем эту верхнюю строку как строку 0. а 0 {\displaystyle а_{0}} б 0 {\displaystyle b_{0}}

Последующие строки (спускаясь к основанию треугольника) нумеруются последовательно (от 0) как целые числа — пусть обозначает номер заполняемой в данный момент строки. Эти строки строятся в соответствии с номером строки ( ) следующим образом: к {\displaystyle к} к {\displaystyle к}

  • Для всех пронумерованных строк в строке будет ровно значений. к ∈ Н {\displaystyle k\in \mathbb {N} } ( к + 1 ) {\displaystyle (к+1)}
  • Если нечетное, то поместите значение в правый конец строки. к {\displaystyle к} а к {\displaystyle а_{к}}
    • Заполните внутреннюю часть этой строки справа налево, где каждое значение (индекс: ) является результатом «сложения» значения справа (индекс: ) и значения вверху справа (индекс: ). ( к , дж ) {\displaystyle (к,j)} ( к , дж + 1 ) {\displaystyle (к,j+1)} ( к − 1 , дж + 1 ) {\displaystyle (k-1,j+1)}
    • Выходное значение будет находиться в левом конце нечетной строки (где — нечетное ). б к {\displaystyle b_{k}} к {\displaystyle к}
  • Если четное, то поместите входное значение в левый конец строки. к {\displaystyle к} а к {\displaystyle а_{к}}
    • Заполните внутреннюю часть этой строки слева направо, где каждое значение (индекс: ) является результатом «сложения» значения слева от него (индекс: ) и значения вверху слева (индекс: ). ( к , дж ) {\displaystyle (к,j)} ( к , дж − 1 ) {\displaystyle (к,j-1)} ( к − 1 , дж − 1 ) {\displaystyle (k-1,j-1)}
    • Выходное значение будет находиться в правом конце четной строки (где четно ) . б к {\displaystyle b_{k}} к {\displaystyle к}

Для визуального представления этих операций «сложения» обратитесь к стрелкам на рисунке 1 .

Для заданной конечной входной последовательности: значений , в треугольнике будет ровно строк, таких, что — целое число в диапазоне: (исключая). Другими словами, последняя строка — это . ( а 0 , а 1 , . . . а Н ) {\displaystyle (a_{0},a_{1},...a_{N})} Н {\displaystyle N} Н {\displaystyle N} к {\displaystyle к} [ 0 , Н ) {\displaystyle [0,N)} к = Н − 1 {\displaystyle k=N-1}

Рекуррентное соотношение

Более формальное определение использует рекуррентное соотношение . Определим числа (при k  ≥  n  ≥ 0) как Т к , н {\displaystyle T_{k,n}}

Т к , 0 = а к {\displaystyle T_{k,0}=a_{k}}
Т к , н = Т к , н − 1 + Т к − 1 , к − н {\displaystyle T_{k,n}=T_{k,n-1}+T_{k-1,kn}}
с  {\displaystyle {\text{с}}}
к , н ∈ Н {\displaystyle \quad k,n\in \mathbb {N} }
к ≥ н > 0 {\displaystyle \quad k\geq n>0} .

Тогда преобразованная последовательность определяется как (для и больших индексов). б н = Т н , н {\displaystyle b_{n}=T_{n,n}} Т 2 , 2 {\displaystyle T_{2,2}}

В соответствии с этим определением обратите внимание на следующие определения для значений, выходящих за рамки ограничений (из приведенного выше соотношения) для пар: ( k , n ) {\displaystyle (k,n)}

T 0 , 0 = Δ a 0 = Δ b 0 T k , 0 = Δ a k ⟺ k is even T k , 0 = Δ b k ⟺ k is odd T 0 , k = Δ b k ⟺ k is even T 0 , k = Δ a k ⟺ k is odd {\displaystyle {\begin{aligned}T_{0,0}\,{\overset {\Delta }{=}}&\,a_{0}\,{\overset {\Delta }{=}}\,b_{0}\\\\T_{k,0}\,{\overset {\Delta }{=}}&\,a_{k}\,\iff k\,{\text{is even}}\\T_{k,0}\,{\overset {\Delta }{=}}&\,b_{k}\,\iff k\,{\text{is odd}}\\\\T_{0,k}\,{\overset {\Delta }{=}}&\,b_{k}\,\iff k\,{\text{is even}}\\T_{0,k}\,{\overset {\Delta }{=}}&\,a_{k}\,\iff k\,{\text{is odd}}\\\end{aligned}}}

Особые случаи

В случае a0 = 1, an = 0 ( n > 0) полученный треугольник называется треугольником Зейделя–Энтрингера–Арнольда [1] , а числа называются числами Энтрингера (последовательность A008281 в OEIS ). T k , n {\displaystyle T_{k,n}}

В этом случае числа в преобразованной последовательности b n называются числами Эйлера вверх/вниз. [2] Это последовательность A000111 в On-Line Encyclopedia of Integer Sequences . Они перечисляют количество чередующихся перестановок на n буквах и связаны с числами Эйлера и числами Бернулли .

Алгебраические определения

Основываясь на геометрической конструкции преобразования бустрофедона, можно определить алгебраические определения связи между входными значениями ( ) и выходными значениями ( ) для различных алгебр («числовых областей»). a i {\displaystyle a_{i}} b i {\displaystyle b_{i}}

Евклидовы (действительные) значения

В евклидовой ( ) алгебре для действительных ( )-значных скаляров преобразованное бустрофедоном действительное значение ( b n ) связано с входным значением ( a n ) следующим образом: E n {\displaystyle \mathbb {E} ^{n}} R 1 {\displaystyle \mathbb {R} ^{1}}

b n = ∑ k = 0 n ( n k ) a k E n − k {\displaystyle {\begin{aligned}b_{n}&=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}E_{n-k}\\\end{aligned}}} ,

с обратной связью (вход от выхода), определяемой как:

a n = ∑ k = 0 n ( − 1 ) n − k ( n k ) b k E n − k {\displaystyle {\begin{aligned}a_{n}&=\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}b_{k}E_{n-k}\end{aligned}}} ,

где ( E n ) — последовательность чисел «вверх/вниз», также известная как секанс или тангенс . [3]

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

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

E G ( a n ; x ) = ∑ n = 0 ∞ a n x n n ! . {\displaystyle EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.}

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

E G ( b n ; x ) = ( sec ⁡ x + tan ⁡ x ) E G ( a n ; x ) . {\displaystyle EG(b_{n};x)=(\sec x+\tan x)\,EG(a_{n};x).}

Экспоненциальная производящая функция единичной последовательности равна 1, поэтому функция чисел вверх/вниз равна sec  x  + tan  x .

Ссылки

  1. ^ Вайсштейн, Эрик В. «Треугольник Зейделя-Энтрингера-Арнольда». Из MathWorld — веб-ресурса Wolfram. http://mathworld.wolfram.com/Seidel-Entringer-ArnoldTriangle.html
  2. ^ Weisstein, Eric W. "Число Эйлера". Из MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EulerianNumber.html
  3. ^ Weisstein, Eric W. «Преобразование Бустрофедона». Из MathWorld — веб-ресурса Wolfram. http://mathworld.wolfram.com/BoustrophedonTransform.html
  • Миллар, Джессика; Слоан, NJA; Янг, Нил Э. (1996). «Новая операция над последовательностями: преобразование Буструфедона». Журнал комбинаторной теории, серия A. 76 ( 1): 44–54 . arXiv : math.CO/0205218 . doi :10.1006/jcta.1996.0087. S2CID  15637402.
  • Weisstein, Eric W. (2002). CRC Concise Encyclopedia of Mathematics, второе издание . Chapman & Hall/CRC. стр. 273. ISBN 1-58488-347-2.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Boustrophedon_transform&oldid=1215445233"