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)