The Number of Hierarchical Orderings

by

N. J. A. Sloane
AT&T Shannon Labs 
Florham Park, NJ 07932-0971, USA 
(njas@research.att.com, http://NeilSloane.com/) 

and

Thomas Wieder
Darmstadt University of Technology 
Institute for Materials Science 
D-64287 Darmstadt, Germany 
(thomas.wieder@epost.de, http://homepages.tu-darmstadt.de/simwieder) 

June 24, 2003; corrected July 3, 2003 

Abstract

An ordered set-partition (or preferential arrangement) 
of n labeled elements represents a single ``hierarchy'';
these are enumerated by the ordered Bell numbers.
In this note we determine the number of ``hierarchical orderings''
or ``societies'',
where the n elements are first partitioned into m <= n subsets
and a hierarchy is specified for each subset.
We also consider the unlabeled case, where the ordered Bell numbers
are replaced by the composition numbers.
If there is only a single hierarchy, we show that the average
rank of an element is asymptotic to n/(4 log 2) in the labeled case
and to n/4 in the unlabeled case.

Keywords: ordered set-partition, preferential arrangement, 
hierarchical ordering, society

AMS 2000 Classification: Primary 06A07

For the full version see
http://NeilSloane.com/doc/wieder.pdf (pdf) or
http://NeilSloane.com/doc/wieder.ps (ps)