A380766 Triangle read by rows: T(n,k) is the number of coalescent histories for an n-leaf caterpillar species tree and an identically labeled k-pseudocaterpillar gene tree, 3 <= k <= n.

1, 3, 3, 9, 11, 9, 28, 37, 37, 28, 90, 124, 134, 124, 90, 297, 420, 473, 473, 420, 297, 1001, 1441, 1665, 1735, 1665, 1441, 1001, 3432, 5005, 5885, 6291, 6291, 5885, 5005, 3432, 11934, 17576, 20930, 22766, 23354, 22766, 20930, 17576, 11934, 41990, 62322, 74932, 82537, 86149, 86149, 82537, 74932, 62322, 41990

Offset

3,2

Comments

The largest entry in a row with fixed n is at k=(n+3)/2 for n odd and at both k=(n+2)/2 and k=(n+4)/2 for n even (Theorem 7 of Alimpiev & Rosenberg 2021).

Rows of T(n,k) have a symmetry: T(n,k) = T(n,n-k+3) for all (n,k) with 3 <= k <=n (Theorem 14 of Alimpiev & Rosenberg 2021).

Links

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

Egor Alimpiev and Noah A. Rosenberg, Enumeration of coalescent histories for caterpillar species trees and p-pseudocaterpillar gene trees, Adv. Appl. Math. 131 (2021), 102265.

Formula

T(n,k) = Sum_{l=k-1..n-1} (l-k+2)^2 * (l-k+4) * (2n-k-l-1)! * (l+k-3)! / ( (l+1)! * (n-l-1)! * (n-k+1)! * (k-3)! ) (Equation 9 of Alimpiev & Rosenberg 2021).

Example

Triangle begins (the first row is n=3 and the first column is k=3):
    1;
    3;     3;
    9;    11;     9;
   28;    37;    37;    28;
   90;   124;   134;   124;    90;
  297;   420;   473;   473;   420;   297;
 1001;  1441;  1665;  1735;  1665;  1441;  1001;
 3432;  5005;  5885;  6291;  6291;  5885;  5005;  3432;
11934; 17576; 20930; 22766; 23354; 22766; 20930; 17576; 11934;
41990; 62322; 74932; 82537; 86149; 86149; 82537; 74932; 62322; 41990;

Mathematica

T[n_, k_]:=Sum[(l-k+2)^2*(l-k+4)*(2n-k-l-1)!*(l+k-3)!/((l+1)!*(n-l-1)!*(n-k+1)!*(k-3)!), {l, k-1, n-1}]; Table[T[n, k], {n, 3, 12}, {k, 3, n}]//Flatten (* Stefano Spezia, Feb 02 2025 *)

Crossrefs

T(n,3) and T(n,n) are A000245 (shifted).

T(n,4) and T(n,n-1) are A306423.

Sequence in context: A133164 A022156 A125027 * A360244 A360242 A005296

Adjacent sequences: A380763 A380764 A380765 * A380767 A380768 A380769

Keyword

nonn,tabl

Author

Noah A Rosenberg, Feb 01 2025

Status

approved