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.

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 , … ) {\displaystyle (a_{0},a_{1},a_{2},\ldots )} , the boustrophedon transform yields another sequence: ( b 0 , b 1 , b 2 , … ) {\displaystyle (b_{0},b_{1},b_{2},\ldots )} , where b 0 {\displaystyle b_{0}} is likely defined equivalent to a 0 {\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.

To fill-out the numerical Isosceles triangle (Figure 1), you start with the input sequence, ( a 0 , a 1 , a 2 , … ) {\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 a 0 {\displaystyle a_{0}} , equivalent to output value b 0 {\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 k {\displaystyle k} denote the number of the row currently being filled. These rows are constructed according to the row number ( k {\displaystyle k} ) as follows:

• For all rows, numbered k ∈ N {\displaystyle k\in \mathbb {N} } , there will be exactly ( k + 1 ) {\displaystyle (k+1)} values in the row.
• If k {\displaystyle k} is odd, then put the value a k {\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: ( k , j ) {\displaystyle (k,j)} ) is the result of "addition" between the value to right (index: ( k , j + 1 ) {\displaystyle (k,j+1)} ) and the value to the upper right (index: ( k − 1 , j + 1 ) {\displaystyle (k-1,j+1)} ).
  • The output value b k {\displaystyle b_{k}} will be on the left-hand end of an odd row (where k {\displaystyle k} is odd).
• If k {\displaystyle k} is even, then put the input value a k {\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: ( k , j ) {\displaystyle (k,j)} ) is the result of "addition" between the value to its left (index: ( k , j − 1 ) {\displaystyle (k,j-1)} ) and the value to its upper left (index: ( k − 1 , j − 1 ) {\displaystyle (k-1,j-1)} ).
  • The output value b k {\displaystyle b_{k}} will be on the right-hand end of an even row (where k {\displaystyle 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 ) {\displaystyle (a_{0},a_{1},...a_{N})} , of N {\displaystyle N} values, there will be exactly N {\displaystyle N} rows in the triangle, such that k {\displaystyle k} is an integer in the range: [ 0 , N ) {\displaystyle [0,N)} (exclusive). In other words, the last row is k = N − 1 {\displaystyle k=N-1} .

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

T k , 0 = a k {\displaystyle T_{k,0}=a_{k}}

T k , n = T k , n − 1 + T k − 1 , k − n {\displaystyle T_{k,n}=T_{k,n-1}+T_{k-1,k-n}}

with  {\displaystyle {\text{with }}}

k , n ∈ N {\displaystyle \quad k,n\in \mathbb {N} }

k ≥ n > 0 {\displaystyle \quad k\geq n>0} .

Then the transformed sequence is defined by b n = T n , n {\displaystyle b_{n}=T_{n,n}} (for T 2 , 2 {\displaystyle 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 ) {\displaystyle (k,n)} pairs:

T 0 , 0 = Δ a 0 = Δ b 0 T k , 0 = Δ a k ⟺ k is even T k , 0 = Δ b k ⟺ k is odd T 0 , k = Δ b k ⟺ k is even T 0 , k = Δ a k ⟺ k is odd {\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}}}

In the case a₀ = 1, a_n = 0 (n > 0), the resulting triangle is called the Seidel–Entringer–Arnold Triangle^[1] and the numbers T k , n {\displaystyle 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.^[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.

Building from the geometric design of the boustrophedon transform, algebraic definitions of the relationship from input values ( a i {\displaystyle a_{i}} ) to output values ( b i {\displaystyle b_{i}} ) can be defined for different algebras ("numeric domains").

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

b n = ∑ k = 0 n ( n k ) a k E n − k {\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:

a n = ∑ k = 0 n ( − 1 ) n − k ( n k ) b k E n − k {\displaystyle {\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.^[3]

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

E G ( a n ; x ) = ∑ n = 0 ∞ a n x n n ! . {\displaystyle 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

E G ( b n ; x ) = ( sec ⁡ x + tan ⁡ x ) E G ( a n ; x ) . {\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.

• 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. S2CID 15637402.
• Weisstein, Eric W. (2002). CRC Concise Encyclopedia of Mathematics, Second Edition. Chapman & Hall/CRC. p. 273. ISBN 1-58488-347-2.