A355044 Number of coalescent histories for matching gene trees and species trees with n leaves and a 5-leaf seed tree.

10, 37, 130, 453, 1584, 5577, 19786, 70720, 254524, 921842, 3357908, 12294995, 45229500, 167093505, 619689690, 2306312580, 8611143420, 32246815350, 121085968380, 455817192090, 1719872196432, 6503354706762, 24640476660420, 93534587913648, 355675196682904

Offset

5,1

Comments

a(n) is the number of coalescent histories for matching gene tree G and species tree S, where G and S are identically labeled and have shape (...((((A_1,A_2),A_3),(A_4,A_5)),.),.),...), with n leaves.

Links

Table of n, a(n) for n=5..29.

Noah A. Rosenberg, Coalescent histories for caterpillar-like families, IEEE/ACM Trans. Comp. Biol. Bioinformat. 10 (2013), 1253-1262.

Formula

a(n) = ((23*n^2-131*n+180)/(4*(2*n-3)*(2*n-5)))*(2*n-2)!/((n-1)!*n!).

a(n) = ((23*n^2-131*n+180)/(4*(2*n-3)*(2*n-5)))*A000108(n-1).

a(n) ~ 23 * 4^(n-3) / (n^(3/2) * sqrt(Pi)). - Amiram Eldar, Oct 10 2025

Mathematica

a[n_] := ((23*n^2 - 131*n + 180)/(4*(2*n-3)*(2*n-5))) * CatalanNumber[n-1]; Array[a, 30, 5] (* Amiram Eldar, Oct 10 2025 *)

Crossrefs

Cf. A000108, A070031 (for the same computation with a 4-leaf seed tree).

Sequence in context: A212755 A048480 A116970 * A373577 A394275 A199208

Adjacent sequences: A355041 A355042 A355043 * A355045 A355046 A355047

Keyword

nonn,easy

Author

Noah A Rosenberg, Jun 16 2022

Status

approved