A064002 -id:A064002 - cp's OEIS frontend

A064064 n-th step is to add a(n) to each previous number a(k) (including itself, i.e., k <= n) to produce n+1 more terms of the sequence, starting with a(0)=1.

1, 2, 3, 4, 4, 5, 6, 5, 6, 7, 8, 5, 6, 7, 8, 8, 6, 7, 8, 9, 9, 10, 7, 8, 9, 10, 10, 11, 12, 6, 7, 8, 9, 9, 10, 11, 10, 7, 8, 9, 10, 10, 11, 12, 11, 12, 8, 9, 10, 11, 11, 12, 13, 12, 13, 14, 9, 10, 11, 12, 12, 13, 14, 13, 14, 15, 16, 6, 7, 8, 9, 9, 10, 11, 10, 11, 12, 13, 10, 7, 8, 9, 10, 10

Offset: 0

Henry Bottomley, Aug 31 2001

Each number eventually appears A001190 times (binary rooted trees can be constructed by combining earlier trees in a similar manner with the n-th tree having a(n) endpoints).

The number of leaves in the tree of rank n+1 according to the Colijn-Plazzotta ranking scheme for unlabeled binary rooted trees. - Noah A Rosenberg, Jun 14 2022

			Start with (1). So after initial step we have (*1*, 1+1 = 2), then (1, *2*, 1+2 = 3, 2+2 = 4), then (1, 2, *3*, 4, 1+3 = 4, 2+3 = 5, 3+3 = 6), then (1, 2, 3, *4*, 4, 5, 6, 1+4 = 5, 2+4 = 6, 3+4 = 7, 4+4 = 8), then (1, 2, 3, 4, *4*, 5, 6, 5, 6, 7, 8, 1+4 = 5, 2+4 = 6, 3+4 = 7, 4+4 = 8, 4+4 = 8), etc.

Rémy Sigrist, Table of n, a(n) for n = 0..10000
C. Colijn and G. Plazzotta, A Metric on Phylogenetic Tree Shapes, Systematic Biology, volume 67, number 1, January 2018, pages 113-126, with section 2.3 number of tips v_a(1) = a(n) for tree R_a = n+1.
N. A. Rosenberg, On the Colijn-Plazzotta numbering scheme for unlabeled binary rooted trees, Discr. Appl. Math. 291 (2021), 88-98.

Cf. A001190, A064065, A064066, A064067.

Cf. A002262, A003056, A064002.

a[0]=1; a[n_]:=With[{s = Floor[(Sqrt[8*n - 7] - 1)/2]}, a[s] + a[n - s*(s + 1)/2 - 1]]; Array[a,84,0] (* Harry Richman, Feb 24 2024 *)

a(n) = if (n==0, return (1), return (a(A002262(n-1))+a(A003056(n-1)))) \\ Rémy Sigrist, Aug 07 2017

a(0) = 1 and a(n+1) = a(A002262(n)) + a(A003056(n)) for any n >= 0. - Rémy Sigrist, Aug 07 2017

a(n) = (A064002(n+1) + 1)/2. - Kevin Ryde, Jul 22 2022

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.

Original entry on oeis.org

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

Kevin Ryde, Sep 19 2022

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.

			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

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

Cf. A002024, A002260 (root subtrees).
Cf. A064002 (number of vertices), A064064 (number of childless).
Cf. A356918 (d1 metric).

PARI
```
\\ See links.
```

row(n) = sort {row(x), row(y), n} for n>=2, where x = A002024(n-1) and y = A002260(n-1).

A356918 Triangle read by rows where T(n,k) is Colijn and Plazzotta's distance metric d_1(n,k) between rooted binary tree numbers n and k, for 1 <= k <= n.

Original entry on oeis.org

0, 2, 0, 4, 2, 0, 6, 4, 4, 0, 6, 4, 2, 4, 0, 8, 6, 4, 4, 4, 0, 10, 8, 6, 6, 6, 4, 0, 8, 6, 6, 2, 6, 4, 6, 0, 10, 8, 8, 4, 8, 6, 6, 4, 0, 12, 10, 8, 6, 8, 6, 6, 6, 4, 0, 14, 12, 12, 8, 12, 10, 10, 8, 6, 6, 0, 8, 6, 4, 6, 2, 4, 6, 6, 8, 8, 12, 0

Offset: 1

Kevin Ryde, Sep 19 2022

