A390932 Triangle read by rows: T(n,k) is the number of rooted binary perfect phylogenies with sample size n and k leaves.

1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 4, 4, 3, 1, 3, 6, 10, 9, 6, 1, 3, 9, 17, 24, 20, 11, 1, 4, 12, 30, 49, 61, 46, 23, 1, 4, 16, 44, 93, 138, 152, 106, 46, 1, 5, 20, 66, 157, 290, 387, 386, 248, 98, 1, 5, 25, 90, 253, 535, 878, 1072, 974, 582, 207

Offset

1,8

Links

Table of n, a(n) for n=1..66.

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

Formula

T(n,1)=1, T(n,k) = (1/2) * (Sum_{j=1..k-1} Sum_{i=j..n-k+j} T(n-i,k-j) * T(i,j)) + [n, k even] * T(n/2,k/2) where [] is the Iverson bracket.

T(n,n) = A001190(n) (main diagonal).

T(n+2,n+1) = A085748(n) (first sub-diagonal).

T(n-1,3) = A002620(n) (third column).

T(n,4) = A389571(n) (fourth column).

Example

Triangle begins:
  1;
  1, 1;
  1, 1,  1;
  1, 2,  2,  2;
  1, 2,  4,  4,   3;
  1, 3,  6, 10,   9,   6;
  1, 3,  9, 17,  24,  20,  11;
  1, 4, 12, 30,  49,  61,  46,   23;
  1, 4, 16, 44,  93, 138, 152,  106,  46;
  1, 5, 20, 66, 157, 290, 387,  386, 248,  98;
  1, 5, 25, 90, 253, 535, 878, 1072, 974, 582, 207;
  ...

Crossrefs

Cf. A113822 (row sums).

Cf. A001190, A085748, A002620, A389571.

Sequence in context: A353981 A377289 A271205 * A303841 A380791 A379376

Adjacent sequences: A390929 A390930 A390931 * A390933 A390934 A390935

Keyword

nonn,tabl

Author

Noah A Rosenberg, Nov 24 2025

Status

approved