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.

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$, 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: ,_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_$_(with_''k'' ≥ ''n'' ≥ 0)_by
:$T__=_a_k$
:$T__=_T__+_T_$
:$\text$
:$\quad_k,n_\in_\mathbb$
:$\quad_k_\ge_n_>_0$.

Then_the_transformed_sequence_is_defined_by_$b_n_=_T_$_(for_$T_$_and_greater_indices).

Per_this_definition,_note_the_following_definitions_for_values_outside_the_restrictions_(from_the_relationship_above)_on_$(k,n)$_pairs:

$\begin T_\,_\overset&_\,_a__\,_\overset_\,_b_\\ \\ T_\,_\overset&_\,_a__\,_\iff_k_\,_\text\\ T_\,_\overset&_\,_b__\,_\iff_k_\,_\text\\ \\ T_\,_\overset&_\,_b__\,_\iff_k_\,_\text\\ T_\,_\overset&_\,_a__\,_\iff_k_\,_\text\\ \end$

__Special_Cases_

In_the_case_''a''₀_=_1,_''a''_''n''_=_0_(''n''_>_0),_the_resulting_triangle_is_called_the_Seidel–Entringer–Arnold_Triangle_and_the_numbers_$T_$_are_called_Entringer_numbers_.

In_this_case_the_numbers_in_the_transformed_sequence_''b''_''n''_are_called_the_Euler_up/down_numbers._This_is_sequence_oeis:A000111.html" "title="recurrence_relation.html" ;"title=", N) (exclusive). In other words, the last row is $k = N - 1$.

Recurrence relation

A more formal definition uses a recurrence relation">, 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_$ (with ''k'' ≥ ''n'' ≥ 0) by
:$T_ = a_k$
:$T_ = T_ + T_$
:$\text$
:$\quad k,n \in \mathbb$
:$\quad k \ge n > 0$.

Then the transformed sequence is defined by $b_n = T_$ (for $T_$ and greater indices).

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

$\begin T_\, \overset& \, a_ \, \overset \, b_\\ \\ T_\, \overset& \, a_ \, \iff k \, \text\\ T_\, \overset& \, b_ \, \iff k \, \text\\ \\ T_\, \overset& \, b_ \, \iff k \, \text\\ T_\, \overset& \, a_ \, \iff k \, \text\\ \end$

Special Cases

In the case ''a''₀ = 1, ''a''_''n'' = 0 (''n'' > 0), the resulting triangle is called the Seidel–Entringer–Arnold Triangle and the numbers $T_$ are called Entringer numbers .

In this case the numbers in the transformed sequence ''b''_''n'' are called the Euler up/down numbers. This is sequence oeis:A000111">A000111