login
Number of preferential arrangements for the set partitions of the n-set [1,2,3,...,n].
20

%I #46 Dec 01 2018 15:13:26

%S 1,1,4,23,175,1662,18937,251729,3824282,65361237,1241218963,

%T 25928015368,590852003947,14586471744301,387798817072596,

%U 11046531316503163,335640299372252595,10835556229612637150,370383732831919278037,13363914680277923634517

%N Number of preferential arrangements for the set partitions of the n-set [1,2,3,...,n].

%C Labeled analog of A055887. See combstruct commands for more precise definition.

%C Stirling transform of A000670(n) = [1,3,13,75,...] is a(n) = [1,4,23,175,...]. - _Michael Somos_, Mar 04 2004

%C Row sums of A232598. So 2*a(n) is the number of formulas in first-order logic that have an n-place predicate, and don't include a negator. - _Tilman Piesk_, Nov 28 2013

%H Alois P. Heinz, <a href="/A083355/b083355.txt">Table of n, a(n) for n = 0..406</a>

%H K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, <a href="http://arXiv.org/abs/quant-ph/0312202">Hierarchical Dobinski-type relations via substitution and the moment problem</a>, arXiv:quant-ph/0312202, 2003; J. Phys. A 37 (2004), 3475-3487.

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%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="/A083355/a083355.txt">Further comments on A083355</a>

%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.

%F E.g.f.: 1/(2-exp(exp(x)-1)).

%F Representation as a double infinite series (Dobinski-type formula), in Maple notation: a(n) = sum(k^n/k!*sum(p^k/(2*exp(1))^p, p=1..infinity), k=1..infinity)/2, n=1, 2... . - _Karol A. Penson_ and Pawel Blasiak (blasiak(AT)lptl.jussieu.fr), Nov 30 2003

%F a(n) ~ n!/(2 * c * (log c)^(n+1)) where c = 1 + log 2.

%F a(n) = Sum_{k=1..n} C(n, k)*Bell(k)*a(n-k). - _Vladeta Jovovic_, Jul 24 2003

%F a(n) = Sum_{i=1..n} Sum_{j=1..i} j!*Stirling2(i,j)*Stirling2(n,i). - _Thomas Wieder_, May 09 2005

%F a(n) = Sum_{k=1..n} S2(n,k) A000670(k).

%F a(n) = Sum_{k >= 0} Bell(n,k)/2^(k+1), where Bell(n,x) = Sum_{k = 0..n} Stirling2(n,k)*x^k denotes the n-th Bell or exponential polynomial. - _Peter Bala_, Jul 09 2014

%e Let the colon ":" be a separator between two levels. E.g. in {1,2}:{3} the set {1,2} is on the first level, the set {3} is on the second level.

%e n=2 gives A083355(2)=4 because we have {1,2} {1}{2} {1}:{2} {2}:{1}.

%e n=3 gives A083355(3)=23 because we have:

%e {1,2,3}

%e {1,2}{3} {1,2}:{3} {3}:{1,2}

%e {1,3}{2} {1,3}:{2} {2}:{1,3}

%e {2,3}{1} {2,3}:{1} {1}:{2,3}

%e {1}{2}{3}

%e {1}:{2}:{3}

%e {3}:{1}:{2}

%e {2}:{3}:{1}

%e {1}:{3}:{2}

%e {2}:{1}:{3}

%e {3}:{2}:{1}

%e {1}{2}:{3} {1}{3}:{2} {2}{3}:{1}

%e {1}:{2}{3} {2}:{1}{3} {3}:{1}{2}.

%e Examples for the unlabeled case A055887:

%e n=2 gives A055887(2)=3 because {1,1} {{1}:{1}} {2}

%e n=3 gives A055887(3)=8 because {1,1,1} {{1}:{1,1}} {{1,1}:{1}} {{1}:{1}:{1}} {1,2} {{1}:{2}} {{2}:{1}} {3}.

%p with(combstruct); SeqSetSetL := [T, {T=Sequence(S), S=Set(U,card >= 1), U=Set(Z,card >= 1)},labeled]; A083355 := n-> count(SeqSetSetL,size=n);

%p A083355 := proc(n::integer) #with(combinat); local a,i,j; a:=0; for i from 1 to n do for j from 1 to i do a := a + j!*stirling2(i,j)*stirling2(n,i); od; od; print("n, a(n): ",n, a); end proc; # _Thomas Wieder_

%p A083355 := proc() local a,k,n; for n from 1 to 12 do a[n]:=0: for k from 1 to n do a[n]:=a[n]+stirling2(n,k)*A000670(k): od: od: print(a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],a[10],a[11],a[12]); end proc; A000670 := proc(n) local Result,k; Result:=0: for k from 1 to n do Result:=Result+stirling2(n,k)*k! od: end proc;

%t Range[0, 18]!CoefficientList[Series[1/(2 - E^(E^x - 1)), {x, 0, 18}], x] (* _Robert G. Wilson v_, Jul 13 2004 *)

%t a[n_] := Sum[StirlingS2[n, k] PolyLog[-k, 1/2]/2, {k, 1, n}]; a[0] = 1; Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Mar 30 2016 *)

%o (PARI) a(n)=if(n<0,0,n!*polcoeff(1/(2-exp(exp(x+x*O(x^n))-1)),n))

%Y Cf. A055887.

%Y Cf. A000079, A000670, A034691, A055887, A075729, A232598.

%K nonn

%O 0,3

%A _Thomas Wieder_, Jun 11 2003, May 07 2008