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;