Boustrophedon transform

The Boustrophedon transform is a sequence transform which preserves integer sequences. The B-transform $\mathbf {b} =(b_{n})_{n\geq 0}={\mathcal {B}}(\mathbf {a} )$ of an integer sequence $\mathbf {a} =(a_{n})_{n\geq 0}$ is most simply defined as $b_{n}:=T_{n,n}$, introducing an auxiliary triangle $\mathbf {T} =(T_{n,k})_{n\geq k\geq 0}$ defined by

$T_{n,0}=a_{n}~;~~T_{n+1,k+1}=T_{n+1,k}+T_{n,n-k}~;~~{n\geq k\geq 0}~.$

Practical calculation

The above defining formula can be applied as follows: To calculate the triangle $(T_{n,k})_{n\geq k\geq 0}$, 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 $a_{n+1}$, 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 $T_{n,n}$ of each row is defined to be $b_{n}$, so

$b_{0}=T_{0,0}=a_{0},~b_{1}=T_{1,1}=a_{1}+a_{0},~b_{2}=T_{2,2}=a_{2}+b_{1}+a_{1},~...$

Explicit formula

As a result of the construction, one has $b_{n}=\sum _{k=0}^{n}B_{n,k}a_{k}$, where the Boustrophedon coefficients A109449 are given by

$B_{n,k}={n \choose k}E_{n-k}~,~~n\geq k\geq 0~,$

with the usual binomial coefficients and the so-called Euler numbers $E_{n}$ given in A000111, with e.g.f. $\sum E_{n}{\frac {x^{n}}{n!}}=\sec x+\tan x~~(\sec x=1/\cos x)$.

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 $(-1)^{n+k}$:

$\mathbf {B} ^{-1}={\begin{pmatrix}1&0&0&0&0&0&\cdots \\-1&1&0&0&0&0&\cdots \\1&-2&1&0&0&0&\cdots \\-2&3&-3&1&0&0&\cdots \\5&-8&6&-4&1&0&\cdots \\-16&25&-20&10&-5&1&\cdots \\61&-96&75&-40&15&-6&\ddots \\\vdots &&&\vdots &&&\ddots \end{pmatrix}}.$

As a consequence, multiplication by this inverse matrix is the inverse transformation, which can also be expressed as

$a_{n}={\mathcal {B}}^{-1}b_{n}=\sum _{k=0}^{n}(-1)^{n+k}\,B_{n,k}\,b_{k}~,~~n\geq k\geq 0.$

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]