

A357701


Irregular triangle read by rows where row n is the vertex depths of the rooted binary tree with ColijnPlazzotta tree number n, traversed in preorder, numerically larger child first.


2



0, 0, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 2, 1, 2, 2, 0, 1, 2, 3, 3, 2, 1, 0, 1, 2, 3, 3, 2, 1, 2, 2, 0, 1, 2, 3, 3, 2, 1, 2, 3, 3, 2, 0, 1, 2, 3, 3, 2, 3, 3, 1, 0, 1, 2, 3, 3, 2, 3, 3, 1, 2, 2, 0, 1, 2, 3, 3, 2, 3, 3, 1, 2, 3, 3, 2, 0, 1, 2, 3, 3, 2, 3, 3, 1, 2, 3, 3, 2, 3, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,7


COMMENTS

Colijn and Plazzotta enumerate rooted binary trees (every vertex 0 or 2 children) by n=1 as a singleton or if n>1 then a root with child subtrees x = A002024(n1) and y = A002260(n1), which is y = 1..x for each successive x.
Depth levels are distance down from the root, so 0 for the root itself, 1 for children of the root, and so on.
The preorder traversal visits a vertex and then recursively traverses its "x" subtree followed by its "y" subtree.
The resulting depths vector is the lexicographically greatest among all possible orderings of siblings (as seen by induction).
Rows are in lexicographically increasing order (again by induction) so that an equivalent definition is greatest depths vectors in increasing order.
Row n has length A064002(n) which is the number of vertices.
Row n begins 0,1,2,...,h where h is the height of the tree, i.e. greatest depth of any vertex.


LINKS



FORMULA

row(n) = {0, row(x)+1, row(y)+1} for n>=2, where row(c)+1 means +1 on each term of row c, and where x = A002024(n1) and y = A002260(n1).


EXAMPLE

Triangle begins:
k=1 2 3 4 5 6 7 8 9 10 11
n=1: 0,
n=2: 0, 1, 1,
n=3: 0, 1, 2, 2, 1,
n=4: 0, 1, 2, 2, 1, 2, 2,
n=5: 0, 1, 2, 3, 3, 2, 1,
n=6: 0, 1, 2, 3, 3, 2, 1, 2, 2,
n=7: 0, 1, 2, 3, 3, 2, 1, 2, 3, 3, 2,
n=8: 0, 1, 2, 3, 3, 2, 3, 3, 1,
n=9: 0, 1, 2, 3, 3, 2, 3, 3, 1, 2, 2,
For n=6, tree 6 is as follows, with vertices numbered by preorder traversal (column number k),
1 depth=0
/ \
2 7 depth=1
/ \ / \
3 6 8 9 depth=2
/ \
4 5 depth=3
row(6) = depths 0,1,2,3,3,2,1,2,2


PROG

(PARI) See links.


CROSSREFS



KEYWORD

nonn,easy,tabf


AUTHOR



STATUS

approved



