Boustrophedon transform

{{short description|Mathematical transformation on sequences}} 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.

==Definition==

The boustrophedon transform is a numerical, sequence-generating transformation, which is determined by a binary operation such as addition.

right|frame|'''Figure 1.''' The boustrophedon transform: Start with the original sequence (in blue), then add numbers as indicated by the arrows, and finally read-off the transformed sequence on the other side (in red, with <math>b_0 = a_0</math>).

Generally speaking, given a sequence: <math>(a_0, a_1, a_2, \ldots)</math>, the boustrophedon transform yields another sequence: <math>(b_0, b_1, b_2, \ldots)</math>, where <math>b_0</math> is likely defined equivalent to <math>a_0</math>. The entirety of the transformation itself can be visualized (or imagined) as being constructed by filling-out the triangle as shown in '''Figure 1'''.

=== Boustrophedon Triangle ===

To fill-out the numerical Isosceles triangle ('''Figure 1'''), you start with the input sequence, <math>(a_0, a_1, a_2, \ldots)</math>, and place one value (from the input sequence) per row, using the boustrophedon scan (zigzag- or serpentine-like) approach.

The top vertex of the triangle will be the input value <math>a_0</math>, equivalent to output value <math>b_0</math>, and we number this top row as row 0.

The subsequent rows (going down to the base of the triangle) are numbered consecutively (from 0) as integers—let <math>k</math> denote the number of the row currently being filled. These rows are constructed according to the row number (<math>k</math>) as follows: * For all rows, numbered <math>k \in \mathbb{N}</math>, there will be exactly <math>(k+1)</math> values in the row. * If <math>k</math> is odd, then put the value <math>a_k</math> on the right-hand end of the row. ** Fill-out the interior of this row from right-to-left, where each value (index: <math>(k,j)</math>) is the result of "addition" between the value to right (index: <math>(k,j+1)</math>) and the value to the upper right (index: <math>(k-1,j+1)</math>). ** The output value <math>b_k</math> will be on the left-hand end of an odd row (where <math>k</math> is odd). * If <math>k</math> is even, then put the input value <math>a_k</math> on the left-hand end of the row. ** Fill-out the interior of this row from left-to-right, where each value (index: <math>(k,j)</math>) is the result of "addition" between the value to its left (index: <math>(k,j-1)</math>) and the value to its upper left (index: <math>(k-1,j-1)</math>). ** The output value <math>b_k</math> will be on the right-hand end of an even row (where <math>k</math> is even).

Refer to the arrows in '''Figure 1''' for a visual representation of these "addition" operations.

For a given, finite input-sequence: <math>(a_0, a_1, ... a_N)</math>, of <math>N</math> values, there will be exactly <math>N</math> rows in the triangle, such that <math>k</math> is an integer in the range: <math>[0, N)</math> (exclusive). In other words, the last row is <math>k = N - 1</math>.

==Recurrence relation==

A more formal definition uses a recurrence relation. Define the numbers <math>T_{k,n}</math> (with ''k'' ≥ ''n'' ≥ 0) by :<math>T_{k,0} = a_k</math> :<math>T_{k,n} = T_{k,n-1} + T_{k-1,k-n}</math> :<math>\text{with }</math> :<math>\quad k,n \in \mathbb{N}</math> :<math>\quad k \ge n > 0</math>.

Then the transformed sequence is defined by <math>b_n = T_{n,n}</math> (for <math>T_{2,2}</math> and greater indices).

Per this definition, note the following definitions for values outside the restrictions (from the relationship above) on <math>(k,n)</math> pairs:

<math>\begin{align} 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{align}</math>

=== Special Cases === In the case ''a''0 = 1, ''a''''n'' = 0 (''n'' > 0), the resulting triangle is called the '''Seidel–Entringer–Arnold Triangle'''<ref>[http://mathworld.wolfram.com/about/author.html Weisstein, Eric W.] "Seidel-Entringer-Arnold Triangle." From [http://mathworld.wolfram.com/ MathWorld]--A Wolfram Web Resource. http://mathworld.wolfram.com/Seidel-Entringer-ArnoldTriangle.html</ref> and the numbers <math>T_{k,n}</math> are called '''Entringer numbers''' {{OEIS|id=A008281}}.

In this case the numbers in the transformed sequence ''b''''n'' are called the Euler up/down numbers.<ref>[http://mathworld.wolfram.com/about/author.html Weisstein, Eric W.] "Eulerian Number." From [http://mathworld.wolfram.com/ MathWorld]--A Wolfram Web Resource. http://mathworld.wolfram.com/EulerianNumber.html</ref> 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.

== Algebraic definition(s) ==

Building from the geometric design of the boustrophedon transform, algebraic definitions of the relationship from input values (<math>a_i</math>) to output values (<math>b_i</math>) can be defined for different algebras ("numeric domains").

=== Euclidean (Real) values ===

In the Euclidean (<math>\mathbb{E}^{n}</math>) Algebra for Real (<math>\mathbb{R}^{1}</math>)-valued scalars, the boustrophedon transformed Real-value {{math|(''b''{{sub|''n''}})}} is related to the input value, {{math|(''a''{{sub|''n''}})}}, as:

<math>\begin{align} b_n &= \sum_{k=0}^n \binom{n}{k} a_k E_{n-k} \\ \end{align}</math>,

with the reverse relationship (input from output) defined as:

<math>\begin{align} a_n &= \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} b_k E_{n-k} \end{align}</math>,

where {{math|(''E''{{sub|''n''}})}} is the sequence of "up/down" numbers—also known as secant or tangent numbers.<ref>[http://mathworld.wolfram.com/about/author.html Weisstein, Eric W.] "Boustrophedon Transform." From [http://mathworld.wolfram.com/ MathWorld]--A Wolfram Web Resource. http://mathworld.wolfram.com/BoustrophedonTransform.html</ref>

==The exponential generating function==

The exponential generating function of a sequence (''a''''n'') is defined by :<math> EG(a_n;x)=\sum _{n=0}^{\infty} a_n \frac{x^n}{n!}. </math> The exponential generating function of the boustrophedon transform (''b''''n'') is related to that of the original sequence (''a''''n'') by :<math> EG(b_n;x) = (\sec x + \tan x) \, EG(a_n;x). </math>

The exponential generating function of the unit sequence is 1, so that of the up/down numbers is sec ''x'' + tan ''x''.

==References== {{reflist}} * {{cite journal|first1=Jessica|last1= Millar |first2=N.J.A. |last2=Sloane |first3=Neal E. |last3= Young |title =A New Operation on Sequences: the Boustrouphedon Transform |journal=Journal of Combinatorial Theory, Series A | volume=76 | number=1|pages=44–54 |year=1996|doi=10.1006/jcta.1996.0087|arxiv=math.CO/0205218|s2cid= 15637402 }} * {{cite book |author=Weisstein, Eric W. |title=CRC Concise Encyclopedia of Mathematics, Second Edition |publisher=Chapman & Hall/CRC |year=2002 |page=273 |isbn=1-58488-347-2}}

Category:Integer sequences Category:Triangles of numbers Category:Permutations Category:Transforms