cp's OEIS Frontend

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

%I A354970 #28 Jul 23 2024 10:24:19
%S A354970 1,2,3,4,6,7,10,11,20,22,28,29,53,56,66,67,202,211,252,254,401,407,
%T A354970 435,436,1408,1432,1594,1597,2202,2212,2278,2279,20369,20504,22358,
%U A354970 22367,31838,31879,32384,32386,80455,80602,83023,83029,94803,94831,95266,95267
%N A354970 Smallest value of the Colijn-Plazzotta rank among n-leaved unlabeled binary rooted trees.
%C A354970 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.
%H A354970 C. Colijn and G. Plazzotta, <a href="https://doi.org/10.1093/sysbio/syx046">A metric on phylogenetic tree shapes</a>, Syst. Biol., 67 (2018), 113-126.
%H A354970 Michael R. Doboli, Hsien-Kuei Hwang, and Noah A. Rosenberg, <a href="https://doi.org/10.4230/LIPIcs.AofA.2024.18">Periodic Behavior of the Minimal Colijn-Plazzotta Rank for Trees with a Fixed Number of Leaves</a>, 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).
%H A354970 N. A. Rosenberg, <a href="https://doi.org/10.1016/j.dam.2020.11.021">On the Colijn-Plazzotta numbering scheme for unlabeled binary rooted trees</a>, Discr. Appl. Math., 291 (2021), 88-98.
%H A354970 Kevin Ryde, <a href="/A354970/a354970.gp.txt">PARI/GP Code</a>
%F A354970 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.
%p A354970 a := proc(n) option remember; local r, h; if n = 1 then 1 else
%p A354970 r := irem(n, 2); h := a((n + r)/2); (h^2 - h)/2 + a((n - r)/2) + 1 fi end:
%p A354970 seq(a(n), n = 1..48); # _Peter Luschny_, Jun 15 2022
%t A354970 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]];
%t A354970 Table[a[n], {n, 1, 48}] (* _Jean-François Alcover_, Nov 08 2023, after _Peter Luschny_ *)
%o A354970 (Python)
%o A354970 from collections import deque
%o A354970 from itertools import islice
%o A354970 def A354970_gen(): # generator of terms
%o A354970     aqueue, f, a, b = deque([]), False, 1, 2
%o A354970     yield from (1,2)
%o A354970     while True:
%o A354970         c = b*(b-1)//2+1+(b if f else a)
%o A354970         yield c
%o A354970         aqueue.append(c)
%o A354970         if f: a, b = b, aqueue.popleft()
%o A354970         f = not f
%o A354970 A354970_list = list(islice(A354970_gen(),40)) # _Chai Wah Wu_, Jun 17 2022
%o A354970 (PARI) \\ See links.
%Y A354970 Cf. A001190, A108225.
%K A354970 nonn
%O A354970 1,2
%A A354970 _Noah A Rosenberg_, Jun 14 2022