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

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.

Note that 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 a0 = 1, an = 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 bn 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 (bn) is related to the input value, (an), 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 (En) 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 (an) 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 (bn) is related to that of the original sequence (an) 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.