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
KEYWORD
nonn
AUTHOR
Thomas Wieder, Jun 11 2003, May 07 2008
STATUS
approved