++
 
 http://www.research.att.com/~njas/sequences/a080237tree.txt 
 
 Notes concerning the connections between the OEIS sequences A007001, 
 A080237, A080336, A076050, A085197 and A085193, 
 written by Antti Karttunen, 1618. June 2003. 
 
++
The sequence A007001 in OEIS is given as:
ID Number: A007001 (Formerly M0108)
URL: http://www.research.att.com/projects/OEIS?Anum=A007001
Sequence: 1,2,1,2,3,1,2,1,2,3,1,2,3,4,1,2,1,2,3,1,2,1,2,3,1,2,3,4,1,2,
1,2,3,1,2,3,4,1,2,3,4,5,1,2,1,2,3,1,2,1,2,3,1,2,3,4,1,2,1,2,
3,1,2,1,2,3,1,2,3,4,1,2,1,2,3,1,2,3,4,1,2,3,4,5,1,2,1,2,3,1,
2,1,2,3,1,2,3,4,1,2,1,2,3,1,2
Name: Generated by 1 > 12, 2 > 123, 3 > 1234, etc. starting from 1.
References S. Lehr, J. Shallit and J. Tromp, On the vector space of the
automatic reals, Theoret. Comput. Sci. 163 (1996), no. 12,
193210.
J. West, Generating trees and forbidden subsequences,
Proc. 6th FPSAC (1994), pp. 441450 (see p. 443).
etc.
but without reading e.g. West's or Banderier's articles, one might not see
that it actually hides a tree:
1
/ \
/ \
/ \
/ \
/ \
/ \
/ \
1 2
/ /\
/  /  \
/  /  \
/  /  \
1 2 1 2 3
/ ^ / ^ ^______
/  /\ /  /\ \\__ \
/  /  \ /  /  \  \ \ \
1 2 1 2 3 1 2 1 2 3 1 2 3 4
etc, ad infinitum, and the sequence A007001 consists of
the terms collected from the w:th level of this tree
(where "w" stands for the first transfinite ordinal).
Note that if we collect ALL the terms, starting from
the top and going down a level by level, we get
the sequence A080237 1,1,2,1,2,1,2,3,1,2,1,2,3,1,2,1,2,3,1,2,3,4,...
Benoit Cloitre gives a different definition for it:
"Start with 1 and apply the process: kth run is 1, 2, 3, .., a(k1)+1.",
but it's clear that we get the above tree with that process.
From now on, we call above tree as "A080237tree".
++
 
 Connection with A082315 and A085197. 
 
