A097237 Number of hierarchical orderings ("societies") of n labeled elements ("individuals") with at least two occupied levels.

0, 2, 12, 86, 780, 8462, 106092, 1507046, 23905740, 418581662, 8014481772, 166501716086, 3728936827980, 89530481995502, 2293539506425452, 62429371709206406, 1799021068567370700, 54707449240102350782, 1750530594833378049132, 58787407236482804618006

Offset

1,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..150

N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.

Formula

E.g.f.: exp(-(exp(z)^2-2*exp(z)+1)/(-2+exp(z))).

a(n) ~ exp(sqrt(2*n/log(2)) + 1/(4*log(2)) - n - 7/4) * n^(n-1/4) / (2^(3/4) * log(2)^(n+1/4)). - Vaclav Kotesovec, Sep 13 2014

Example

a(3) = 12. Let : denote the partition of n labeled individuals 1,2,3,4 into x=2 sets (i.e. "societies"). E.g., in 12:34 one has a single society with members 1 and 2 and a further single society with members 3 and 4. Let | denote a higher level (within a single society), e.g., in 1|2 the individual 2 is one level up with respect to individual 1. The order of individuals on a level is insignificant, e.g., 12|34 is equivalent to 21|43. For n = 3 and x = 2 one has 12|3; 23|1; 13|2; 1|23; 2|13; 3|12; 1|2|3; 2|3|1; 3|1|2; 1|3|2; 3|2|1; 2|1|3; which gives 12 different societies with at least 2 occupied levels.

Maple

with(combstruct); SetSeq2SetL:=[T, {T=Set(S), S=Sequence(U, card>=2), U=Set(Z, card >= 1)}, labeled];
# where x is an integer 1, 2, 3, ... ; x=2 gives 2 levels per society.
seq (count (SetSeq2SetL, size=j), j=1..12);

Mathematica

Rest[CoefficientList[Series[E^((2*E^x-E^(2*x)-1) / (E^x-2)), {x, 0, 20}], x] * Range[0, 20]!] (* Vaclav Kotesovec, Sep 13 2014 *)

Crossrefs

Cf. A075729, A097236.

Sequence in context: A364279 A208977 A372104 * A363255 A055531 A305209

Adjacent sequences: A097234 A097235 A097236 * A097238 A097239 A097240

Keyword

nonn

Author

Thomas Wieder, Aug 02 2004

Status

approved