+----------------------------------------------------------------------------+
|                                                                            |
| http://silk.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, 16-18. June 2003.                              |
|                                                                            |
+----------------------------------------------------------------------------+
   
  The sequence A007001 in OEIS is given as:
   
  ID Number: A007001 (Formerly M0108)
  URL:       http://silk.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. 1-2,
                193-210.
             J. West, Generating trees and forbidden subsequences,
                Proc. 6th FPSAC (1994), pp. 441-450 (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: k-th run is 1, 2, 3, .., a(k-1)+1.",
  but it's clear that we get the above tree with that process.
  From now on, we call above tree as "A080237-tree".

  
+----------------------------------------------------------------------------+
|                                                                            |
| 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(n-1)..A014138(n-1)] 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  2-3  4-------8  9-------------------------------------22
  
  with each of them "normalized" to begin from one by subtracting A014138(n-2)
  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[n-1] 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 "top-level".

  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 S-expressions"
   ( () ), ( ()() ), ( (()) ), ( ()()() ), ( ()(()) ), ( (())() ),
   ( (()()) ), ( ((())) ), ...
  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[n-1] 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 right-hand
  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 right-hand
  subtree of A080237-tree, 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 A080237-tree (i.e. the sequence A007001)
  can also be collected by scanning the right hand side of
  the tree in the simple left-to-right, breadth-first 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(n-1))

  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 double-invocation
  of gma057501 works.

  We can code any finite or infinite parenthesization as
  a list of nodes needed to traverse in A080237-tree
  to reach the destination node.
  Thus all parenthesizations at the level "w" are coded
  as [1,...,1,rear-end] where the number of 1's before
  rear-end is infinite, and rear-end begins with a number
  larger than one. After doing our operation, the code
  changes to [1,...,1,rear-end,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(n-1)
        - 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(n-1) + 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 one-based 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 A080237-tree, 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