+----------------------------------------------------------------------------+ | | | 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