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

1, 0, 1, 3, 8, 18, 45, 102, 245, 565, 1324, 3049, 7066, 16199, 37187, 84887, 193532, 439600, 996818, 2253941, 5086980, 11454778, 25746467, 57756522, 129342179, 289153474, 645399011, 1438308839, 3200671082, 7112360474, 15783402471, 34980122720, 77428353682

Offset: 0

Author

Thomas Wieder, Jul 09 2005

Keywords

• nonn

Comments

Unlabeled analog of A097237.

Primes in this sequence include: a(3) = 3, a(11) = 3049, a(19) = 2253941, a(22) = 25746467. Semiprimes in this sequence include: a(9) = 565 = 5 * 113, a(12) = 7066 = 2 * 3533, a(13) = 16199 = 97 * 167, a(14) = 37187 = 41 * 907, a(15) = 84887 = 11 * 7717, a(18) = 996818 = 2 * 498409, a(24) = 129342179 = 23 * 5623573, a(30) = 15783402471 = 3 * 5261134157. - Jonathan Vos Post, Jul 10 2005

Examples

			Let * denote an unlabeled element.
Let : denote a delimiter between two levels of a hierarchy.
Let | denote a delimiter between two subhierarchies.
a(4) = 8 because we have *:*:*:*, ***:*, **:*:*, *:*|*:*, *:***, **:**, *:**:*, *:*:**.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, arXiv:math/0307064 [math.CO], 2003; Order 21 (2004), 83-89.

Crossrefs

Cf. A075729, A034691, A097237.

Programs

Maple

SetSeqXSetU := [S, {S=Set(U), U=Sequence(V,card>=2),V=Set(Z,card>=1)},unlabeled]; seq(count(SetSeqXSetU,size=j),j=0..30); #where x is an integer 1, 2, 3,... # x=2 gives 2 levels per society.

Mathematica

nmax = 40; CoefficientList[Series[E^Sum[x^(2*k)/(k*(1 - x^k)*(1 - 2*x^k)), {k, 1, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Jun 08 2018 *)

Formula

G.f.: Product_{k>=1} 1/(1 - x^k)^(2^(k-1)-1). - Ilya Gutkovskiy, Jun 07 2018

a(n) ~ 2^n * exp(sqrt(2*n) - 5/4 + c) / (sqrt(2*Pi) * 2^(3/4) * n^(3/4)), where c = Sum_{k>=2} 1/(k*(2^k-1)*(2^k-2)) = 0.0927294481510243482503144824759369647388... - Vaclav Kotesovec, Jun 08 2018