A143463 Number of multiple hierarchies for n labeled elements.

1, 4, 20, 133, 1047, 9754, 103203, 1229330, 16198452, 234110702, 3675679471, 62287376870, 1132138152251, 21963847972941, 452786198062541, 9881445268293457, 227522503290656371, 5510876754647261442, 140040543831299600637, 3724688873146823853387

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

single A000041 A005651

multiple A001970 A143463

Hierarchical orderings on elements:

........ unlabeled labeled

single A000079 A000670

multiple A034691 A075729

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
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, 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

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

There is a similar formula for A075729. - Thomas Wieder, Sep 09 2008

Sequence in context: A201355 A292468 A360660 * A290444 A270665 A330538

Adjacent sequences: A143460 A143461 A143462 * A143464 A143465 A143466

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