# Boustrophedon transform

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 an "addition" operation.

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 ${\displaystyle b_{0}=a_{0}}$).

Generally speaking, given a sequence: ${\displaystyle (a_{0},a_{1},a_{2},\ldots )}$, the boustrophedon transform yields another sequence: ${\displaystyle (b_{0},b_{1},b_{2},\ldots )}$, where ${\displaystyle b_{0}}$ is likely defined equivalent to ${\displaystyle a_{0}}$. 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, ${\displaystyle (a_{0},a_{1},a_{2},\ldots )}$, 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 ${\displaystyle a_{0}}$, equivalent to output value ${\displaystyle b_{0}}$, 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 ${\displaystyle k}$ denote the number of the row currently being filled. These rows are constructed according to the row number (${\displaystyle k}$) as follows:

• For all rows, numbered ${\displaystyle k\in \mathbb {N} }$, there will be exactly ${\displaystyle (k+1)}$ values in the row.
• If ${\displaystyle k}$ is odd, then put the value ${\displaystyle a_{k}}$ on the right-hand end of the row.
• Fill-out the interior of this row from right-to-left, where each value (index: ${\displaystyle (k,j)}$) is the result of "addition" between the value to right (index: ${\displaystyle (k,j+1)}$) and the value to the upper right (index: ${\displaystyle (k-1,j+1)}$).
• The output value ${\displaystyle b_{k}}$ will be on the left-hand end of an odd row (where ${\displaystyle k}$ is odd).
• If ${\displaystyle k}$ is even, then put the input value ${\displaystyle a_{k}}$ on the left-hand end of the row.
• Fill-out the interior of this row from left-to-right, where each value (index: ${\displaystyle (k,j)}$) is the result of "addition" between the value to its left (index: ${\displaystyle (k,j-1)}$) and the value to its upper left (index: ${\displaystyle (k-1,j-1)}$).
• The output value ${\displaystyle b_{k}}$ will be on the right-hand end of an even row (where ${\displaystyle k}$ is even).

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

Note that for a given, finite input-sequence: ${\displaystyle (a_{0},a_{1},...a_{N})}$, of ${\displaystyle N}$ values, there will be exactly ${\displaystyle N}$ rows in the triangle, such that ${\displaystyle k}$ is an integer in the range: ${\displaystyle [0,N)}$ (exclusive). In other words, the last row is ${\displaystyle k=N-1}$.

## Recurrence relation

A more formal definition uses a recurrence relation. Define the numbers ${\displaystyle T_{k,n}}$ (with k ≥ n ≥ 0) by

${\displaystyle T_{k,0}=a_{k}}$
${\displaystyle T_{k,n}=T_{k,n-1}+T_{k-1,k-n}}$
${\displaystyle {\text{with }}}$
${\displaystyle \quad k,n\in \mathbb {N} }$
${\displaystyle \quad k\geq n>0}$.

Then the transformed sequence is defined by ${\displaystyle b_{n}=T_{n,n}}$ (for ${\displaystyle T_{2,2}}$ and greater indices).

Per this definition, note the following definitions for values outside the restrictions (from the relationship above) on ${\displaystyle (k,n)}$ pairs:

{\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}}}

### Special Cases

In the case a0 = 1, an = 0 (n > 0), the resulting triangle is called the Seidel–Entringer–Arnold Triangle[1] and the numbers ${\displaystyle T_{k,n}}$ are called Entringer numbers (sequence A008281 in the OEIS).

In this case the numbers in the transformed sequence bn are called the Euler up/down numbers[2]. 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 (${\displaystyle a_{i}}$) to output values (${\displaystyle b_{i}}$) can be defined for different algebras ("numeric domains").

### Euclidean (Real) values

In the Euclidean (${\displaystyle \mathbb {E} ^{n}}$) Algebra for Real (${\displaystyle \mathbb {R} ^{1}}$)-valued scalars, the boustrophedon transformed Real-value (bn) is related to the input value, (an), as:

{\displaystyle {\begin{aligned}b_{n}&=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}E_{n-k}\\\end{aligned}}},

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

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

where (En) is the sequence of "up/down" numbers -- also known as secant or tangent numbers[3].

## The exponential generating function

The exponential generating function of a sequence (an) is defined by

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

The exponential generating function of the boustrophedon transform (bn) is related to that of the original sequence (an) by

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

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

## References

1. ^ Weisstein, Eric W. "Seidel-Entringer-Arnold Triangle." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Seidel-Entringer-ArnoldTriangle.html
2. ^ Weisstein, Eric W. "Eulerian Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EulerianNumber.html
3. ^ Weisstein, Eric W. "Boustrophedon Transform." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/BoustrophedonTransform.html
• Millar, Jessica; Sloane, N.J.A.; Young, Neal E. (1996). "A New Operation on Sequences: the Boustrouphedon Transform". Journal of Combinatorial Theory Series A. 76 (1): 44–54. arXiv:math.CO/0205218. doi:10.1006/jcta.1996.0087.
• Weisstein, Eric W. (2002). CRC Concise Encyclopedia of Mathematics, Second Edition. Chapman & Hall/CRC. p. 273. ISBN 1-58488-347-2.