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
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
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
(PARI) \\ See links.
CROSSREFS
KEYWORD
nonn
AUTHOR
Noah A Rosenberg, Jun 14 2022
STATUS
approved