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;