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,2

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

Links

Table of n, a(n) for n=3..68.

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.

Formula

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

Example

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.

Mathematica

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

Prog

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

Crossrefs

Cf. A001147, A001190, A006472.

Sequence in context: A096491 A217871 A362872 * A106160 A305117 A283426

Adjacent sequences: A306387 A306388 A306389 * A306391 A306392 A306393

Keyword

nonn

Author

Noah A Rosenberg, Feb 12 2019

Status

approved