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 ${\displaystyle \mathbf {b} =(b_{n})_{n\geq 0}={\mathcal {B}}(\mathbf {a} )}$ of an integer sequence ${\displaystyle \mathbf {a} =(a_{n})_{n\geq 0}}$ is most simply defined as ${\displaystyle b_{n}:=T_{n,n}}$, introducing an auxiliary triangle ${\displaystyle \mathbf {T} =(T_{n,k})_{n\geq k\geq 0}}$ defined by

${\displaystyle 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 ${\displaystyle (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 ${\displaystyle 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 ${\displaystyle T_{n,n}}$ of each row is defined to be ${\displaystyle b_{n}}$, so

${\displaystyle 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 ${\displaystyle b_{n}=\sum _{k=0}^{n}B_{n,k}a_{k}}$, where the Boustrophedon coefficients A109449 are given by

${\displaystyle 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 ${\displaystyle E_{n}}$ given in A000111, with e.g.f. ${\displaystyle \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 ${\displaystyle (-1)^{n+k}}$:

${\displaystyle \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

${\displaystyle 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.

Authorship

This page was created by M. F. Hasler on Oct. 5, 2017.