A256006 Recurrence: a(n) = Sum_{k=0..n-1} a(k)*C(n+1,k), a(0)=1.

1, 1, 4, 29, 336, 5687, 132294, 4047969, 157601068, 7607093435, 445794008034, 31177310522789, 2564976392355144, 245223349515360543, 26959450820298057694, 3377267272710103354409, 478240674001176206987556, 76011318838172580152245187

Offset: 0

Author

Vaclav Kotesovec, May 06 2015

Keywords

• nonn

Comments

The number of merger histories for n+1 distinct firms into one firm, where any number of firms may be merged at a time but mergers of two separate sets of firms never occur simultaneously. See MathStackExchange link. - William P. Orrick, Oct 28 2016

a(n) is the number of distinct labeled increasing trees of size n (see Wirtz at pages 4 - 5). - Stefano Spezia, Nov 13 2022

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..260
• Christian Blatter, How many ways to merge N companies into one big company: Bell or Catalan?, Math StackExchange.
• Johannes Wirtz, On the enumeration of leaf-labelled increasing trees with arbitrary node-degree, arXiv:2211.03632 [q-bio.PE], 2022.

Crossrefs

Cf. A103996.

Programs

Mathematica

nmax = 30; aa = ConstantArray[0,nmax+1]; aa[[1]] = 1; Do[aa[[n+1]]=Sum[Binomial[n+1,k]*aa[[k+1]],{k,0,n-1}],{n,nmax}]; aa

Formula

a(n) ~ c * n^(2*n+8/3) / (2^n * exp(2*n)), where c = 4.001655169623968944922713533374039000521095549333460838578... .

E.g.f. A(x) satisfies A(x) = A'(x)*(exp(x) - 1 - x) + x (see Wirtz at page 7). - Stefano Spezia, Nov 13 2022