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

Author

Thomas Wieder, Aug 02 2004

Keywords

• nonn

Examples

			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.
		

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.

Crossrefs

Cf. A075729, A097236.

Programs

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

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