|
%I #37 May 21 2019 05:53:24
%S 1,4,20,133,1047,9754,103203,1229330,16198452,234110702,3675679471,
%T 62287376870,1132138152251,21963847972941,452786198062541,
%U 9881445268293457,227522503290656371,5510876754647261442,140040543831299600637,3724688873146823853387
%N Number of multiple hierarchies for n labeled elements.
%C 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 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 The present sequence is the Exp transform of A005651.
%C 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 Hierarchies on elements:
%C ........ unlabeled labeled
%C single A000041 A005651
%C multiple A001970 A143463
%C Hierarchical orderings on elements:
%C ........ unlabeled labeled
%C single A000079 A000670
%C multiple A034691 A075729
%H 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 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 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 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 a(n) = (n-1)! * Sum_{k=1..n} (a(n-k) A005651(k))/((n-k)! (k-1)!). - _Thomas Wieder_, Sep 09 2008
%F 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 Let "|" separate two hierarchies. Then we have
%e n=1 gives 1 arrangement:
%e 1
%e n=2 gives 4 arrangements:
%e 1,2 1:2 2:1 1|2
%e n=3 gives 20 arrangements:
%e 1,2,3 1,2:3 1:2:3 1,2|3 1:2|3 1|2|3
%e 1,3:2 3:1:2 1,3|2 1:3|2
%e 2,3:1 2:3:1 2,3|1 2:3|1
%e 1:3:2 2:1|3
%e 2:1:3 3:1|2
%e 3:2:1 3:2|1
%p A143463:=proc(n::integer)
%p # Begonnen am: 14.08.2008
%p # Letzte Aenderung: 14.08.2008
%p # Subroutines required: ListeMengenzerlegungenAuf, A005651.
%p local iverbose, Liste, Zerlegungen, Zerlegung, Produkt, Summe, Untermenge, ZahlElemente;
%p iverbose:=0;
%p Liste:=[seq( i, i=1..n )];
%p Zerlegungen:=ListeMengenzerlegungenAuf(Liste);
%p Summe:=0;
%p if iverbose=1 then
%p print("Zerlegungen: ",Zerlegungen);
%p end if;
%p for Zerlegung in Zerlegungen do
%p Produkt:=1;
%p if iverbose=1 then
%p print("Zerlegung: ",Zerlegung);
%p end if;
%p # Eine Zerlegung besteht aus Untermengen.
%p for Untermenge in Zerlegung do
%p ZahlElemente:=nops(Untermenge);
%p Produkt:=Produkt*A005651(ZahlElemente);
%p if iverbose=1 then
%p print("Untermenge: ",Untermenge,"A005651(ZahlElemente)",A005651(ZahlElemente));
%p end if;
%p # Ende der Schleife in der Zerlegung.
%p od;
%p Summe:=Summe+Produkt;
%p # Ende der Schleife ueber die Zerlegungen.
%p od;
%p print("Resultat:",Summe);
%p end proc;
%p 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 # second Maple program:
%p with(numtheory):
%p b:= proc(k) option remember; add(d/d!^(k/d), d=divisors(k)) end:
%p c:= proc(n) option remember; `if`(n=0, 1,
%p add((n-1)!/ (n-k)!* b(k) * c(n-k), k=1..n))
%p end:
%p a:= proc(n) option remember; `if`(n=0, 1,
%p c(n) +add(binomial(n-1, k-1) *c(k) *a(n-k), k=1..n-1))
%p end:
%p seq(a(n), n=1..25); # _Alois P. Heinz_, Oct 10 2008
%t 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 Cf. A000041, A005651, A001970, A143463, A000079, A000670, A034691, A075729.
%Y There is a similar formula for A075729. - _Thomas Wieder_, Sep 09 2008
%K nonn
%O 1,2
%A _Thomas Wieder_, Aug 17 2008
%E Partially edited by _N. J. A. Sloane_, Aug 24 2008
%E More terms from _Alois P. Heinz_, Oct 10 2008
| 