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

0, 1, 1, 4, 29, 336, 5687, 132293, 4047932, 157599498, 7607014464, 445789277010, 31176975417126, 2564948607907686, 245220679951969722, 26959156361305448280, 3377230301505301128888, 478235430296927841409872, 76010484446415665803480824, 13474613251341094194492053904

Offset

0,4

Comments

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

Links

Table of n, a(n) for n=0..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) + (n*(n-1)*(n-2)*(n-3)*(n-4)*(n-5)/720)*a(n-5) for n>=6; base cases follow A256006(n-1) for 1<=n<=5.

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] + Binomial[n, 6] A[n-5], A[0]==0, A[1]==1, A[2]==1, A[3]==4, A[4]==29}, A, {n, 20}]

Crossrefs

Cf. A006472, A256006, A358072, A396065, A393749.

Sequence in context: A396065 A276728 A393749 * A256006 A137646 A231498

Adjacent sequences: A393756 A393757 A393758 * A393760 A393761 A393762

Keyword

nonn

Author

Noah A Rosenberg, May 21 2026

Status

approved