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

1, 1, 4, 23, 175, 1662, 18937, 251729, 3824282, 65361237, 1241218963, 25928015368, 590852003947, 14586471744301, 387798817072596, 11046531316503163, 335640299372252595, 10835556229612637150, 370383732831919278037, 13363914680277923634517

Offset: 0

Author

Thomas Wieder, Jun 11 2003, May 07 2008

Keywords

• nonn

Comments

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

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

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

Examples

			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.
n=2 gives A083355(2)=4 because we have {1,2} {1}{2} {1}:{2} {2}:{1}.
n=3 gives A083355(3)=23 because we have:
  {1,2,3}
  {1,2}{3} {1,2}:{3} {3}:{1,2}
  {1,3}{2} {1,3}:{2} {2}:{1,3}
  {2,3}{1} {2,3}:{1} {1}:{2,3}
  {1}{2}{3}
  {1}:{2}:{3}
  {3}:{1}:{2}
  {2}:{3}:{1}
  {1}:{3}:{2}
  {2}:{1}:{3}
  {3}:{2}:{1}
  {1}{2}:{3} {1}{3}:{2} {2}{3}:{1}
  {1}:{2}{3} {2}:{1}{3} {3}:{1}{2}.
Examples for the unlabeled case A055887:
n=2 gives A055887(2)=3 because {1,1} {{1}:{1}} {2}
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}.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..406
• K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem, arXiv:quant-ph/0312202, 2003; J. Phys. A 37 (2004), 3475-3487.
• N. J. A. Sloane, Transforms
• 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, Further comments on A083355
• 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.

Crossrefs

Cf. A055887.

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

Programs

Maple

with(combstruct); SeqSetSetL := [T, {T=Sequence(S), S=Set(U,card >= 1), U=Set(Z,card >= 1)},labeled]; A083355 := n-> count(SeqSetSetL,size=n);
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
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;

Mathematica

Range[0, 18]!CoefficientList[Series[1/(2 - E^(E^x - 1)), {x, 0, 18}], x] (* Robert G. Wilson v, Jul 13 2004 *)
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 *)

PARI

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

Formula

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

Representation as a double infinite series (Dobinski-type formula): a(n) = (1/2)*Sum_{k>=1} (k^n/k!)*Sum_{p>=1} p^k/(2*exp(1))^p, n >= 1. - Karol A. Penson and Pawel Blasiak (blasiak(AT)lptl.jussieu.fr), Nov 30 2003

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

a(n) = Sum_{k=1..n} C(n, k)*Bell(k)*a(n-k). - Vladeta Jovovic, Jul 24 2003

a(n) = Sum_{i=1..n} Sum_{j=1..i} j!*Stirling2(i,j)*Stirling2(n,i). - Thomas Wieder, May 09 2005

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

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