login
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.
2

%I #26 Dec 20 2024 10:45:21

%S 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,

%T 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,

%U 6,0,8,6,4,6,2,4,6,6,8,8,12,0

%N 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.

%C 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.

%C 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.

%C 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.

%C 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.

%C The main diagonal is T(n,n) = 0 which is distance 0 between n and itself.

%C As a flat sequence, a(m) is distance d_1 between the two child subtrees of the root in tree number m+1.

%H Kevin Ryde, <a href="/A356918/b356918.txt">Table of n, a(n) for rows 1..150, flattened</a>

%H Caroline Colijn, <a href="https://github.com/carolinecolijn/treetop/">Treetop</a>, R Code, see labeldistance() and distunlab().

%H 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, see section 2.3 d_1.

%H Kevin Ryde, <a href="/A356918/a356918.gp.txt">PARI/GP Code</a>

%F 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.

%e Triangle begins:

%e k=1 2 3 4 5 6 7 8

%e n=1: 0,

%e n=2: 2, 0,

%e n=3: 4, 2, 0,

%e n=4: 6, 4, 4, 0,

%e n=5: 6, 4, 2, 4, 0,

%e n=6: 8, 6, 4, 4, 4, 0,

%e n=7: 10, 8, 6, 6, 6, 4, 0,

%e n=8: 8, 6, 6, 2, 6, 4, 6, 0,

%e ...

%e 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.

%e n=68: 1,1,1,1,1,1, 2, 3, 5,12,68

%e k= 4: 1,1,1,1, 2,2, 4

%e diff: 1,1, 2, 3, 4, 5,12,68

%o (PARI) \\ See links.

%o (R) # See links.

%Y Cf. A356917 (subtree numbers).

%Y Cf. A002024, A002260 (root subtrees).

%Y Cf. A064002 (number of vertices).

%K nonn,tabl

%O 1,2

%A _Kevin Ryde_, Sep 19 2022