SEQUENCES GENERATED BY
AGE-DETERMINED INSERTION TREES
John W. Layman
Math. Dept., Virginia Tech
<layman@math.vt.edu>
January, 2006
I. SIMPLE INSERTION TREES.
A. We first illustrate the general concept of an insertion tree by the following well-known example.
Start with the finite sequence (1,1) and successively form longer sequences by inserting their sum between each pair of adjacent terms. This produces a succession of sequences:
1 1
1 2 1
1 3 2 3 1
1 4 3 5 2 5 3 4 1
1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1
...
...
If we now omit the final 1 in each row and concatenate the rows in order, we obtain the initial terms of the sequence
1,1,2,1 3,2,3,1,4,3,5,2,5,3,4,1,5,4,7,3,8,5,7,2,7,5,8,3,7,4,5,...,
which is the Stern-Brocot tree sequence (OEIS A002487). If we denote the terms of this sequence by a(n), for n=0,1,2,..., then a(n) counts the number of representations of n by sums of powers of 2 with coefficients no larger than 2.
B. A second example of a sequence generated by a slightly modified form of a simple insertion tree without age-dependence is the following.
Start with (1,1) as the first row and construct successive rows according to the following rule: insert their sum between each pair of adjacent terms in the previous row, then replace each term of the previous row, with the exception of the final 1, by two copies of itself. This produces the tree of sequences:
1 1
1 1 2 1
1 1 2 1 1 3 2 2 3 1
1 1 2 1 1 3 2 2 3 1 1 2 1 1 4 3 3 5 2 2 4 2 2 5 3 3 4 1
...
...
Again omit the right-most 1 from each row and concatenate the rows to produce the sequence
1,1,1,2,1,1,2,1,1,3,2,2,3,1,1,2,1,1,3,2,2,3,1,1,2,1,1,4,3,3,5,2,2,4,2,2,5,3,3,4,...
It appears that this is the sequence of the number of representations of n by sums of powers of 3 with coefficients no larger than 3 for n=0,1,2,... This has been verified for n up to 3000. It appears in the OEIS as A054390.
II. AGE-DETERMINED INSERTION TREES.
A. We now consider that each term, in each of the successively generated finite sequences, has a "birthday" from which its "age" can be determined, and choose the insertion rule according to the ages of the terms. We illustrate by a simple example.
Again start with (1 1), both 1's being "born" on day 0. We now generate rows on successive days by using the following rule: if a term is not exactly 2 days old it is simply copied to the next row, but if it is exactly 2 days old (at day n, say) then it is not only copied to the next row but, in addition, 2 copies of the sum of that term and its nearest neighbor are inserted between the term and the neighbor, each inserted term having birthday n+1. This is done for both neighbors, except on day 2 when there is only one neighbor for each 1. So the following succession of sequences is generated:
Day 0: 1 1
Day 1: 1 1
Day 2: 1 2 2 1
Day 3: 1 2 2 1
Day 4: 1 3 3 2 4 4 2 3 3 1
Day 5: 1 3 3 2 4 4 2 3 3 1
Day 6: 1 4 4 3 6 6 3 5 5 2 6 6 4 8 8 4 6 6 2 5 5 3 6 6 3 4 4 1
Day 7: 1 4 4 3 6 6 3 5 5 2 6 6 4 8 8 4 6 6 2 5 5 3 6 6 3 4 4 1
...
...
If we again omit the 1 at the right end of each row and concatenate, we get
1,1,1,2,2,1,2,2,1,3,3,2,4,4,2,3,3,1,3,3,2,4,4,2,3,3,1,4,4,3,6,6,3,5,5,2,6,6,4,8,8,4,6,6,2,5,5,3,6,6,3,4,4,...
If we denote the terms of this sequence by a(n), for n=0,1,2,3,..., it appears that a(n) counts the number of representations of n by sums of powers of 3 with coefficients no larger that 4. This has been verified for n up to 2185.
B. Of particular interest is the fact that a sequence related to Fibonacci numbers can apparently be determined from the construction of an age-determined insertion tree, as shown below.
We consider the age-determined insertion tree constructed by initializating with the sequence (1,1), each term with age 2, and evolving according to the following three rules:
(1) If x is any term with age 1, then x "divides" into two copies x,x each assigned an age of 1.
(2) If x is any term with age 2, and y is a neighbor adjacent to x with x<>y, then x+y, assigned an age of 0, is inserted between x and y.
(3) If two copies of x, both of age 3, are adjacent, then 2x, assigned an age of 0, is inserted between the two x's.
We show the first few stages in detail. Start with (1,1) both 1's at age 2.
1 1 (both at age 2)
In the next row both adjacent terms x=1 are at age 3, so Rule 3 applies, and thus so 2, at age 0, is inserted between the two 1's, giving
1 1 ( both 1's at age 2)
1 2 1 (2 at age 0, 1's at age 3)
For the third row we have the 2 at age 1 and the 1's at age 4. Thus Rule 1 applies, so the 2 divides into two copies 2,2 and the list becomes
1 1 (both 1's at age 2)
1 2 1 (2 at age 0, 1's at age 3)
1 2 2 1 (2's at age 1, 1's at age 4)
For the 4th row the 2's have age 2 with 2<>1, so Rule 2 applies. Thus the sums 1+2 and 2+1 are inserted between 1,2 and 2,1, giving
1 1 (both 1's at age 2)
1 2 1 (2 at age 0, 1's at age 3)
1 2 2 1 (2's at age 1, 1's at age 4)
1 3 2 2 3 1 (2's age 2, 3 age 0)
In the 5th row the 3's are at age 1 so Rule 1 applies. Also, the 2's are at age 3 so Rule 3 applies as well. Thus each 3 divides into 3,3 and 2*2=4 is inserted betwee the two 2's, giving
1 1 (both 1's at age 2)
1 2 1 (2 at age 0, 1's at age 3)
1 2 2 1 (2's at age 1, 1's at age 4)
1 3 2 2 3 1 (2's age 2, 3 age 0)
1 3 3 2 4 2 3 3 1
Continuing this process gives:
1 1
1 2 1
1 2 2 1
1 3 2 2 3 1
1 3 3 2 4 2 3 3 1
1 4 3 3 5 2 4 4 2 5 3 3 4 1
1 4 4 3 6 3 5 5 2 6 4 4 6 2 5 5 3 6 3 4 4 1
...
...
Again we omit the 1 at the right end of each row and concatenate rows to get the sequence:
1,1,2,1,2,2,1,3,2,2,3,1,3,3,2,4,2,3,3,1,4,3,3,5,2,4,4,2,5,3,3,4,1,4,4,3,6,3,5,5,2,6,4,4,6,2,5,5,3,6,3,4,4,...
It appears that this sequence gives the count of the number of representations of n as a sum of distinct Fibonacci numbers for n=1,2,3,... (OEIS A000119). This has been verified for values of n up to 1500. We therefor conjecture that this particular age-determined insertion tree in fact determines A000119 for all n.
Created by Mathematica (March 25, 2006)