login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A357701 Irregular triangle read by rows where row n is the vertex depths of the rooted binary tree with Colijn-Plazzotta tree number n, traversed in pre-order, 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(n-1) and y = A002260(n-1), 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 pre-order 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
Caroline Colijn and Giacomo Plazzotta, A Metric on Phylogenetic Tree Shapes, Systematic Biology, volume 67, number 1, January 2018, pages 113-126.
Kevin Ryde, PARI/GP Code
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(n-1) and y = A002260(n-1).
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 pre-order 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
Cf. A064002 (row lengths), A357702 (row sums).
Cf. A002024 (larger child), A002260 (smaller child).
Sequence in context: A293680 A293539 A292469 * A307011 A285007 A194527
KEYWORD
nonn,easy,tabf
AUTHOR
Kevin Ryde, Oct 11 2022
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 20 23:17 EDT 2024. Contains 374461 sequences. (Running on oeis4.)