login
A358372
Number of nodes in the n-th standard ordered rooted tree.
18
1, 2, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 6, 6, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 5, 6, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 7, 7, 8, 8, 8, 8, 8
OFFSET
1,2
COMMENTS
We define the n-th standard ordered rooted tree to be obtained by taking the (n-1)-th composition in standard order (graded reverse-lexicographic, A066099) as root and replacing each part with its own standard ordered rooted tree. This ranking is an ordered variation of Matula-Goebel numbers, giving a bijective correspondence between positive integers and unlabeled ordered rooted trees.
EXAMPLE
The standard ordered rooted tree ranking begins:
1: o 10: (((o))o) 19: (((o))(o))
2: (o) 11: ((o)(o)) 20: (((o))oo)
3: ((o)) 12: ((o)oo) 21: ((o)((o)))
4: (oo) 13: (o((o))) 22: ((o)(o)o)
5: (((o))) 14: (o(o)o) 23: ((o)o(o))
6: ((o)o) 15: (oo(o)) 24: ((o)ooo)
7: (o(o)) 16: (oooo) 25: (o(oo))
8: (ooo) 17: ((((o)))) 26: (o((o))o)
9: ((oo)) 18: ((oo)o) 27: (o(o)(o))
For example, the 25th ordered tree is (o,(o,o)) because the 24th composition is (1,4) and the 3rd composition is (1,1). Hence a(25) = 5.
MATHEMATICA
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
srt[n_]:=If[n==1, {}, srt/@stc[n-1]];
Table[Count[srt[n], _, {0, Infinity}], {n, 100}]
CROSSREFS
The triangle counting trees by leaves is A001263, unordered A055277.
The version for unordered trees is A061775, leaves A109129, edges A196050.
The leaves are counted by A358371.
A000081 counts unlabeled rooted trees, ranked by A358378.
A358374 ranks ordered identity trees, counted by A032027.
A358375 ranks ordered binary trees, counted by A126120
Sequence in context: A255402 A230411 A358551 * A029128 A303660 A290021
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 14 2022
STATUS
approved