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

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

Table of n, a(n) for n=1..48.

C. Colijn and G. Plazzotta, A metric on phylogenetic tree shapes, Syst. Biol., 67 (2018), 113-126.

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

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.

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

Prog

(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
(PARI) See links.

Crossrefs

Cf. A001190, A108225.

Sequence in context: A259625 A068713 A218549 * A099523 A049806 A158381

Adjacent sequences: A354967 A354968 A354969 * A354971 A354972 A354973

Keyword

nonn

Author

Noah A Rosenberg, Jun 14 2022

Status

approved