This site is supported by donations to The OEIS Foundation.
Boustrophedon transform
The Boustrophedon transform is a sequence transform which preserves integer sequences. The B-transform of an integer sequence is most simply defined as , introducing an auxiliary triangle defined by
Contents
Practical calculation
The above defining formula can be applied as follows: To calculate the triangle , fill the increasingly longer rows in alternating directions (one row from left to right, next row from right to left), starting the n-th row at the respective beginning with , and then adding as next element the sum of the previously placed element plus the nearest element on the previous row:
T00 := a0 a1 =: T10 --------> T11=T10+T00 T22=T21+T10 <-------- T21=T20+T11 <-------- T20 := a2 a3 =: T30 --------> T31=T30+T22 --------> T32=T31+T21 --------> T33=T32+T20 (...) <-------- T41=T40+T33 <-------- T40 := a4
and so on.
The "final" element of each row is defined to be , so
Explicit formula
As a result of the construction, one has , where the Boustrophedon coefficients A109449 are given by
with the usual binomial coefficients and the so-called Euler numbers given in A000111, with e.g.f. .
The table of these Boustrophedon coefficients reads:
1; 1, 1; 1, 2, 1; 2, 3, 3, 1; 5, 8, 6, 4, 1; 16, 25, 20, 10, 5, 1; 61, 96, 75, 40, 15, 6, 1; (...)
If this table is considered as an infinite square array or matrix B, completing the upper right half with zeros, the Boustrophedon transform can be expressed as simply multiplying the sequence, considered as a column matrix, by this matrix B.
Inverse transform
The above infinite matrix B has an inverse (A247453) which is equal to B up to alternating signs :
As a consequence, multiplication by this inverse matrix is the inverse transformation, which can also be expressed as
History
(to be written) -- see the Millar, Sloane & Young reference.
Programs
PARI/gp
B(a,T=a[1..1],S)={for(n=2,#a,T=vector(n,k,if(k>1,S+=T[n-k+1],S=a[n]))/*;print(T)*/;a[n]=S);a}
or
B(a)={a+vector(#a,n,sum(k=1,n-1,abs(polylog(k-n,I))*2*binomial(n-1,k-1)*a[k]))}
See the "Transformations of Integer Sequences" page on main OEIS web site for further Maple, Mathematica and PARI/GP code.
References
- J. Millar, N. J. A. Sloane and N. E. Young, A new operation on sequences: the Boustrophedon transform, J. Comb. Theory 17A (1996) pp. 44-54.
Authorship
This page was created by M. F. Hasler on Oct. 5, 2017.
Cite this page as
M. F. Hasler, Boustrophedon transform.— From the On-Line Encyclopedia of Integer Sequences® Wiki (OEIS® Wiki). [https://oeis.org/wiki/Boustrophedon_transform]