login
A356917
Irregular triangle read by rows where row n lists the Colijn-Plazzotta subtree numbers, in ascending order, of each vertex of the rooted binary tree with their tree number n.
2
1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 1, 2, 2, 4, 1, 1, 1, 1, 2, 3, 5, 1, 1, 1, 1, 1, 2, 2, 3, 6, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 7, 1, 1, 1, 1, 1, 2, 2, 4, 8, 1, 1, 1, 1, 1, 1, 2, 2, 2, 4, 9, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 3, 4, 10, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 11
OFFSET
1,4
COMMENTS
Colijn and Plazzotta enumerate rooted binary trees (every vertex 0 or 2 children) by n=1 as a singleton and thereafter tree n is a root with child subtrees x = A002024(n-1) and y = A002260(n-1).
Each row starts with 1's for the childless vertices (A064064(n) of them).
Each row ends with n itself (the tree root).
The second last term in each row is the numerically largest subtree of the root, which is x.
Row lengths are A064002(n), the number of vertices.
LINKS
Caroline Colijn and Giacomo Plazzotta, A Metric on Phylogenetic Tree Shapes, Systematic Biology, volume 67, number 1, January 2018, pages 113-126, see section 2.3 where their L_n = row n here.
Kevin Ryde, PARI/GP Code
FORMULA
row(n) = sort {row(x), row(y), n} for n>=2, 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: 1,
n=2: 1, 1, 2,
n=3: 1, 1, 1, 2, 3,
n=4: 1, 1, 1, 1, 2, 2, 4,
n=5: 1, 1, 1, 1, 2, 3, 5,
n=6: 1, 1, 1, 1, 1, 2, 2, 3, 6,
n=7: 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 7,
n=8: 1, 1, 1, 1, 1, 2, 2, 4, 8,
Tree n=6 and its subtree numbers are as follows and row 6 is these subtree numbers in ascending order.
6 root
/ \
3 2
/ \ / \
2 1 1 1
/ \
1 1
PROG
(PARI) See links.
CROSSREFS
Cf. A002024, A002260 (root subtrees).
Cf. A064002 (number of vertices), A064064 (number of childless).
Cf. A356918 (d1 metric).
Sequence in context: A304495 A175069 A245563 * A122945 A209972 A205573
KEYWORD
nonn,easy,tabf
AUTHOR
Kevin Ryde, Sep 19 2022
STATUS
approved