A393749 The total number of at-most-5-furcating labeled histories that can be constructed for n labeled leaves.

1, 1, 4, 29, 336, 5686, 132265, 4046980, 157560312, 7605060162, 445672370220, 31168687232760, 2564260300175574, 245154432841736418, 26951837497162698120, 3376310080623048408840, 478104755655706037450592, 75989669747033337085430640, 13470917008811991735384666288

Offset

1,3

Comments

a(n) is the number of "merger histories" of n elements, where at most 5 elements can merge at the same time (see A256006).

Links

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

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

a(n) = (n*(n-1)/2)*a(n-1) + (n*(n-1)*(n-2)/6)*a(n-2) + (n*(n-1)*(n-2)*(n-3)/24)*a(n-3) + (n*(n-1)*(n-2)*(n-3)*(n-4)/120)*a(n-4) for n>=5; base cases follows A256006(n-1) for 1<=n<=4.

Mathematica

RecurrenceTable[{A[n] == Binomial[n, 2] A[n-1] + Binomial[n, 3] A[n-2] + Binomial[n, 4] A[n-3] + Binomial[n, 5] A[n-4], A[0]==0, A[1]==1, A[2]==1, A[3]==4}, A, {n, 1, 20}]

Crossrefs

Cf. A006472, A256006, A358072, A396065.

Sequence in context: A305636 A396065 A276728 * A393759 A256006 A137646

Adjacent sequences: A393746 A393747 A393748 * A393750 A393751 A393752

Keyword

nonn

Author

Noah A Rosenberg, May 21 2026

Status

approved