- 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 inboustrophedon (zig-zag) manner.Definition
Given a sequence , the boustrophedon transform yields another sequence, , 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 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 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 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 .
Recurrence relation
A more formal definition uses a
recurrence relation . Define the numbers (with "k" ≥ "n" ≥ 0) by::Then the transformed sequence is defined by .The up/down numbers
The up/down numbers count the number of
alternating permutation s of the set {1, 2, 3, …, "n"}, i.e.permutation s 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, 2The 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::This sequence is the boustrophedon transform of the unit sequence:For this reason, the up/down numbers are also called the "boustrophedon transform numbers".
The even up/down numbers are related to the
Euler number s and the odd up/down numbers are related to theBernoulli number s :::
The exponential generating function
The
exponential generating function of a sequence ("a""n") is defined by:The exponential generating function of the boustrophedon transform ("b""n") is related to that of the original sequence ("a""n") by:The exponential generating function of the unit sequence is 1, so that of the up/down numbers is:This explains why the up/down numbers appear as the
Taylor coefficient s of the tangent and secant functions.References
* 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 [http://arxiv.org/abs/math.CO/0205218 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.