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

1, 1, 4, 28, 320, 5360, 123760, 3765440, 145951680, 7019678400, 410164339200, 28615175635200, 2349290700556800, 224201377681881600, 24610071925350912000, 3078761402543963136000, 435446399655217606656000

Offset: 1

Author

Johannes Wirtz, Oct 29 2022

Keywords

• nonn

Comments

Also the number of unordered, leaf-labeled increasing trees on n leaves with maximum node outdegree 3.

Links

• Johannes Wirtz, Table of n, a(n) for n = 1..1000
• Johannes Wirtz, On the enumeration of leaf-labelled increasing trees with arbitrary node-degree, arXiv:2211.03632 [q-bio.PE], 2022.

Crossrefs

Cf. A256006.

Programs

Maple

a := proc(n) option remember; if n < 2 then return 1 else
a(n-2)*binomial(n, 3) + a(n-1)*binomial(n, 2) fi end:
seq(a(n), n = 1..17);

Formula

a(n) = n*(n-1)*((n-2)*a(n-2) + 3*a(n-1))/6 for n >= 3.

a(n+1) ~ 2*Pi*exp(-2/3)*Gamma(5/3)^(-1)*n^(2n+8/3)*2^(-n)*exp^(-2n).

2*Pi*exp(-2/3)*Gamma(5/3)^(-1) = 3.573427548...