A396308 Triangle read by rows: T(n,k) is the number of at-most-k-furcating labeled histories that can be constructed for n labeled leaves, 2<=k<=n.

1, 3, 4, 18, 28, 29, 180, 320, 335, 336, 2700, 5360, 5665, 5686, 5687, 56700, 123760, 131705, 132265, 132293, 132294, 1587600, 3765440, 4028430, 4046980, 4047932, 4047968, 4047969, 57153600, 145951680, 156800490, 157560312, 157599498, 157601022, 157601067, 157601068, 2571912000, 7019678400, 7567091700, 7605060162, 7607014464, 7607091054

Offset

2,2

Comments

Labeled histories for at-most-k-furcating trees can be extended to n=1, with T(1,k)=1. They can also be extended to k>n, with T(n,k)=T(n,n) for k>n.

Links

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

Emily H. Dickey and Noah A. Rosenberg, Labeled histories and maximally probable labeled topologies with multifurcation, Discr. Appl. Math. 391 (2026), 192-203. See Table 1.

Formula

T(n,k) = Sum_{i=2..min(n,k)} (n!/(i!*(n-i)!))*T(n+1-i,k) for n>=k>=2, with T(1,k)=1 for all k>=2.

Example

Triangle begins (the first row is n=2 and the first column is k=2):
        1;
        3;         4;
       18;        28;        29;
      180;       320;       335;       336;
     2700;      5360;      5665;      5686;      5687;
    56700;    123760;    131705;    132265;    132293;    132294;
  1587600;   3765440;   4028430;   4046980;   4047932;   4047968;   4047969;
 57153600; 145951680; 156800490; 157560312; 157599498; 157601022; 157601067; 157601068;

Crossrefs

T(n,2) is A006472(n). T(n,3) is A358072(n). T(n,4) is A396065(n). T(n,5) is A393749(n). T(n,6) is A393759(n). T(n,n) is A256006(n-1).

Sequence in context: A025118 A025094 A025113 * A290956 A089427 A197564

Adjacent sequences: A396305 A396306 A396307 * A396309 A396310 A396311

Keyword

nonn,tabl

Author

Noah A Rosenberg, May 21 2026

Status

approved