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.

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, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32

Offset: 3

Author

Noah A Rosenberg, Feb 12 2019

Keywords

• nonn

Comments

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

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

Examples

			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.
		

Links

• E. H. Dickey and N. A. Rosenberg, Labelled histories with multifurcation and simultaneity, Phil. Trans. R. Soc. B 380 (2025), 20230307. (see Theorem 4)
• F. Disanto and N. A. Rosenberg, Enumeration of ancestral configurations for matching gene trees and species trees, J. Comput. Biol. 24 (2017), 831-850.
• E. F. Harding, The probabilities of rooted tree-shapes generated by random bifurcation, Adv. Appl. Prob. 3 (1971), 44-77.

Crossrefs

Cf. A001147, A001190, A006472.

Programs

Mathematica

Table[2^(1 + Floor[Log2[(n - 1)/3]]), {n, 3, 100}]

PARI

a(n) = 2^(1 + log((n-1)/3)\log(2)); \\ Michel Marcus, Mar 08 2019

Formula

a(n) = 2^(1 + floor(log_2((n-1)/3))).