

A296689


Let phi be the onetoone mapping between binary trees and natural numbers described in the Tychonievich link. Let a(n) = min({phi^{1}(t) size(t)=n}); i.e., a(n) is the rank  starting from 0  of the first tree the size of which is n.


1



0, 1, 2, 4, 7, 13, 24, 30, 54, 64, 124, 244, 383, 503, 981, 1021, 1981, 3901, 6137, 8057, 13649, 16369, 32689, 65329, 98230, 130870, 229312, 261952, 491516, 524156, 1046388, 1048564, 2093044, 4182004, 8359924, 16715764, 25141220, 33497060, 58703812, 67059652, 125828996, 134184836, 259487492, 268435204, 536866564, 1073729284
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Let v(n) = max({phi^{1}(t) size(t)=n}); v(n) is already known as A072639.
The interleaving process used by Tychonievich is not specific to base 2, each base b>=3 giving birth to a new a(n)like sequence and a new v(n)like sequence.
The treeenumeration scheme of Tychonievich is similar, but not the same as "Recursive binary interleaving of binary trees" mentioned at my OEIS Wiki notes about Alternative Catalan Orderings. On the other hand, it seems to be the same (possibly up to the reflection of binary trees) as the ranking/unranking scheme mentioned in the section "Binary tree encoding with bijection" and in sequences A072634  A072637 that are permutations of nonnegative integers induced by crossranking binary trees between such a "dense" binary interleaving ranking system and the standard lexicographic ordering of them (A014486).  Antti Karttunen, Dec 20 2017


LINKS



PROG

(OCaml)
let rec evenOdd=function(*Luther Tychonievich decomposition*)
 n when n<=1 > n, 0
 n > let ev, od=evenOdd(n/2) in
2*od+n mod 2, ev
let rec cardImage=function
 n when n<=1 > n
 n > let ev, od=evenOdd(n1) in 1+cardImage(ev)+cardImage(od)
let checkCatalanBis n=(*why 2*n+1 ? empirical...*)
let (first, last)=(Array.make (2*n+1) 0, Array.make (2*n+1) 0) in
for i=0 to 1 lsl n do
let cai=cardImage i in
last.(cai)<1+last.(cai);
if first.(cai)=0 then first.(cai)<i done;
(first, last)
(Python)
def dei(n):
n1 = n2 = 0
bit = 1
while n:
if n&1:
n1 += bit
n >>= 1
if n&1:
n2 += bit
n >>= 1
bit <<= 1
return (n1, n2)
r = [0]
for n in range(1, 100):
r.append(1 + sum(r[x] for x in dei(n1)))
print([r.index(x) for x in range(max(r)+1)])


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



