Boustrophedon transform

Boustrophedon transform

In mathematics, the boustrophedon transform is a procedure which maps one sequence to another. The transformed sequence is computed by filling a triangle in boustrophedon (zig-zag) manner.


Given a sequence (a_0, a_1, a_2, ldots), the boustrophedon transform yields another sequence, (b_0, b_1, b_2, ldots), 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.

The numbers b_k 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.

Recurrence relation

A more formal definition uses a recurrence relation. Define the numbers T_{k,n} (with "k" ≥ "n" ≥ 0) by:T_{k,0} = a_k quad mbox{for } k ge 0, :T_{k,n} = T_{k,n-1} + T_{k-1,k-n} quad mbox{for } k ge n > 0. Then the transformed sequence is defined by b_n = T_{n,n} .

The up/down numbers

The up/down numbers u_n count the number of alternating permutations of the set {1, 2, 3, …, "n"}, i.e. permutations that alternately rise and fall, starting with a rise. For example, "u"4 = 5, because there are five permutations of {1, 2, 3, 4} satisfying these conditions, namely:
* 1, 3, 2, 4
* 1, 4, 2, 3
* 2, 3, 1, 4
* 2, 4, 1, 3
* 3, 4, 1, 2

The following figure illustrates the five alternating permutations of {1, 2, 3, 4} that begin with a rise:

The sequence of up/down numbers starts as follows:: u_0 = 1, u_1 = 1, u_2 = 1, u_3 = 2, u_4 = 5, u_5 = 16, u_6 = 61, ldots , This sequence is the boustrophedon transform of the unit sequence: 1, 0, 0, 0, ldots , For this reason, the up/down numbers are also called the "boustrophedon transform numbers".

The even up/down numbers are related to the Euler numbers E_n and the odd up/down numbers are related to the Bernoulli numbers B_n:: u_{2k} = (-1)^k E_{2k} qquad mbox{for } k=0,1,2,ldots, ,

: u_{2k-1} = frac{(-1)^{k-1} 4^k (4^k-1) B_{2k{2k} qquad mbox{for } k=1,2,3,ldots. ,

The exponential generating function

The exponential generating function of a sequence ("a""n") is defined by: EG(a_n;x)=sum _{n=0}^{infty} a_n frac{x^n}{n!}. The exponential generating function of the boustrophedon transform ("b""n") is related to that of the original sequence ("a""n") by: EG(b_n;x) = (sec x + an x) , EG(a_n;x).

The exponential generating function of the unit sequence is 1, so that of the up/down numbers is: EG(u_n;x) = sec x + an x = anleft({x over 2} + {pi over 4} ight). , This explains why the up/down numbers appear as the Taylor coefficients of the tangent and secant functions.


* Jessica Millar, N.J.A. Sloane, Neal E. Young, "A New Operation on Sequences: the Boustrouphedon Transform," "Journal of Combinatorial Theory, Series A," volume 76, number 1, pages 44–54, 1996. Also available in a slightly different version as e-print [ math.CO/0205218] on the arXiv.

External links

* Sequence on the On-Line Encyclopedia of Integer Sequences contains the up/down numbers.

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Boustrophedon — (pronEng|ˌbustroʊˈfiːdən; from Greek ox turning mdash;that is, turning like oxen in ploughing), is an ancient way of writing manuscripts and other inscriptions.Rather than going from left to right as in modern English, or right to left as in… …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Bernoulli number — In mathematics, the Bernoulli numbers Bn are a sequence of rational numbers with deep connections to number theory. They are closely related to the values of the Riemann zeta function at negative integers. There are several conventions for… …   Wikipedia

  • Alternating permutation — In combinatorial mathematics, an alternating permutation of the set {1, 2, 3, ..., n } is an arrangement of those numbers into an order c 1, ..., c n such that no element c i is between c i − 1 and c i + 1 for any value of i and c 1 lt; c 2.Let A …   Wikipedia

  • List of triangle topics — This list of triangle topics includes things related to the geometric shape, either abstractly, as in idealizations studied by geometers, or in triangular arrays such as Pascal s triangle or triangular matrices, or concretely in physical space.… …   Wikipedia

  • Triangular array — Not to be confused with Triangular matrix. The triangular array whose right hand diagonal sequence consists of Bell numbers In mathematics and computing, a triangular array of numbers, polynomials, or the like, is a doubly indexed sequence in… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.