T(n,k) is the cardinality of the multiset symmetric difference ("XOR") between the subtree numbers in tree n, and in k, those being rows n and k of A356917.
A multiset symmetric difference discards copies of elements common to both sets, and keeps the excess copies which one of the multisets has over the other.
Equivalently, T(n,k) is the multi-dimensional Manhattan distance between vectors v_n and v_k where vector element v_t(s) is the number of occurrences of subtree number s in tree t.
Column k=1 it the distance to the singleton, which is a single subtree 1, so that T(n,1) = A064002(n) - 1 is the number of vertices of n except one 1.
The main diagonal is T(n,n) = 0 which is distance 0 between n and itself.
As a flat sequence, a(m) is distance d_1 between the two child subtrees of the root in tree number m+1.

			Triangle begins:
       k=1  2  3  4  5  6  7  8
  n=1:   0,
  n=2:   2, 0,
  n=3:   4, 2, 0,
  n=4:   6, 4, 4, 0,
  n=5:   6, 4, 2, 4, 0,
  n=6:   8, 6, 4, 4, 4, 0,
  n=7:  10, 8, 6, 6, 6, 4, 0,
  n=8:   8, 6, 6, 2, 6, 4, 6, 0,
  ...
For n=68,k=4, rows 68 and 4 from A356917 are as follows and their multiset symmetric difference has T(68,4) = 8 terms.
  n=68:  1,1,1,1,1,1, 2,   3,    5,12,68
  k= 4:  1,1,1,1,     2,2,    4
  diff:          1,1,   2, 3, 4, 5,12,68

Kevin Ryde, Table of n, a(n) for rows 1..150, flattened
Caroline Colijn, Treetop, R Code, see labeldistance() and distunlab().
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 d_1.
Kevin Ryde, PARI/GP Code

Cf. A356917 (subtree numbers).
Cf. A002024, A002260 (root subtrees).
Cf. A064002 (number of vertices).

PARI
```
\\ See links.
```
R
```
# See links.
```

T(n,k) = Sum_{s = subtree numbers in n or k} abs(v_n(s) - v_k(s)) where v_t(s) is the number of times s occurs in row t of A356917.

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.

Original entry on oeis.org

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

Offset: 1

Kevin Ryde, Oct 11 2022

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.

			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

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.
Kevin Ryde, PARI/GP Code

Cf. A064002 (row lengths), A357702 (row sums).

Cf. A002024 (larger child), A002260 (smaller child).

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 *)

PARI
```
\\ See links.
```

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).

A357702 Path length (total depths of vertices) of the rooted binary tree with Colijn-Plazzotta tree number n.

Original entry on oeis.org

0, 2, 6, 10, 12, 16, 22, 18, 22, 28, 34, 20, 24, 30, 36, 38, 26, 30, 36, 42, 44, 50, 34, 38, 44, 50, 52, 58, 66, 28, 32, 38, 44, 46, 52, 60, 54, 34, 38, 44, 50, 52, 58, 66, 60, 66, 42, 46, 52, 58, 60, 66, 74, 68, 74, 82, 50, 54, 60, 66, 68, 74, 82, 76, 82, 90

Offset: 1

Kevin Ryde, Oct 11 2022

In a rooted binary tree each vertex has 0 or 2 children.

All terms are even since each pair of 2 child vertices are at the same depth.

			For n=3, tree number 3 and the depth of each of its vertices is
      0  root
     / \
    1   1      total depths
   / \         a(3) = 0 + 1+1 + 2+2 = 6
  2   2

Kevin Ryde, PARI/GP Code

Cf. A357701 (vertex depths), A064002 (number of vertices).
Cf. A002024, A002260.
Cf. A196047 (in Matula-Goebel).

PARI
```
\\ See links.
```

a(n) = a(x) + a(y) + A064002(n) - 1, for n>=2, where x = A002024(n-1) and y = A002260(n-1).

cp's OEIS Frontend

A064064 n-th step is to add a(n) to each previous number a(k) (including itself, i.e., k <= n) to produce n+1 more terms of the sequence, starting with a(0)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A356918 Triangle read by rows where T(n,k) is Colijn and Plazzotta's distance metric d_1(n,k) between rooted binary tree numbers n and k, for 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

R

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A357702 Path length (total depths of vertices) of the rooted binary tree with Colijn-Plazzotta tree number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula