# 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 a binary operation such as addition.
Generally speaking, given a sequence: $(a_{0},a_{1},a_{2},\ldots )$, the boustrophedon transform yields another sequence: $(b_{0},b_{1},b_{2},\ldots )$, where $b_{0}$ is likely defined equivalent to $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, $(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 $a_{0}$, equivalent to output value $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 $k$ denote the number of the row currently being filled. These rows are constructed according to the row number ($k$) as follows:
* For all rows, numbered $k\in \mathbb {N}$, there will be exactly $(k+1)$ values in the row.
* If $k$ is odd, then put the value $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: $(k,j)$) is the result of "addition" between the value to right (index: $(k,j+1)$) and the value to the upper right (index: $(k-1,j+1)$).
** The output value $b_{k}$ will be on the left-hand end of an odd row (where $k$ is odd).
* If $k$ is even, then put the input value $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: $(k,j)$) is the result of "addition" between the value to its left (index: $(k,j-1)$) and the value to its upper left (index: $(k-1,j-1)$).
** The output value $b_{k}$ will be on the right-hand end of an even row (where $k$ is even).
Refer to the arrows in Figure 1 for a visual representation of these "addition" operations.
For a given, finite input-sequence: $(a_{0},a_{1},...a_{N})$, of $N$ values, there will be exactly $N$ rows in the triangle, such that $k$ is an integer in the range: $[0,N)$ (exclusive). In other words, the last row is $k=N-1$.

## Recurrence relation

A more formal definition uses a recurrence relation. Define the numbers $T_{k,n}$ (with k ≥ n ≥ 0) by
    $T_{k,0}=a_{k}$
    $T_{k,n}=T_{k,n-1}+T_{k-1,k-n}$
    ${\text{with }}$
    $\quad k,n\in \mathbb {N}$
    $\quad k\geq n>0$.
Then the transformed sequence is defined by $b_{n}=T_{n,n}$ (for $T_{2,2}$ and greater indices).
Per this definition, note the following definitions for values outside the restrictions (from the relationship above) on $(k,n)$ pairs:
${\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 a$_0$ = 1, a$_n$ = 0 (n > 0), the resulting triangle is called the Seidel–Entringer–Arnold Triangle and the numbers $T_{k,n}$ are called Entringer numbers (sequence A008281 in the OEIS).
In this case the numbers in the transformed sequence b$_n$ are called the Euler up/down numbers. 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 ($a_{i}$) to output values ($b_{i}$) can be defined for different algebras ("numeric domains").

### Euclidean (Real) values

In the Euclidean ($\mathbb {E} ^{n}$) Algebra for Real ($\mathbb {R} ^{1}$)-valued scalars, the boustrophedon transformed Real-value (b$_n$) is related to the input value, (a$_n$), as:
${\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:
${\begin{aligned}a_{n}&=\sum _{k=0}^{n}(-1)^{n-k}{\binom {n}{k}}b_{k}E_{n-k}\end{aligned}}$,
where (E$_n$) is the sequence of "up/down" numbers—also known as secant or tangent numbers.

## The exponential generating function

The exponential generating function of a sequence (a$_n$) is defined by
    $EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.$
The exponential generating function of the boustrophedon transform (b$_n$) is related to that of the original sequence (a$_n$) by
    $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.