1,2

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

single A000041 A005651

multiple A001970 the present sequence

Hierarchical orderings on elements:

...... unlabeled labeled

single A000079 A000670

multiple A034691 A075729

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 (thomas.wieder(AT)t-online.de), Nov 14 2009]

N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.

Thomas Wieder, Home Page.

Thomas Wieder, (Old) Home Page.

Consider the set partitions of the n-set {1,2,...,n}. As usual, Bell(n) means 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)} prod_{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); Asymptotic expansion: fas3:= n -> C1*(1/n)^(3/4)*exp(-1/((1/n)^(1/2)))^C2; with C1 := 0.003513007407745965260575286922448606702911 C2 := -3.180866173225395352491431782718333740227

a(n) = (n-1)! sum_{k=1}^{n} (a(n-k) A005651(k))/((n-k)! (k-1)!) [From Thomas Wieder (thomas.wieder(AT)t-online.de), Sep 09 2008]

a(n) = sum_{k=1}^{n} C(n-1,k-1) A005651 a(n-k) and a(0)=1. [From Thomas Wieder (thomas.wieder(AT)t-online.de), Sep 12 2008]

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

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

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;

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 (thomas.wieder(AT)t-online.de), Sep 09 2008]

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); [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Oct 10 2008]

Cf. A000041, A005651, A001970, A143463, A000079, A000670, A034691, A075729.

There is a similar formula for A075729. [From Thomas Wieder (thomas.wieder(AT)t-online.de), Sep 09 2008]

Sequence in context: A140585 A132436 A038173 this_sequence A141716 A129102 A129099

Adjacent sequences: A143460 A143461 A143462 this_sequence A143464 A143465 A143466

nonn,new

Thomas Wieder (thomas.wieder(AT)t-online.de), Aug 17 2008

Partially edited by N. J. A. Sloane (njas(AT)research.att.com), Aug 24 2008

More terms from Alois P. Heinz (heinz(AT)hs-heilbronn.de), Oct 10 2008