cp's OEIS Frontend

A306390 Size of one subtree in the unlabeled binary rooted tree shape of size n whose leaf-labeled trees have the largest number of coalescence sequences.

%I A306390 #24 Apr 12 2025 06:29:47
%S A306390 1,2,2,2,4,4,4,4,4,4,8,8,8,8,8,8,8,8,8,8,8,8,16,16,16,16,16,16,16,16,
%T A306390 16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,32,32,32,32,32,32,32,
%U A306390 32,32,32,32,32,32,32,32,32,32,32,32,32
%N A306390 Size of one subtree in the unlabeled binary rooted tree shape of size n whose leaf-labeled trees have the largest number of coalescence sequences.
%C A306390 Consider the unlabeled, rooted, binary tree shapes (A001190). For each unlabeled shape, assign a labeling of the leaves: a labeled topology. This topology is a leaf-labeled, rooted, binary tree (chosen from among all such trees, A001147). From among the set of possible coalescence sequences (A006472), count all coalescence sequences, or labeled histories, that give rise to the specified labeled topology. For the unlabeled shape of size n whose labeled topologies have the largest number of coalescence sequences, the two subtrees immediately descended from the root have sizes a(n) and n-a(n) (Harding 1971, Eq. 5.7).
%C A306390 The decomposition of trees of n leaves into subtrees with sizes a(n) and n-a(n) also describes the set of unlabeled tree shapes whose labeled topologies have the largest number of root ancestral configurations (Disanto & Rosenberg 2017, Proposition 4).
%H A306390 E. H. Dickey and N. A. Rosenberg, <a href="https://doi.org/10.1098/rstb.2023.0307">Labelled histories with multifurcation and simultaneity</a>, Phil. Trans. R. Soc. B 380 (2025), 20230307. (see Theorem 4)
%H A306390 F. Disanto and N. A. Rosenberg, <a href="https://doi.org/10.1089/cmb.2016.0159">Enumeration of ancestral configurations for matching gene trees and species trees</a>, J. Comput. Biol. 24 (2017), 831-850.
%H A306390 E. F. Harding, <a href="https://doi.org/10.2307/1426329">The probabilities of rooted tree-shapes generated by random bifurcation</a>, Adv. Appl. Prob. 3 (1971), 44-77.
%F A306390 a(n) = 2^(1 + floor(log_2((n-1)/3))).
%e A306390 For n=5, the three unlabeled shapes are ((((.,.),.),.),.), (((.,.),(.,.)),.), and (((.,.),.),(.,.)). The formula gives a(5)=2, so that the shape with a subtree of size 2, (((.,.),.),(.,.)), is the one whose labeled topologies have the largest number of coalescence sequences. A labeled topology (((A,B),C),(D,E)) has 3 coalescence sequences, whereas ((((A,B),C),D),E) has 1 and (((A,B),(C,D)),E) has 2.
%t A306390 Table[2^(1 + Floor[Log2[(n - 1)/3]]), {n, 3, 100}]
%o A306390 (PARI) a(n) = 2^(1 + log((n-1)/3)\log(2)); \\ _Michel Marcus_, Mar 08 2019
%Y A306390 Cf. A001147, A001190, A006472.
%K A306390 nonn
%O A306390 3,2
%A A306390 _Noah A Rosenberg_, Feb 12 2019