|
|
A143463
|
|
Number of multiple hierarchies for n labeled elements.
|
|
4
|
|
|
1, 4, 20, 133, 1047, 9754, 103203, 1229330, 16198452, 234110702, 3675679471, 62287376870, 1132138152251, 21963847972941, 452786198062541, 9881445268293457, 227522503290656371, 5510876754647261442, 140040543831299600637, 3724688873146823853387
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
The n labeled elements 1,2,3,...,n can be distributed in A005651(n) ways onto the levels of a single hierarchy. For the present sequence we distributed the n elements onto 1 up to n separate hierarchies. a(n) gives the number of such separate hierarchies for given n.
A hierarchy is a distribution of elements onto levels. Within a hierarchy the occupation number of level l_j is <= the occupation numbers of the levels l_i with i < j. Let the colon ":" separate two levels l_i and l_(j=i+1). Then we may have 1,2,3:4,5, but 1,2:3,4,5 is forbidden since the higher level has a greater occupation number. On the other hand, for a hierarchical ordering the second configuration is allowed.
The present sequence is the Exp transform of A005651.
The present sequence is related to A075729 which gives the number of separated hierarchical orderings. A034691 gives the number of separated hierarchical orderings for unlabeled elements. Thus we have
Hierarchies on elements:
........ unlabeled labeled
Hierarchical orderings on elements:
........ unlabeled labeled
|
|
LINKS
|
|
|
FORMULA
|
Consider the set partitions of the n-set {1,2,...,n}. As usual, Bell(n) denotes the Bell numbers. The i-th set partition SP(i)={U(1),...,U(Z(i))} consists of Z(i) subsets U(j) with j=1,2,...,Z(i). |U(j)| is the number of elements in U(j). Then a(n) = Sum_{i=1..Bell(n)} Product_{j=1..Z(i)} A005651(|U(j)|). E.g.f.: series((1/exp(1))*exp(mul(1/(1-x^k/k!), k=1..12)), x=0,12);
|
|
EXAMPLE
|
Let "|" separate two hierarchies. Then we have
n=1 gives 1 arrangement:
1
n=2 gives 4 arrangements:
1,2 1:2 2:1 1|2
n=3 gives 20 arrangements:
1,2,3 1,2:3 1:2:3 1,2|3 1:2|3 1|2|3
1,3:2 3:1:2 1,3|2 1:3|2
2,3:1 2:3:1 2,3|1 2:3|1
1:3:2 2:1|3
2:1:3 3:1|2
3:2:1 3:2|1
|
|
MAPLE
|
# Begonnen am: 14.08.2008
# Letzte Aenderung: 14.08.2008
# Subroutines required: ListeMengenzerlegungenAuf, A005651.
local iverbose, Liste, Zerlegungen, Zerlegung, Produkt, Summe, Untermenge, ZahlElemente;
iverbose:=0;
Liste:=[seq( i, i=1..n )];
Zerlegungen:=ListeMengenzerlegungenAuf(Liste);
Summe:=0;
if iverbose=1 then
print("Zerlegungen: ", Zerlegungen);
end if;
for Zerlegung in Zerlegungen do
Produkt:=1;
if iverbose=1 then
print("Zerlegung: ", Zerlegung);
end if;
# Eine Zerlegung besteht aus Untermengen.
for Untermenge in Zerlegung do
ZahlElemente:=nops(Untermenge);
Produkt:=Produkt*A005651(ZahlElemente);
if iverbose=1 then
print("Untermenge: ", Untermenge, "A005651(ZahlElemente)", A005651(ZahlElemente));
end if;
# Ende der Schleife in der Zerlegung.
od;
Summe:=Summe+Produkt;
# Ende der Schleife ueber die Zerlegungen.
od;
print("Resultat:", Summe);
end proc;
# second Maple program:
with(numtheory):
b:= proc(k) option remember; add(d/d!^(k/d), d=divisors(k)) end:
c:= proc(n) option remember; `if`(n=0, 1,
add((n-1)!/ (n-k)!* b(k) * c(n-k), k=1..n))
end:
a:= proc(n) option remember; `if`(n=0, 1,
c(n) +add(binomial(n-1, k-1) *c(k) *a(n-k), k=1..n-1))
end:
|
|
MATHEMATICA
|
nmax=20; Rest[CoefficientList[Series[Exp[Product[1/(1-x^k/k!), {k, 1, nmax}]-1], {x, 0, nmax}], x] * Range[0, nmax]!] (* Vaclav Kotesovec, May 11 2015 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|