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

1, 1, 4, 29, 335, 5665, 131705, 4028430, 156800490, 7567091700, 443391506250, 31006215829050, 2550705276018900, 243844277577250350, 26806543530806539500, 3357980302742399334000, 475494120154548612117000, 75572740333888003521315000, 13396707931178035747104822000

Offset

1,3

Comments

a(n) is the number of "merger histories" of n elements, where at most 4 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) for n>=4.

Example

For n=3, the 4 labeled histories are: (1) merge A with B, then merge the result with C; (2) merge A with C, then merge the result with B; (3) merge B with C, then merge the result with A; (4) merge A, B, and C simultaneously.
For n=4, the 29 labeled histories are: the 18 labeled histories with only binary mergers (see A006472(4)); the 6 labeled histories that have a binary merger then a ternary merger; the 4 labeled histories that have a ternary merger then a binary merger; and the 1 labeled history that merges all four elements simultaneously.

Mathematica

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

Crossrefs

Cf. A006472, A256006, A358072 (mergers of up to 3 elements).

Sequence in context: A325478 A099700 A305636 * A276728 A393749 A393759

Adjacent sequences: A396062 A396063 A396064 * A396066 A396067 A396068

Keyword

nonn,easy

Author

Noah A Rosenberg, May 15 2026

Status

approved