login
A354970
Smallest value of the Colijn-Plazzotta rank among n-leaved unlabeled binary rooted trees.
1
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
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
A354970_list = list(islice(A354970_gen(), 40)) # Chai Wah Wu, Jun 17 2022
(PARI) \\ See links.
CROSSREFS
Sequence in context: A259625 A068713 A218549 * A099523 A049806 A158381
KEYWORD
nonn
AUTHOR
Noah A Rosenberg, Jun 14 2022
STATUS
approved