# 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.

## Contents

## Definition[edit]

The boustrophedon transform is a numerical, sequence-generating transformation, which is determined by an "addition" operation.

Generally speaking, given a sequence: , the boustrophedon transform yields another sequence: , where is likely defined equivalent to . 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[edit]

To fill-out the numerical Isosceles triangle (**Figure 1**), you start with the input sequence, , 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 , equivalent to output value , 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 denote the number of the row currently being filled. These rows are constructed according to the row number () as follows:

- For all rows, numbered , there will be exactly values in the row.
- If is odd, then put the value on the right-hand end of the row.
- Fill-out the interior of this row from right-to-left, where each value (index: ) is the result of "addition" between the value to right (index: ) and the value to the upper right (index: ).
- The output value will be on the left-hand end of an odd row (where is odd).

- If is even, then put the input value on the left-hand end of the row.
- Fill-out the interior of this row from left-to-right, where each value (index: ) is the result of "addition" between the value to its left (index: ) and the value to its upper left (index: ).
- The output value will be on the right-hand end of an even row (where 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: , of values, there will be exactly rows in the triangle, such that is an integer in the range: (exclusive). In other words, the last row is .

## Recurrence relation[edit]

A more formal definition uses a recurrence relation. Define the numbers (with *k* ≥ *n* ≥ 0) by

- .

Then the transformed sequence is defined by (for and greater indices).

Per this definition, note the following definitions for values outside the restrictions (from the relationship above) on pairs:

### Special Cases[edit]

In the case *a*_{0} = 1, *a*_{n} = 0 (*n* > 0), the resulting triangle is called the **Seidel–Entringer–Arnold Triangle**^{[1]} and the numbers 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^{[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)[edit]

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

### Euclidean (Real) values[edit]

In the Euclidean () Algebra for Real ()-valued scalars, the boustrophedon transformed Real-value (*b*_{n}) is related to the input value, (*a*_{n}), as:

,

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

,

where (*E*_{n}) is the sequence of "up/down" numbers -- also known as secant or tangent numbers^{[3]}.

## The exponential generating function[edit]

The exponential generating function of a sequence (*a*_{n}) is defined by

The exponential generating function of the boustrophedon transform (*b*_{n}) is related to that of the original sequence (*a*_{n}) by

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

## References[edit]

**^**Weisstein, Eric W. "Seidel-Entringer-Arnold Triangle." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Seidel-Entringer-ArnoldTriangle.html**^**Weisstein, Eric W. "Eulerian Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EulerianNumber.html**^**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.