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
Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 1..430 (first 200 terms from Alois P. Heinz)
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, arXiv:math/0307064 [math.CO], 2003; Order 21 (2004), 83-89.
Thomas Wieder, The number of certain rankings and hierarchies formed from labeled or unlabeled elements and sets, Applied Mathematical Sciences, vol. 3, 2009, no. 55, 2707 - 2724. [From Thomas Wieder, Nov 14 2009]
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);
a(n) = (n-1)! * Sum_{k=1..n} (a(n-k) A005651(k))/((n-k)! (k-1)!). - Thomas Wieder, Sep 09 2008
a(n) = Sum_{k=1..n} binomial(n-1,k-1)*A005651(k)*a(n-k) and a(0)=1. - Thomas Wieder, Sep 12 2008
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
A143463:=proc(n::integer)
# 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
end if;
# Ende der Schleife in der Zerlegung.
od;
Summe:=Summe+Produkt;
# Ende der Schleife ueber die Zerlegungen.
od;
print("Resultat:", Summe);
end proc;
A143463 := proc(n::integer) local k, A005651, Resultat; A005651:=array(1..20): A005651[1]:=1: A005651[2]:=3: A005651[3]:=10: A005651[4]:=47: A005651[5]:=246: A005651[6]:=1602: A005651[7]:=11481: A005651[8]:=95503: A005651[9]:=871030: A005651[10]:=8879558: A005651[11]:=98329551: A005651[12]:=1191578522: A005651[13]:=15543026747: A005651[14]:=218668538441: A005651[15]:=3285749117475: A005651[16]:=52700813279423: A005651[17]:=896697825211142: A005651[18]:=16160442591627990: A005651[19]:=307183340680888755: A005651[20]:=6147451460222703502: if n = 0 then Resultat:=1: RETURN(Resultat); end if; Resultat:=0: for k from 1 to n do Resultat:=Resultat+(A143463(n-k)*A005651[k])/((n-k)!*(k-1)!): od; Resultat:=Resultat*(n-1)!; RETURN(Resultat); end proc; [From Thomas Wieder, Sep 09 2008]
# 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:
seq(a(n), n=1..25); # Alois P. Heinz, Oct 10 2008
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
Thomas Wieder, Aug 17 2008
EXTENSIONS
Partially edited by N. J. A. Sloane, Aug 24 2008
More terms from Alois P. Heinz, Oct 10 2008
STATUS
approved