From thomas.wieder(AT)epost.de  Sun Sep  5 16:28:59 2004
From: Thomas Wieder

5.9.2004

Dear Neil,

just a short note concerning the number of hierarchical orderings in the
unlabeled case. This is OEIS A034691.

Today I found a closed formula for the unlabeled case. In our
publication (N.J.A. Sloane and T. Wieder, The Number of Hierarchical
Orderings, 2004), we have not given it. Below, you will find a Maple
program which calculates the closed formula.

Once one has a formula, everthing looks trivial: We have to split the
integer n into all its possible partitions. This is the first partition.
We distribute the elements or "individuals" over different
subhierarchies. So we have a first loop over all partitions. Lets pick a
certain partition: APart_1 + APart_2 + ... + APart_i + ... + APart_n =
n.

E.g. n=5 and 2 + 3 = 5

For example, APart_2 is the number of elements in the second
subhierarchy. Then we have to distribute the APart_2 elements over up to
APart2 possible levels.

E.g. for APart_2 = 3 we have four subhierarchies: 3; 2|1; 1|2; 1|1|1.

This distributing over levels forms the second partition stage. How many
possibilities for the distribution are there? We distribute say m
unlabeled elements over l boxes (where l is the number of labels). There
are C(m-1,l-1) possibilities for doing this (where C denotes the
binomial coefficient) and since we have l=1,...,APart_i levels we have
to sum over l which results in the simple factor 2^(APart_i-1).

So far, it was not so complicated. But we consider two hierarchies as
identical if they have the same subhierarchies, i.e. subhierarchies are
unlabeled. E.g. for n=5 the two hierarchies (1, 1|1, 2) and (1, 2, 1|1)
are identical. The problem comes from parts which arrise repeatedly in
the first partition.

E.g. for n=5 we can have (1,2,2), that is two times "2". Each "2" can be
partitioned, i.e. distributed over levels according to 2, 1|1. The
cartesian product counts the totality of all possibilites and is [(2,2),
(2,1|1), (1|1,2), (2,2)]. We see that the case (2,1|1) = (1|1,2) occurs
two times, but we want to count this case only one time. Let denote
MltAPart_i the multiplicity of APart_i, that is the number of
repititions of APart_i in the first partition of n.

What we are counting here is the number of different combinations with
repititions of NPart_i elements in the order MltAPart_i. There are
C(NPart_i + MltAPart_i - 1, MltAPart_i) possibilities to do that.

Finally we have for a(n)

a(n) = Sum_(partitions of n) Prod(over set of parts of partition of n)_i
C(2^(APart_i - 1) + MltAPart_i - 1, MltAPart_i)

Please note, in the product over the parts of the first partition, we
need to loop only over the set of parts. E.g. for n = 5 = 1 + 2 + 2 we
the set of parts (1,2) and we have a product coming from Apart_1 = 1 and
a product coming from APart_2 = 2, we need not to from a second product
for the second "2" in that partition. Okay, the above transcritption of
the formula is not standard format..., please refer to the Maple
program.

I am really happy that finally we have a closed formula for the unlabeled case.

Sincerely yours

Thomas

main := proc(n::integer)
# Begonnen am:         31.8.2004.
# Letzte Aenderung am: 05.9.2004

# Calculate sequence A034691 of the OEIS by a closed formula.
# A034691: 1, 1, 3, 7, 18, 42, 104, 244, 585, 1373
# E.g. a(6) = 104.
# UNLABELED CASE!
# Literature:
# N.J.A. Sloane and T. Wieder: The Number of Hierarchical Orderings, 2004.
# Thomas Wieder, thomas.wieder@epost.de, 
http://homepages.tu-darmstadt.de/~wieder

# Written for Maple 9.
# Most likely, this program will not run with any other version of Maple
# without modifications.
# With my instance of Maple, I need to call this programm twice before
# it gives correct results (but then it runs stable).

local a, iverbose, ListOfPartitions, NumberOfPartitions, APartition,
APart, ASet, MultipliticityOfAPart, ndxprttn, ndxprt, Term, Produkt;

with(combinat):
with(ListTools):
# Set *** iverbose *** := 1 for debugging purposes.
iverbose := 1;
a := 0;

ListOfPartitions := partition(n);
NumberOfPartitions := nops(ListOfPartitions);

for ndxprttn from 1 to NumberOfPartitions do
if iverbose = 1 then
print(" ");
fi;

APartition := ListOfPartitions[ndxprttn];
ASet := convert(APartition,set);
Produkt := 1;

for ndxprt from 1 to nops(ASet) do

APart := op(ndxprt,ASet);
MultipliticityOfAPart := Occurrences(APart, APartition);
if iverbose = 1 then
print("APart, MultipliticityOfAPart: ",APart,MultipliticityOfAPart);
fi;

Term := 2^(APart-1);
Term := binomial(Term+MultipliticityOfAPart-1,MultipliticityOfAPart);

Produkt := Produkt * Term;
if iverbose = 1 then
print("APartition, APart, 2^(APart-1), Term: 
",APartition,APart,2^(APart-1),Term);
fi;

# End of do-loop *** ndxprt ***.
end do;

a := a + Produkt;

# End of do-loop *** ndxprttn ***.
end do;

print("n, a(n):",n,a);
end proc;