A389571 - OEIS

A389571

Number of rooted binary perfect phylogenies with sample size n and 4 leaves.

2, 4, 10, 17, 30, 44, 66, 90, 124, 160, 208, 259, 324, 392, 476, 564, 670, 780, 910, 1045, 1202, 1364, 1550, 1742, 1960, 2184, 2436, 2695, 2984, 3280, 3608, 3944, 4314, 4692, 5106, 5529, 5990, 6460, 6970, 7490, 8052, 8624, 9240, 9867, 10540, 11224, 11956

(list; graph; refs; listen; history; text; internal format)

OFFSET

4,1

LINKS

Paolo Xausa, Table of n, a(n) for n = 4..10000

Chloe E. Shiff and Noah A. Rosenberg, Enumeration of rooted binary perfect phylogenies, Discr. Appl. Math. 380 (2026), 538-561. See Table 2, Corollary 9, and eq. 20.

Index entries for linear recurrences with constant coefficients, signature (2,0,-2,2,-2,0,2,-1).

FORMULA

a(n) = (n-1)*(n-3)*(5*n-1)/48 for odd n; a(n) = n*(n-2)*(5*n-11)/48+(1/2)*floor(n/4) for even n.

G.f.: x^4*(2+2*x^2+x^3)/((1-x)^4*(1+x)^2*(1+x^2)).

MATHEMATICA

LinearRecurrence[{2, 0, -2, 2, -2, 0, 2, -1}, {2, 4, 10, 17, 30, 44, 66, 90}, 50] (* Paolo Xausa, Jan 03 2026 *)

PROG

(Python)

def A389571(n): return ((n-1)*(n-3)*(5*n-1) + (0 if n&1 else 3*(n+1+((n&-3)<<1))))//48 # Chai Wah Wu, Nov 13 2025

CROSSREFS

Cf. A113822 (total number of perfect phylogenies with sample size n).

Cf. A002620 (number of perfect phylogenies with sample size n and 3 leaves).