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.

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,2

Comments

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.

Links

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

Formula

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.

Example

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

Prog

(PARI) See links.
(R) See links.

Crossrefs

Cf. A356917 (subtree numbers).

Cf. A002024, A002260 (root subtrees).

Cf. A064002 (number of vertices).

Sequence in context: A341419 A366503 A185879 * A081880 A144289 A293815

Adjacent sequences: A356915 A356916 A356917 * A356919 A356920 A356921

Keyword

nonn,tabl

Author

Kevin Ryde, Sep 19 2022

Status

approved