A000258 Expansion of e.g.f. exp(exp(exp(x)-1)-1). (Formerly M2932 N1178)

1, 1, 3, 12, 60, 358, 2471, 19302, 167894, 1606137, 16733779, 188378402, 2276423485, 29367807524, 402577243425, 5840190914957, 89345001017415, 1436904211547895, 24227076487779802, 427187837301557598, 7859930038606521508, 150601795280158255827

Offset

0,3

Comments

Number of 3-level labeled rooted trees with n leaves. - Christian G. Bower, Aug 15 1998

Number of pairs of set partitions (d,d') of [n] such that d is finer than d'. - A. Joseph Kennedy (kennedy_2001in(AT)yahoo.co.in), Feb 05 2006

In the Comm. Algebra paper cited, I introduce a sequence of algebras called 'class partition algebras' with this sequence as dimensions. The algebras are the centralizers of wreath product in combinatorial representation theory. - A. Joseph Kennedy (kennedy_2001in(AT)yahoo.co.in), Feb 17 2008

a(n) is the number of ways to partition {1,2,...,n} and then partition each cell (block) into subcells.

References

J. Ginsburg, Iterated exponentials, Scripta Math., 11 (1945), 340-353.

Ulrike Sattler, Decidable classes of formal power series with nice closure properties, Diplomarbeit im Fach Informatik, Univ. Erlangen - Nuernberg, Jul 27 1994

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Example 5.2.4.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..475 (first 101 terms from T. D. Noe)

A. Aboud, J.-P. Bultel, A. Chouria, J.-G. Luque, and O. Mallet, Bell polynomials in combinatorial Hopf algebras, arXiv preprint arXiv:1402.2960 [math.CO], 2014.

Francesca Aicardi, Diego Arcis, and Jesús Juyumaya, Brauer and Jones tied monoids, arXiv:2107.04170 [math.RT], 2021.

P. Blasiak, A. Horzela, K. A. Penson, G. H. E. Duchamp and A. I. Solomon, Boson normal ordering via substitutions and Sheffer-type polynomials, arXiv:quant-ph/0501155, 2005.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

P. J. Cameron, D. A. Gewurz and F. Merola, Product action, Discrete Math., 308 (2008), 386-394.

Jekuthiel Ginsburg, Iterated exponentials, Scripta Math., 11 (1945), 340-353. [Annotated scanned copy]

Gottfried Helms, Bell Numbers, 2008.

T. Hogg and B. A. Huberman, Attractors on finite sets: the dissipative dynamics of computing structures, Phys. Review A 32 (1985), 2338-2346.

T. Hogg and B. A. Huberman, Attractors on finite sets: the dissipative dynamics of computing structures, Phys. Review A 32 (1985), 2338-2346. (Annotated scanned copy)

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 70

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 292

A. Joseph Kennedy, Class partition algebras as centralizer algebras, Communications in Algebra, 35 (2007), 145-170, see page 153.

A. Joseph Kennedy, P. Jaish, and P. Sundaresan, Note on generating function of higher dimensional bell numbers (sic), Malaya Journal of Matematik (2020) Vol.8, No. 2, 369-372.

Marin Knežević, Vedran Krčadinac, and Lucija Relić, Matrix products of binomial coefficients and unsigned Stirling numbers, arXiv:2012.15307 [math.CO], 2020.

T. Mansour, A. Munagi, and M. Shattuck, Recurrence Relations and Two-Dimensional Set Partitions , J. Int. Seq. 14 (2011) #11.4.1.

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

John Riordan, Letter, Apr 28 1976.

N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, arXiv:math/0307064 [math.CO], 2003, [Order 21 (2004), 83-89].

Index entries for sequences related to rooted trees

Formula

a(n) = |A039811(n, 1)| (first column of triangle).

a(n) = Sum_{k=0..n} Stirling2(n, k)*Bell(k). - Detlef Pauly (dettodet(AT)yahoo.de), Jun 06 2002

Representation as an infinite series (Dobinski-type formula), in Maple notation: a(n)=exp(exp(-1)-1)*sum(evalf(sum(p!*stirling2(k, p)*exp(-p), p=1..k))*k^n/k!, k=0..infinity), n=1, 2, ... . - Karol A. Penson, Nov 28 2003

a(n) = Sum_{k=0..n} A055896(n,k). - R. J. Mathar, Apr 15 2008

G.f.: Sum_{j>=0} Bell(j)*x^j / Product_{k=1..j} (1 - k*x). - Ilya Gutkovskiy, Apr 06 2019

Example

G.f. = 1 + x + 3*x^2 + 12*x^3 + 60*x^4 + 358*x^5 + 2471*x^6 + 19302*x^7 + ...

Maple

with(combinat, bell, stirling2): seq(add(stirling2(n, k)*(bell(k)), k=0..n), n=0..30);
with(combstruct); SetSetSetL := [T, {T=Set(S), S=Set(U, card >= 1), U=Set(Z, card >=1)}, labeled];
# alternative Maple program:
b:= proc(n, t) option remember; `if`(n=0 or t=0, 1, add(
       b(n-j, t)*b(j, t-1)*binomial(n-1, j-1), j=1..n))
    end:
a:= n-> b(n, 2):
seq(a(n), n=0..23);  # Alois P. Heinz, Sep 02 2021

Mathematica

nn = 20; Range[0, nn]! CoefficientList[Series[Exp[Exp[Exp[x] - 1] - 1], {x, 0, nn}], x]
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[ Exp[ Exp[x] - 1] - 1] , {x, 0, n}]]; (* Michael Somos, Aug 15 2015 *)
a[n_] := Sum[StirlingS2[n, k]*BellB[k], {k, 0, n}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 06 2016 *)
Table[Sum[BellY[n, k, BellB[Range[n]]], {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)

Prog

(Maxima) makelist(sum(stirling2(n, k)*belln(k), k, 0, n), n, 0, 24); /* Emanuele Munarini, Jul 04 2011 */
(Magma) m:=25; R<x>:=PowerSeriesRing(Rationals(), m); b:=Coefficients(R!(Exp(Exp(Exp(x)-1)-1))); [Factorial(n-1)*b[n]: n in [1..m]]; // Vincenzo Librandi, Feb 01 2020

Crossrefs

Cf. A000110, A000307, A000357, A000405, A001669, A039811.

Row sums of (Stirling2)^2 triangle A130191.

Column k=2 of A144150.

Sequence in context: A096471 A140097 A105227 * A326242 A070863 A180707

Adjacent sequences: A000255 A000256 A000257 * A000259 A000260 A000261

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved