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,3

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.

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...

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);

Crossrefs

Cf. A256006.

Sequence in context: A337592 A192485 A332097 * A198513 A113371 A280570

Adjacent sequences: A358069 A358070 A358071 * A358073 A358074 A358075

Keyword

nonn

Author

Johannes Wirtz, Oct 29 2022

Status

approved