From thomas.wieder(AT)epost.de Sun Sep 5 16:28:59 2004 From: Thomas Wieder 5.9.1004 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; # ##################################################################### # ##################################################################### PartitionList := proc (n, k) # Authors: # Herbert S. Wilf and Joanna Nordlicht, # Source: # Lecture Notes "East Side West Side,..." # University of Pennsylvania, USA, 2002. # Avalible at: http://www.cis.upenn.edu/~wilf/lecnotes.html # Berechnet die Partitionen von *** n *** # mit *** k *** Summanden. local East, West; if n < 1 or k < 1 or n < k then RETURN([]) elif n = 1 then RETURN([[1]]) else if n < 2 or k < 2 or n < k then West := [] else West := map(proc (x) options operator, arrow; [op(x), 1] end proc, PartitionList(n-1, k-1)) end if; if k <= n-k then East := map(proc(y) options operator, arrow; map(proc (x) options operator, arrow; x+1 end proc, y) end proc, PartitionList(n-k, k)) else East := [] end if; RETURN([op(West), op(East)]) end if end proc; # ##################################################################### # ##################################################################### -- Mit freundlichen Grüßen Thomas Wieder ------------------------------------------------------ Dr. Thomas Wieder Anschrift/Address: Am Hahnen 17 c 34132 Kassel Deutschland/Germany Tel.: +49-(0)561-4009881 Handy: 0151-14102344 or 0171-2817099 Fax: +49-(0)561-4009882 E-mail: thomas.wieder@epost.de Heimseite/Homepage: http://homepages.tu-darmstadt.de/~wieder http://www.uni-kassel.de/~wieder Stand: 26.12.2003 ----------------------------------------------------------- --------------090305090902080209060404 Content-Type: text/plain; name="FormelUC.mpl" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="FormelUC.mpl" 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; # ##################################################################### # ##################################################################### PartitionList := proc (n, k) # Authors: # Herbert S. Wilf and Joanna Nordlicht, # Source: # Lecture Notes "East Side West Side,..." # University of Pennsylvania, USA, 2002. # Avalible at: http://www.cis.upenn.edu/~wilf/lecnotes.html # Berechnet die Partitionen von *** n *** # mit *** k *** Summanden. local East, West; if n < 1 or k < 1 or n < k then RETURN([]) elif n = 1 then RETURN([[1]]) else if n < 2 or k < 2 or n < k then West := [] else West := map(proc (x) options operator, arrow; [op(x), 1] end proc, PartitionList(n-1, k-1)) end if; if k <= n-k then East := map(proc(y) options operator, arrow; map(proc (x) options operator, arrow; x+1 end proc, y) end proc, PartitionList(n-k, k)) else East := [] end if; RETURN([op(West), op(East)]) end if end proc; # #####################################################################