++
In March 15 2003 Wouter Meeussen notified me in a personal mail,
that if you take the permutation which is essentially a composition of
A082313 and A057164, (which has been submitted as A082315), and look
at each subpermutation in range [A014137(n1)..A014138(n1)] of it:
0,1, 2,3, 4,6,8,7,5, 9,11,14,16,19,21,22,18,17,20,13,12,10,15,...
1 23 48 922
with each of them "normalized" to begin from one by subtracting A014138(n2)
from the n:th subpermutation, to get:
1; 1,2; 1,3,5,4,2; 1,3,6,8,11,13,14,10,9,12,5,4,2,7;...
i.e. listed row by row as:
{1},
{1, 2},
{1, 3, 5, 4, 2},
{1, 3, 6, 8, 11, 13, 14, 10, 9, 12, 5, 4, 2, 7},
{1, 3, 6, 8, 11, 15, 17, 20, 22, 25, 29, 31, 34, 38, 36, 37, 40, 41, 42, 27,
28, 24, 23, 26, 33, 32, 35, 39, 13, 14, 10, 9, 12, 5, 4, 2, 7, 19, 18, 16,
21, 30},
{1, 3, 6, 8, 11, 15, 17, 20, 22, 25, 29, 31, 34, 38, 43, 45, 48, 50, 53, ...
etc, then each starts with cat[n1] integers of the previous permutation.
The repeating bit upto 42 integers is:
{1, 3, 6, 8, 11, 15, 17, 20, 22, 25, 29, 31, 34, 38, 43, 45, 48, 50, 53, 57,
59, 62, 64, 67, 71, 73, 76, 80, 85, 87, 90, 92, 95, 99, 101, 104, 108, 113,
115, 118, 122, 127,...... ;
which has been now been submitted to OEIS as A085197.
If one subtracts n from its each term, one obtains:
1,3,6,8,11,15,17,20,22,25,29,31,34,38,43,45,48,50,53,57,59,
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
= 0 1 3 4 6 9 10 12 13 15 18 19 21 24 28 29 31 32 34 37 38 (*).
the sequence which appears to be A080336, defined by
Benoit Cloitre as partial sums of A007001.
I prove that this indeed is the same sequence.
However, before completing the proof, I will call the
sequence (*) "the distance sequence", d(n), where n runs
from 0 onward.
For starters, we should know that the tree inherent in A007001/A080237
can be also used to construct all the parenthesizations
in the same lexicographic order as they are encoded by the
sequences A014486 and A063171:
(), ()(), (()), ()()(), ()(()), (())(), (()()), ((())),
()()()(), ()()(()), ()(())(), ()(()()), ()((())), (())()(),
(())(()), (()())(), (()()()), (()(())), ((()))(), ((())()),
((()())), (((()))), ...
The method is simple: traverse down from the root node at the top
to the desired node, and note the labels of the nodes encountered
in the process.
(A) If the label k of the node is one greater than the label
of its ancestor node above it, then add a pair of parentheses ()
INSIDE the pair added at the previous step (i.e. the rightmost
() in the parenthesization so far constructed).
(B) Otherwise add a pair of parentheses to the rightmost position
"at depth k" of the rightmost subparenthesization so far
constructed. If the label is 1, it means appending () to
the end of parenthesization at the "toplevel".
This illustration gives an example:
1=()
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
1=()() 2=(())
/ /\
/  /  \
/  /  \
/  /  \
/  /  \
/  /  \
/  /  \
/  /  \
/  /  \
1=()()() 2=()(()) 1=(())() 2=(()()) 3=((()))
/ ^ / ^ ^______
/  /\ /  /\ \\__ \
/  /  \ /  /  \  \ \ \
1 2 1 2 3 1 2 1 2 3 1 2 3 4= (((())))
            
            +> ((()()))
           
           +> ((())())
          
          +> ((()))()
         
         +> (()(()))
        
        +> (()()())
       
       +> (()())()
      
      +> (())(())
     
     +> (())()()
    
    +> ()((()))
   
   +> ()(()())
  
  +> ()(())()
 
 +> ()()(())

+> ()()()()
Now, A082315 is also a "square" of A057501, which is induced
in the following way by this simple Lisp/Scheme function:
(define (gma057501 s) (append (car s) (list (cdr s))))
To get an integer sequence 1,3,2,7,8,5,4,6,17,18,20,21,22,12,13,10,...
given in A057501, we let this function act on "symbolless Sexpressions"
( () ), ( ()() ), ( (()) ), ( ()()() ), ( ()(()) ), ( (())() ),
( (()()) ), ( ((())) ), ...
that are obtained from those encoded by A014486/A063171 (and present in
above triangle), by surrounding them with extra parentheses
to get a valid Lisp/Scheme list. Then, after obtaining the result
of gma057501, we remove the extra surrounding parentheses, and look up
the position of new parenthesization from A014486/A063171.
Above function maps ( ()() ) to ( (()) ) and vice versa,
thus A057501(2)=3 and A057501(3)=2.
If we do above mapping twice (i.e. the mapping given by A082315)
then if the argument list contains an empty pair of parentheses ()
as its first element, it is just transferred to the right of the
remaining elements.
E.g.
(gma057501 (gma057501 '(() (()) (() ()) ((())))))
gives the list ((()) (() ()) ((())) ()) as its value.
Note that the fact that "the subpermutations of A082315 each start with
cat[n1] integers of the previous subpermutation" follows from
the fact that (gma057501 (gma057501 '(() () rest)))
is equal to (cons '() (gma057501 (gma057501 '(() rest))))
i.e. if the parenthesization starts with _two_ (or more)
successive empty pair of parentheses (), then we get the
same result if we take the first pair off before we do our
operation, and only after then restore it back to the front.
So the sequence d(n) gives the difference of positions
of ()X and X() in A014486/A063171, where X runs through
() and all the parenthesizations which DO NOT begin with (),
and we should prove that the same holds for the sequence A080336.
Positions of such parenthesizations in A014486 is given by
A081291, and the distance between ()X and X() is given by A085196,
so we should have A080336(n) = A085196(A081291(n)).
We need to construct "w:th" level (where "w" stands for the first
transfinite ordinal) of the above tree in some finitist manner.
We do it like this: first grow from a root a branch of w ones:
1
/
.
. "w" ones.
.
/
1 (at the level "w").
then go back towards root one edge, and graft there the righthand
subtree of the tree A080237, extracted down to the depth 1, i.e.
\
2
to get:
1
/
.
. "w" ones.
1
/ \
1 2
then back up one more edge, and graft the the right the righthand
subtree of A080237tree, extracted down to the depth 2, i.e.
add
\
2
/\
1 2 3
to get:
1
/
.
. "w" ones.
1
/ \
1 2
/ /\
1 2 1 2 3
etc, ad infinitum, a level by level. Now it's clear that the
terms on the "w":th level of the A080237tree (i.e. the sequence A007001)
can also be collected by scanning the right hand side of
the tree in the simple lefttoright, breadthfirst fashion.
But it's just the sequence A081291 that gives the proper indices
(apart from its initial term) to the right hand side of the tree,
so A007001 can now be defined as:
A007001(1)=1 and for n>1 A007001(n) = A080237(A081291(n1))
The nodes at "w":th level correspond to parenthesizations
prefixed with an infinite number of empty pairs (),
and one has to mentally grab them from their rear end,
to preserve their distinct identity from each other.
Fortunately, transferring one pair of parentheses ()
from the front of such infinite head is equal to
much easier operation, that is picking up the
LAST () before the first non() part (i.e. part beginning
as ((.. ), and transferring it to the end of the whole
parenthesization, and this is just a corollary of
what we said above about how the doubleinvocation
of gma057501 works.
We can code any finite or infinite parenthesization as
a list of nodes needed to traverse in A080237tree
to reach the destination node.
Thus all parenthesizations at the level "w" are coded
as [1,...,1,rearend] where the number of 1's before
rearend is infinite, and rearend begins with a number
larger than one. After doing our operation, the code
changes to [1,...,1,rearend,1] and we note that
the relative lexicographic order between any two
parenthesizations does not change after such an operation.
So each parenthesization is moved to the next "available"
parenthesization that ends with (), i.e. one whose corresponding
node at the "w":th level of the tree is 1.
The leftmost 1 in A007001 corresponds to a parenthesization
composed solely of infinite number of ()'s, so it's position
doesn't change, and the distance function d(0) = 0.
A007001(2) = 2 corresponds to (()) prefixed with an infinite number of ()'s,
and it will change to (())() [prefixed with an infinite number of ()'s],
located at the next node, so d(1) = 1.
We see that
d(0) = 0
d(n) =
d(n1)
 1 [because we start one node right from the previous one]
+ distance from the previous 1 (used) to the next 1 (free)
But now it's time to notice that A007001 has a nice feature,
that if one counts the number of terms between successive 1's, as:
1,2,1,2,3,1,2,1,2,3,1,2,3,4,1,2,1,2,3,1,2,1,2,3,1,2,3,4,1,2,1,2,3,1,2,3,4,1,
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
1 2 1 2 3 1 2 1 2 3 1 2 3
one obtains A007001 again. (i.e. distance between successive 1's
is A007001(n)+1 = A076050(n)).
Why? Think about the two identical transfinite levels, the "w:th" and
"w+1:th" level in the above tree. Each node labeled k on the level "w"
has k+1 children on the level "w+1", of which the leftmost is 1, thus
there are just k nodes > 1 before the next 1.
Thus the above formula reduces to:
d(0) = 0
d(n) = d(n1) + A007001(n)
which is just a formula for the partial sums of A007001,
thus d(n) = A080336(n). QED.
++
 
 Formula for A085193. 
 
++
The same tree can also be used to reason about other related
sequences.
For example, I have defined A085193(n) as A085192(A081291(n+1)1)
where A085192(n) = A014486(n+1)A014486(n).
I.e., the sequence A085193 is the repeating part in the first
differences of A014486.
Now we replace the opening and closing parentheses with 1 and 0,
to see better how the terms of A014486/A063171 fit there.
By looking at the tree below it should be obvious that
A085193(n) = 4*A085193(A085182(n+1)1) + 2  (2^A007001(n+1))
if A007001(n+2)==1,
otherwise 2^A007001(n+1).
where A085182 is an onebased sequence beginning as:
1,1,2,2,2,3,3,4,4,4,5,5,5,5,6,6,7,7,7,8,8,9,9,9,...
and defined as "n occurs A076050(n) (= A007001(n)+1) times",
i.e. we can think it as an auxiliary sequence whose purpose is to
return the position of the ancestor node at the level "w"
of the A080237tree, for the node n at the "w+1:th" level.
1=10
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
1=1010 2=1100
/ /\
/  /  \
/  /  \
/  /  \
/  /  \
/  /  \
/  /  \
/  /  \
/  /  \
1=101010 2=101100 1=110010 2=110100 3=111000
/ ^ / ^ ^______
/  /\ /  /\ \\__ \
/  /  \ /  /  \  \ \ \
1 2 1 2 3 1 2 1 2 3 1 2 3 4= 11110000
            
            +> 11101000
           
           +> 11100100
          
          +> 11100010
         
         +> 11011000
        
        +> 11010100
       
       +> 11010010
      
      +> 11001100
     
     +> 11001010
    
    +> 10111000
   
   +> 10110100
  
  +> 10110010
 
 +> 10101100

+> 10101010