cp's OEIS Frontend

A143463 Number of multiple hierarchies for n labeled elements.

%I A143463 #37 May 21 2019 05:53:24
%S A143463 1,4,20,133,1047,9754,103203,1229330,16198452,234110702,3675679471,
%T A143463 62287376870,1132138152251,21963847972941,452786198062541,
%U A143463 9881445268293457,227522503290656371,5510876754647261442,140040543831299600637,3724688873146823853387
%N A143463 Number of multiple hierarchies for n labeled elements.
%C A143463 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.
%C A143463 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.
%C A143463 The present sequence is the Exp transform of A005651.
%C A143463 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
%C A143463 Hierarchies on elements:
%C A143463 ........ unlabeled labeled
%C A143463 single   A000041   A005651
%C A143463 multiple A001970   A143463
%C A143463 Hierarchical orderings on elements:
%C A143463 ........ unlabeled labeled
%C A143463 single   A000079   A000670
%C A143463 multiple A034691   A075729
%H A143463 Alois P. Heinz and Vaclav Kotesovec, <a href="/A143463/b143463.txt">Table of n, a(n) for n = 1..430</a> (first 200 terms from Alois P. Heinz)
%H A143463 N. J. A. Sloane and Thomas Wieder, <a href="https://arxiv.org/abs/math/0307064">The Number of Hierarchical Orderings</a>, arXiv:math/0307064 [math.CO], 2003; Order 21 (2004), 83-89.
%H A143463 Thomas Wieder, <a href="http://www.m-hikari.com/ams/ams-password-2009/ams-password53-56-2009/wiederAMS53-56-2009.pdf">The number of certain rankings and hierarchies formed from labeled or unlabeled elements and sets</a>, Applied Mathematical Sciences, vol. 3, 2009, no. 55, 2707 - 2724. [From _Thomas Wieder_, Nov 14 2009]
%F A143463 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);
%F A143463 a(n) = (n-1)! * Sum_{k=1..n} (a(n-k) A005651(k))/((n-k)! (k-1)!). - _Thomas Wieder_, Sep 09 2008
%F A143463 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
%e A143463 Let "|" separate two hierarchies. Then we have
%e A143463 n=1 gives 1 arrangement:
%e A143463 1
%e A143463 n=2 gives 4 arrangements:
%e A143463 1,2 1:2 2:1 1|2
%e A143463 n=3 gives 20 arrangements:
%e A143463 1,2,3 1,2:3 1:2:3 1,2|3 1:2|3 1|2|3
%e A143463 1,3:2 3:1:2 1,3|2 1:3|2
%e A143463 2,3:1 2:3:1 2,3|1 2:3|1
%e A143463 1:3:2 2:1|3
%e A143463 2:1:3 3:1|2
%e A143463 3:2:1 3:2|1
%p A143463 A143463:=proc(n::integer)
%p A143463 # Begonnen am: 14.08.2008
%p A143463 # Letzte Aenderung: 14.08.2008
%p A143463 # Subroutines required: ListeMengenzerlegungenAuf, A005651.
%p A143463 local iverbose, Liste, Zerlegungen, Zerlegung, Produkt, Summe, Untermenge, ZahlElemente;
%p A143463 iverbose:=0;
%p A143463 Liste:=[seq( i, i=1..n )];
%p A143463 Zerlegungen:=ListeMengenzerlegungenAuf(Liste);
%p A143463 Summe:=0;
%p A143463 if iverbose=1 then
%p A143463 print("Zerlegungen: ",Zerlegungen);
%p A143463 end if;
%p A143463 for Zerlegung in Zerlegungen do
%p A143463 Produkt:=1;
%p A143463 if iverbose=1 then
%p A143463 print("Zerlegung: ",Zerlegung);
%p A143463 end if;
%p A143463 # Eine Zerlegung besteht aus Untermengen.
%p A143463 for Untermenge in Zerlegung do
%p A143463 ZahlElemente:=nops(Untermenge);
%p A143463 Produkt:=Produkt*A005651(ZahlElemente);
%p A143463 if iverbose=1 then
%p A143463 print("Untermenge: ",Untermenge,"A005651(ZahlElemente)",A005651(ZahlElemente));
%p A143463 end if;
%p A143463 # Ende der Schleife in der Zerlegung.
%p A143463 od;
%p A143463 Summe:=Summe+Produkt;
%p A143463 # Ende der Schleife ueber die Zerlegungen.
%p A143463 od;
%p A143463 print("Resultat:",Summe);
%p A143463 end proc;
%p A143463 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]
%p A143463 # second Maple program:
%p A143463 with(numtheory):
%p A143463 b:= proc(k) option remember; add(d/d!^(k/d), d=divisors(k)) end:
%p A143463 c:= proc(n) option remember; `if`(n=0, 1,
%p A143463       add((n-1)!/ (n-k)!* b(k) * c(n-k), k=1..n))
%p A143463     end:
%p A143463 a:= proc(n) option remember; `if`(n=0, 1,
%p A143463        c(n) +add(binomial(n-1, k-1) *c(k) *a(n-k), k=1..n-1))
%p A143463     end:
%p A143463 seq(a(n), n=1..25);  # _Alois P. Heinz_, Oct 10 2008
%t A143463 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 *)
%Y A143463 Cf. A000041, A005651, A001970, A143463, A000079, A000670, A034691, A075729.
%Y A143463 There is a similar formula for A075729. - _Thomas Wieder_, Sep 09 2008
%K A143463 nonn
%O A143463 1,2
%A A143463 _Thomas Wieder_, Aug 17 2008
%E A143463 Partially edited by _N. J. A. Sloane_, Aug 24 2008
%E A143463 More terms from _Alois P. Heinz_, Oct 10 2008