cp's OEIS Frontend

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.

%I A357701 #21 Apr 22 2025 19:11:25
%S A357701 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,
%T A357701 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,
%U A357701 2,3,3,1,2,3,3,2,0,1,2,3,3,2,3,3,1,2,3,3,2,3,3
%N 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.
%C A357701 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.
%C A357701 Depth levels are distance down from the root, so 0 for the root itself, 1 for children of the root, and so on.
%C A357701 The pre-order traversal visits a vertex and then recursively traverses its "x" subtree followed by its "y" subtree.
%C A357701 The resulting depths vector is the lexicographically greatest among all possible orderings of siblings (as seen by induction).
%C A357701 Rows are in lexicographically increasing order (again by induction) so that an equivalent definition is greatest depths vectors in increasing order.
%C A357701 Row n has length A064002(n) which is the number of vertices.
%C A357701 Row n begins 0,1,2,...,h where h is the height of the tree, i.e. greatest depth of any vertex.
%H A357701 Kevin Ryde, <a href="/A357701/b357701.txt">Table of n, a(n) for rows 1..500, flattened</a>
%H A357701 Caroline Colijn and Giacomo Plazzotta, <a href="https://doi.org/10.1093/sysbio/syx046">A Metric on Phylogenetic Tree Shapes</a>, Systematic Biology, volume 67, number 1, January 2018, pages 113-126.
%H A357701 Kevin Ryde, <a href="/A357701/a357701.gp.txt">PARI/GP Code</a>
%F A357701 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).
%e A357701 Triangle begins:
%e A357701       k=1  2  3  4  5  6  7  8  9 10 11
%e A357701   n=1:  0,
%e A357701   n=2:  0, 1, 1,
%e A357701   n=3:  0, 1, 2, 2, 1,
%e A357701   n=4:  0, 1, 2, 2, 1, 2, 2,
%e A357701   n=5:  0, 1, 2, 3, 3, 2, 1,
%e A357701   n=6:  0, 1, 2, 3, 3, 2, 1, 2, 2,
%e A357701   n=7:  0, 1, 2, 3, 3, 2, 1, 2, 3, 3, 2,
%e A357701   n=8:  0, 1, 2, 3, 3, 2, 3, 3, 1,
%e A357701   n=9:  0, 1, 2, 3, 3, 2, 3, 3, 1, 2, 2,
%e A357701 For n=6, tree 6 is as follows, with vertices numbered by pre-order traversal (column number k),
%e A357701           1         depth=0
%e A357701         /   \
%e A357701       2       7     depth=1
%e A357701      / \     / \
%e A357701     3   6   8   9   depth=2
%e A357701    / \
%e A357701   4  5              depth=3
%e A357701   row(6) = depths 0,1,2,3,3,2,1,2,2
%t A357701 yList=FoldList[{#1,#2}&,1,Range[2,20]]//Flatten;x[n_]:=Floor[Sqrt[2*n]+1/2];y[n_]:=yList[[n]];row[1]={0};row[n_]:=row[n]={0}~Join~(row[x[n-1]]+1)~Join~(row[y[n-1]]+1);Flatten[Array[row,11]] (* _Shenghui Yang_, Apr 15 2025 *)
%o A357701 (PARI) \\ See links.
%Y A357701 Cf. A064002 (row lengths), A357702 (row sums).
%Y A357701 Cf. A002024 (larger child), A002260 (smaller child).
%K A357701 nonn,easy,tabf
%O A357701 1,7
%A A357701 _Kevin Ryde_, Oct 11 2022