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.

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

Kevin Ryde, Table of n, a(n) for rows 1..500, flattened

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

Adjacent sequences: A356914 A356915 A356916 * A356918 A356919 A356920

Keyword

nonn,easy,tabf

Author

Kevin Ryde, Sep 19 2022

Status

approved