Sequences A052154 and A137560: Coefficients of Lemniscates for Mandelbrot Set, or Binary Trees of Limited Height

Sloane's A052154 and A137560 give the coefficients of the lemniscates of z→z²+c, a series of polynomials in one complex variable which converge on the boundary of the Mandelbrot set.

Contents

Sequence Terms and Arrangement in a Triangle
Mandelbrot Set Interpretations
Relation to Divisions of a Line Segment
Relation to Binary Trees

Ways to Arrange the Terms

This sequence is most naturally interpreted as a two-dimensional array kind of like a triangle with rows that double in length with each row. The OEIS includes two alternative arrangements of these terms into a linear sequence.

Sequence A052154 is:

1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 2, 0, 0, 1, 1, 2, 1, 0, 0, 1, 1, 2, 5, 0, 0, 0, 1, 1, 2, 5, 6, 0, 0, 0, 1, 1, 2, 5, 14, 6, 0, 0, 0, 1, 1, 2, 5, 14, 26, 4, 0, 0, 0, 1, 1, 2, 5, 14, 42, 44, 1, 0, 0, 0, 1, 1, 2, 5, 14, 42, 100, 69, 0, 0, 0, 0, ...

In A052154, the sequence is given by "antidiagonals", a series of diagonals beginning at the top-left of the table, read from bottom-left to top-right. The order is illustrated by the order of the letters in this diagram:

A C F J O
B E I N
D H M
G L
K (etc.)

so the table of coefficients looks like this:

1 0 0 0   0 0 0 0 0 ...
1 1 0 0   0 0 0 0 ...
1 1 2 1   0 0 0 ...
1 1 2 5   6 6 ...
1 1 2 5 14 ...
1 1 2 5 ...
1 1 2 ...
1 1 ...
1 ...

Therefore the sequence, read by antidiagonals, is: 1, 1,0, 1,1,0, 1,1,0,0, 1,1,2,0,0, 1,1,2,1,0,0, ...

The coefficients are given in a more intuitive row-by-row order in Sloane's sequence A137560 (which includes only one 0 for each row starting with the 2^nd row):

1, 0, 1, 0, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 5, 6, 6, 4, 1, 0, 1, 1, 2, 5, 14, 26, 44, 69, 94, 114, 116, 94, 60, 28, 8, 1, 0, 1, 1, 2, 5, 14, 42, 100, 221, 470, 958, 1860, 3434, 6036, 10068, 15864, 23461, 32398, 41658, 49700, 54746, 55308, 50788, 41944, 30782, 19788, ...

With this ordering, the table of coefficients looks like this:

1
0 1 1
0 1 1 2 1
0 1 1 2 5 6 6 4
0 1 1 2 5 14 26 44 69 94 114 116 94 60 28 8 1
(etc.)

The lemniscate polynomials are:

1
0 + C
0 + C + C²
0 + C + C² + 2 C³ + C⁴
0 + C + C² + 2 C³ + 5 C⁴ + 6 C⁵ + 6 C⁶ + 4 C⁷ + C⁸

Computing the Sequence

This article gives Maxima and PARI/GP code to calculate the polynomials and/or their coefficients.

Relation to the Mandelbrot Set

The relationship of these polynomials to the Mandelbrot set is discussed on this page.

Relation to Divisions of a Line Segment

The coefficients also enumerate the ways to divide a line segment into at most j pieces, with 1 ≤ j ≤ 2^N-1, in which every piece is a power of two in size (so 1/4 is allowed but 1/5 and 3/8 are not), no piece is less than 1/2^N-1 of the whole, and every piece is aligned on a power of 2 boundary (so 1/4+1/2+1/4=1 is not allowed). This is discussed in the context of the question "How many possible musical melodies are there?" in this E2 article. (In the article, the author considers rhythms in a 32-beat measure that do not involve dotted notes, syncopation, or triplets.)

Here are some illustrations showing line segments divided in this way for N=1 through N=4:

j=1 N=1 |--| j=1 j=2 N=2 |---| |-|-| j=1 j=2 j=3 j=4 N=3 |-------| |---|---| |-|-|---| |-|-|-|-| |---|-|-| N=4 j=1 j=2 j=3 j=4 |---------------| |-------|-------| |---|---|-------| |---|---|---|---| |-------|---|---| |-|-|---|-------| |---|-|-|-------| |-------|-|-|---| |-------|---|-|-| j=5 j=6 j=7 j=8 |-|-|---|---|---| |-|-|-|-|---|---| |-|-|-|-|-|-|---| |-|-|-|-|-|-|-|-| |---|-|-|---|---| |-|-|---|-|-|---| |-|-|-|-|---|-|-| |---|---|-|-|---| |-|-|---|---|-|-| |-|-|---|-|-|-|-| |---|---|---|-|-| |---|-|-|-|-|---| |---|-|-|-|-|-|-| |-|-|-|-|-------| |---|-|-|---|-|-| |-------|-|-|-|-| |---|---|-|-|-|-|

Here the coefficients appear in the opposite order than that shown above: for N=3 we get 1,1,2,1 and for N=4 we get 1,1,2,5,6,6,4,1.

Relation to Binary Trees

Each divided line segment above can be constructed by starting with a single undivided segment, then dividing it in half, then dividing one of the 2 pieces in half, then dividing one of the 3 pieces in half, and so on, stopping after having performed N-1 divisions. We keep the requirement that every segment is no smaller than a certain minimum size.

The choices that were made during such a process can be expressed by a binary tree, with j terminal (leaf) nodes representing the segments and other nodes representing the divisions. The "height" of the tree corresponds to the size of the smallest segment. It is fairly easy to see that there is a distinct divided line segment for each binary tree and vice-versa. Thus, the lemniscate coefficients count the number of binary trees with exactly j leaf nodes and a height no greater than N:

j=1 N=1 o j=1 j=2 N=2 o * / \ o o j=1 j=2 j=3 j=4 N=3 o * * * * / \ / \ / \ / \ o o * o o * * * / \ / \ / \ / \ o o o o o o o o j=1 j=2 j=3 N=4 o * * * / \ / \ / \ o o * o o * / \ / \ o o o o j=4 * * * * * / \ / \ / \ / \ / \ * * * o * o o * o * / | | \ / \ / \ / \ / \ o o o o * o o * * o o * / \ / \ / \ / \ o o o o o o o o j=5 * * * * * * / \ / \ / \ / \ / \ / \ * * * * * * * * * o o * / | | \ / \ | \ / | / \ / | | \ / \ / \ * o o o o * o o o o * o o o o * * * * * / \ / \ / \ / \ / | | \ / | | \ o o o o o o o o o o o o o o o o j=6 * * * * * * / \ / \ / \ / \ / \ / \ * * * * * * * * * * * * / \ | \ / \ | \ / \ | \ / \ | \ / \ | \ / | / \ * * o o * o * o * o o * o * * o o * o * o o * * / | | \ / \ / \ / \ / \ / | | \ / \ | \ / | | \ o o o o o o o o o o o o o o o o o o o o o o o o j=7 * * * * / \ / \ / \ / \ * * * * * * * * / | | \ / | | \ / | | \ / | | \ * * * o * * o * * o * * o * * * /| | \ / | /| | \ |\ /| / | |\ | \ / | |\ o o o o o o o o o o o o o o o o o o o o o o o o j=8 * / \ * * / | | \ * * * * / | | \ / | | \ o o o o o o o o

Some other sequences are discussed here.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2011 May 10.

s.27