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

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

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.

Formula

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

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

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

Example

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

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 *)

Prog

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

Crossrefs

Cf. A055887.

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

Sequence in context: A075729 A328006 A127131 * A141763 A025550 A350669

Adjacent sequences: A083352 A083353 A083354 * A083356 A083357 A083358

Keyword

nonn

Author

Thomas Wieder, Jun 11 2003, May 07 2008

Status

approved