A377461 Number of ranked labeled trees compatible with the 2-leaf perfect phylogeny of sample size n that possesses the largest number of compatible ranked labeled trees.

1, 1, 2, 9, 54, 540, 6480, 113400, 2268000, 61236000, 1837080000, 70727580000, 2970558360000, 154469034720000, 8650265944320000, 583892951241600000, 42040292489395200000, 3573424861598592000000, 321608237543873280000000, 33608060823334757760000000

Offset

2,3

Comments

The 2-leaf perfect phylogeny of sample size n that possesses the largest number of compatible ranked labeled trees is (floor(n/2), ceiling(n/2)); a(n) is the number of ranked labeled trees for this perfect phylogeny.

Links

Table of n, a(n) for n=2..21.

J. A. Palacios, A. Bhaskar, F. Disanto and N. A. Rosenberg, Enumeration of binary trees compatible with a perfect phylogeny, J. Math. Biol. 84 (2022), 54.

Formula

a(n) = ((n-2)! / ((floor(n/2)-1)! (n-1-floor(n/2))!)) * (floor(n/2))! (floor(n/2)-1)! (ceiling(n/2))! (ceiling(n/2)-1)! / (2^(floor(n/2)-1) 2^(ceiling(n/2)-1)).

a(n) = A001405(n-2)*A006472(floor(n/2))*A006472(ceiling(n/2)).

a(2n) = A306266(n).

Mathematica

a[n_] := ((n - 2)!/((Floor[n/2] - 1)! (n - 1 - Floor[n/2])!)) Product[Binomial[i, 2], {i, 2, Floor[n/2]}] Product[Binomial[i, 2], {i, 2, Ceiling[n/2]}].
a[n_] := ((n - 2)!/((Floor[n/2] - 1)! (n - 1 - Floor[n/2])!)) Floor[n/2]! (Floor[n/2] - 1)! Ceiling[n/2]! (Ceiling[n/2] - 1)! /(2^(Floor[n/2] - 1) 2^(Ceiling[n/2] - 1)).

Crossrefs

Cf. A001405, A006472, A306266.

Sequence in context: A075679 A001757 A267225 * A078455 A366177 A355281

Adjacent sequences: A377458 A377459 A377460 * A377462 A377463 A377464

Keyword

nonn,changed

Author

Noah A Rosenberg, Jan 03 2025

Status

approved