In mathematics, the boustrophedon transform is a procedure which maps one sequence to another. The transformed sequence is computed by filling a triangular array in boustrophedon (zig-zag) manner.
Given a sequence
(
a
0
,
a
1
,
a
2
,
…
)
, the boustrophedon transform yields another sequence,
(
b
0
,
b
1
,
b
2
,
…
)
, which is constructed by filling up a triangle as pictured on the right. Number the rows in the triangle starting from 0, and fill the rows consecutively. Let k denote the number of the row currently being filled.
If k is odd, then put the number
a
k
on the right end of the row and fill the row from the right to the left, with every entry being the sum of the number to the right and the number to the upper right. If k is even, then put the number
a
k
on the left end and fill the row from the left to the right, with every entry being the sum of the number to the left and the number to the upper left.
Defining
b
0
=
a
0
, the numbers
b
k
|
k
>
0
forming the transformed sequence can then be found on the left end of odd-numbered rows and on the right end of even-numbered rows, that is, opposite to the numbers
a
k
.
A more formal definition uses a recurrence relation. Define the numbers
T
k
,
n
(with k ≥ n ≥ 0) by
T
k
,
0
=
a
k
for
k
≥
0
,
T
k
,
n
=
T
k
,
n
−
1
+
T
k
−
1
,
k
−
n
for
k
≥
n
>
0.
Then the transformed sequence is defined by
b
n
=
T
n
,
n
.
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.
The exponential generating function of a sequence (an) is defined by
E
G
(
a
n
;
x
)
=
∑
n
=
0
∞
a
n
x
n
n
!
.
The exponential generating function of the boustrophedon transform (bn) is related to that of the original sequence (an) by
E
G
(
b
n
;
x
)
=
(
sec
x
+
tan
x
)
E
G
(
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.
