- Source: 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 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.
= Boustrophedon Triangle
=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}
.
Recurrence relation
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}}}
= 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
{\displaystyle 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
{\displaystyle a_{i}}
) to output values (
b
i
{\displaystyle b_{i}}
) can be defined for different algebras ("numeric domains").
= Euclidean (Real) values
=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 (bn) is related to the input value, (an), 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 (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
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 (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
)
.
{\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.
References
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.
Kata Kunci Pencarian:
- Boustrophedon transform
- Boustrophedon
- Floyd–Steinberg dithering
- Triangular array
- Bernoulli number
- Alternating permutation
- List of triangle topics
- Zigzag (disambiguation)
- Boustrophedon cell decomposition
- History of writing
