|
| |
|
|
A098407
|
|
Number of different hierarchical orderings that can be formed from n unlabeled elements with no repetition of subhierarchies.
|
|
0
| |
|
|
1, 2, 6, 13, 33, 78, 186, 436, 1028, 2394, 5566, 12877
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
LINKS
| N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.
|
|
|
FORMULA
| Sum_{ partitions n = s_1 + ... + s_n } Prod_{ Set{s_i} } C(2^(s_i - 1), m(s_i)), where the sum runs over all partitions of n, the product runs over the set of parts of a given partition, s_i is the i-th part in the set of parts, C(k, l) denotes the binomial coefficient and m(s_i) is the multipliticity of part s_i in the given partition.
G.f.: Product((1+x^k)^(2^(k-1)),k=1..infinity). - Vladeta Jovovic (vladeta(AT)eunet.rs), Feb 19 2008
|
|
|
EXAMPLE
| Let a pair of parentheses () indicate a subhierarchy and let square brackets [] denote a set of subhierarchies, that is a hierarchy (also called society). Let the ranks be ordered from left to right and separated by a colon, e.g. (2:3) is a subhierarchy with three elements ("individuals") on top and two elements on the bottom rank.
Then the hierarchical ordering for n = 4 is composed of the following sets:
[(1:1),(2)]; [(1),(3)]; [(1),(1:1:1)]; [(1),(2:1)]; [(1),(1:2)];
[(4)]; [(2:2)]; [(1:3)]; [(3:1)]; [(1:1:2)]; [(1:2:1)]; [(2:1:1)]; [(1:1:1:1)]; thus a(4) = 13.
For example, the following hierarchy is not allowed: [(1),(1),(1),(1)] because of the repetition of (1).
|
|
|
MAPLE
| main := proc(n::integer) local a, ListOfPartitions, NumberOfPartitions, APartition, APart, ASet, MultipliticityOfAPart, ndxprttn, ndxprt, Term, Produkt; with(combinat): with(ListTools): a := 0; ListOfPartitions := partition(n); NumberOfPartitions := nops(ListOfPartitions); for ndxprttn from 1 to NumberOfPartitions do 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); Term := 2^(APart-1); Term := binomial(Term, MultipliticityOfAPart); Produkt := Produkt * Term; # 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. # Available from 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;
series(exp(add((-1)^(j-1)/j*z^j/(1-2*z^j), j=1..40)), z, 40); #Cf. A102866 - Vladeta Jovovic (vladeta(AT)eunet.rs), Feb 19 2008
|
|
|
CROSSREFS
| Cf. A034691, A075729.
Sequence in context: A053562 A003039 A109385 * A151390 A116426 A196906
Adjacent sequences: A098404 A098405 A098406 * A098408 A098409 A098410
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Thomas Wieder (wieder.thomas(AT)t-online.de), Sep 07 2004; corrected Sep 09 2004
|
| |
|
|
