A354970 Smallest value of the Colijn-Plazzotta rank among n-leaved unlabeled binary rooted trees.

1, 2, 3, 4, 6, 7, 10, 11, 20, 22, 28, 29, 53, 56, 66, 67, 202, 211, 252, 254, 401, 407, 435, 436, 1408, 1432, 1594, 1597, 2202, 2212, 2278, 2279, 20369, 20504, 22358, 22367, 31838, 31879, 32384, 32386, 80455, 80602, 83023, 83029, 94803, 94831, 95266, 95267

Offset: 1

Author

Noah A Rosenberg, Jun 14 2022

Keywords

• nonn

Comments

a(n) gives the rank of the unlabeled binary rooted tree, among those with n leaves, that has the smallest rank according to the bijection of Colijn and Plazzotta (2018) between unlabeled binary rooted trees and positive integers.

Links

• C. Colijn and G. Plazzotta, A metric on phylogenetic tree shapes, Syst. Biol., 67 (2018), 113-126.
• Michael R. Doboli, Hsien-Kuei Hwang, and Noah A. Rosenberg, Periodic Behavior of the Minimal Colijn-Plazzotta Rank for Trees with a Fixed Number of Leaves, In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 18:1-18:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2024).
• N. A. Rosenberg, On the Colijn-Plazzotta numbering scheme for unlabeled binary rooted trees, Discr. Appl. Math., 291 (2021), 88-98.
• Kevin Ryde, PARI/GP Code

Crossrefs

Cf. A001190, A108225.

Programs

Maple

a := proc(n) option remember; local r, h; if n = 1 then 1 else
r := irem(n, 2); h := a((n + r)/2); (h^2 - h)/2 + a((n - r)/2) + 1 fi end:
seq(a(n), n = 1..48); # Peter Luschny, Jun 15 2022

Mathematica

a [n_] := a[n] = Module[{r, h}, If[ n == 1, 1, r = Mod[n, 2]; h = a[(n+r)/2]; (h^2-h)/2 + a[(n-r)/2] + 1]];
Table[a[n], {n, 1, 48}] (* Jean-François Alcover, Nov 08 2023, after Peter Luschny *)

PARI

\\ See links.

Python

from collections import deque
from itertools import islice
def A354970_gen(): # generator of terms
    aqueue, f, a, b = deque([]), False, 1, 2
    yield from (1,2)
    while True:
        c = b*(b-1)//2+1+(b if f else a)
        yield c
        aqueue.append(c)
        if f: a, b = b, aqueue.popleft()
        f = not f
A354970_list = list(islice(A354970_gen(),40)) # Chai Wah Wu, Jun 17 2022

Formula

a(n) = a(n/2)*(a(n/2)-1)/2 + 1 + a(n/2) for even n; a(n) = a((n+1)/2)*(a((n+1)/2)-1)/2 + 1 + a((n-1)/2) for odd n>1; a(1)=1.