

A000110


Bell or exponential numbers: number of ways to partition a set of n labeled elements.
(Formerly M1484 N0585)


644



1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, 4213597, 27644437, 190899322, 1382958545, 10480142147, 82864869804, 682076806159, 5832742205057, 51724158235372, 474869816156751, 4506715738447323, 44152005855084346, 445958869294805289, 4638590332229999353, 49631246523618756274
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

The leading diagonal of its difference table is the sequence shifted, see Bernstein and Sloane (1995).  N. J. A. Sloane, Jul 04 2015
Also the number of equivalence relations that can be defined on a set of n elements.  Federico Arboleda (federico.arboleda(AT)gmail.com), Mar 09 2005
a(n) = number of nonisomorphic colorings of a map consisting of a row of n+1 adjacent regions. Adjacent regions cannot have the same color.  David W. Wilson, Feb 22 2005
If an integer is squarefree and has n distinct prime factors then a(n) is the number of ways of writing it as a product of its divisors.  Amarnath Murthy, Apr 23 2001
Consider rooted trees of height at most 2. Letting each tree 'grow' into the next generation of n means we produce a new tree for every node which is either the root or at height 1, which gives the Bell numbers.  Jon Perry, Jul 23 2003
Begin with [1,1] and follow the rule that [1,k] > [1,k+1] and [1,k] k times, e.g., [1,3] is transformed to [1,4], [1,3], [1,3], [1,3]. Then a(n) is the sum of all components. [1,1]=2, [1,2], [1,1]=5, [1,3], [1,2], [1,2],[1,1], [1,2]=15, etc.  Jon Perry, Mar 05 2004
Number of distinct rhyme schemes for a poem of n lines: a rhyme scheme is a string of letters (e.g., 'abba') such that the leftmost letter is always 'a' and no letter may be greater than one more than the greatest letter to its left. Thus 'aac' is not valid since 'c' is more than one greater than 'a'. For example, a(3)=5 because there are 5 rhyme schemes: aaa, aab, aba, abb, abc; also see example by Neven Juric.  Bill Blewett, Mar 23 2004
In other words, number of lengthn restricted growth strings (RGS) [s(0),s(1),...,s(n1)] where s(0)=0 and s(k)<=1+max(prefix) for k>=1, see example (cf. A080337 and A189845).  Joerg Arndt, Apr 30 2011
Number of partitions of {1, ...,n+1} into subsets of nonconsecutive integers, including the partition 12...n+1. E.g., a(3)=5: there are 5 partitions of {1,2,3,4} into subsets of nonconsecutive integers, namely, 1324, 1324, 1423, 1243, 1234.  Augustine O. Munagi, Mar 20 2005
Triangle (addition) scheme to produce terms, derived from the recurrence, from Oscar Arevalo (loarevalo(AT)sbcglobal.net), May 11 2005:
1
1 2
2 3 5
5 7 10 15
15 20 27 37 52
... [This is Aitken's array A011971]
With P(n) = the number of integer partitions of n, p(i) = the number of parts of the ith partition of n, d(i) = the number of different parts of the ith partition of n, p(j,i) = the jth part of the ith partition of n, m(i,j) = multiplicity of the jth part of the ith partition of n, one has: a(n) = Sum_{i=1..P(n)} (n!/(Product_{j=1..p(i)}p(i,j)!)) * (1/(Product_{j=1..d(i)} m(i,j)!))  Thomas Wieder, May 18 2005
a(n+1) is the number of binary relations on an nelement set that are both symmetric and transitive.  Justin Witt (justinmwitt(AT)gmail.com), Jul 12 2005
If Jon Perry's rule is used, i.e., "Begin with [1,1] and follow the rule that [1,k] > [1,k+1] and [1,k] k times, e.g., [1,3] is transformed to [1,4], [1,3], [1,3], [1,3]. Then a(n) is the sum of all components. [1,1]=2, [1,2],[1,1]=5, [1,3],[1,2],[1,2],[1,1],[1,2]=15, etc..." then a(n1) = [number of components used to form a(n)] / 2.  Daniel Kuan (dkcm(AT)yahoo.com), Feb 19 2006
a(n) is the number of functions f from {1,...,n} to {1,...,n,n+1} that satisfy the following two conditions for all x in the domain: (1) f(x)>x; (2)f(x)=n+1 or f(f(x))=n+1. E.g., a(3)=5 because there are exactly five functions that satisfy the two conditions: f1={(1,4),(2,4),(3,4)}, f2={(1,4),(2,3),(3,4)}, f3={(1,3),(2,4),(3,4)}, f4={(1,2),(2,4),(3,4)} and f5={(1,3),(2,3),(3,4)}.  Dennis P. Walsh, Feb 20 2006
Number of asynchronic siteswap patterns of length n which have no zerothrows (i.e., contain no 0's) and whose number of orbits (in the sense given by Allen Knutson) is equal to the number of balls. E.g., for n=4, the condition is satisfied by the following 15 siteswaps: 4444, 4413, 4242, 4134, 4112, 3441, 2424, 1344, 2411, 1313, 1241, 2222, 3131, 1124, 1111. Also number of ways to choose n permutations from identity and cyclic permutations (1 2), (1 2 3), ..., (1 2 3 ... n) so that their composition is identity. For n=3 we get the following five: id o id o id, id o (1 2) o (1 2), (1 2) o id o (1 2), (1 2) o (1 2) o id, (1 2 3) o (1 2 3) o (1 2 3). (To see the bijection, look at Ehrenborg and Readdy paper.)  Antti Karttunen, May 01 2006
a(n) is the number of permutations on [n] in which a 321 (scattered) pattern occurs only as part of a 3241 pattern. Example: a(3) = 5 counts all permutations on [3] except 321. See "Eigensequence for Composition" reference a(n) = number of permutation tableaux of size n (A000142) whose first row contains no 0's. Example: a(3)=5 counts {{}, {}, {}}, {{1}, {}}, {{1}, {0}}, {{1}, {1}}, {{1, 1}}.  David Callan, Oct 07 2006
Take the series 1^n/1! + 2^n/2! + 3^n/3! + 4^n/4! ... If n=1 then the result will be e, about 2.71828. If n=2, the result will be 2e. If n=3, the result will be 5e. This continues, following the pattern of the Bell numbers: e, 2e, 5e, 15e, 52e, 203e, etc.  Jonathan R. Love (japanada11(AT)yahoo.ca), Feb 22 2007
From Gottfried Helms, Mar 30 2007: (Start)
This sequence is also the first column in the matrixexponential of the (lower triangular) Pascalmatrix, scaled by exp(1): PE = exp(P) / exp(1) =
1
1 1
2 2 1
5 6 3 1
15 20 12 4 1
52 75 50 20 5 1
203 312 225 100 30 6 1
877 1421 1092 525 175 42 7 1
First 4 columns are A000110, A033306, A105479, A105480. The general case is mentioned in the two latter entries. PE is also the Hadamardproduct Toeplitz(A000110) (X) P:
1
1 1
2 1 1
5 2 1 1
15 5 2 1 1 (X) P
52 15 5 2 1 1
203 52 15 5 2 1 1
877 203 52 15 5 2 1 1
(End)
The terms can also be computed with finite steps and precise integer arithmetic. Instead of exp(P)/exp(1) one can compute A = exp(P  I) where I is the identitymatrix of appropriate dimension since (PI) is nilpotent to the order of its dimension. Then a(n)=A[n,1] where n is the rowindex starting at 1.  Gottfried Helms, Apr 10 2007
Define a Bell pseudoprime to be a composite number n such that a(n) == 2 (mod n). W. F. Lunnon recently found the Bell pseudoprimes 21361 = 41*521 and C46 = 3*23*16218646893090134590535390526854205539989357 and conjectured that Bell pseudoprimes are extremely scarce. So the second Bell pseudoprime is unlikely to be known with certainty in the near future. I confirmed that 21361 is the first.  David W. Wilson, Aug 04 2007 and Sep 24 2007
This sequence and A000587 form a reciprocal pair under the list partition transform described in A133314.  Tom Copeland, Oct 21 2007
Starting (1, 2, 5, 15, 52, ...), equals row sums and right border of triangle A136789. Also row sums of triangle A136790.  Gary W. Adamson, Jan 21 2008
This is the Expoential transform of A000012.  Thomas Wieder, Sep 09 2008
From Abdullahi Umar, Oct 12 2008: (Start)
a(n) is also the number of idempotent orderdecreasing full transformations (of an nchain).
a(n) is also the number of nilpotent partial oneone orderdecreasing transformations (of an nchain).
a(n+1) is also the number of partial oneone orderdecreasing transformations (of an nchain). (End)
From Peter Bala, Oct 19 2008: (Start)
Bell(n) is the number of npattern sequences [Cooper & Kennedy]. An npattern sequence is a sequence of integers (a_1,...,a_n) such that a_i = i or a_i = a_j for some j < i. For example, Bell(3) = 5 since the 3pattern sequences are (1,1,1), (1,1,3), (1,2,1), (1,2,2) and (1,2,3).
Bell(n) is the number of sequences of positive integers (N_1,...,N_n) of length n such that N_1 = 1 and N_(i+1) <= 1 + max{j = 1..i} N_j for i >= 1 (see the comment by B. Blewett above). It is interesting to note that if we strengthen the latter condition to N_(i+1) <= 1 + N_i we get the Catalan numbers A000108 instead of the Bell numbers.
(End)
Equals the eigensequence of Pascal's triangle, A007318; and starting with offset 1, = row sums of triangles A074664 and A152431.  Gary W. Adamson, Dec 04 2008
The entries f(i, j) in the exponential of the infinite lowertriangular matrix of binomial coefficients b(i, j) are f(i, j) = b(i, j) e a(i  j).  David Pasino, Dec 04 2008
Equals Lim_{k>inf.} A071919^k.  Gary W. Adamson, Jan 02 2009
Equals A154107 convolved with A014182, where A014182 = expansion of exp(1xexp(x)), the eigensequence of A007318^(1). Starting with offset 1 = A154108 convolved with (1,2,3,...) = row sums of triangle A154109.  Gary W. Adamson, Jan 04 2009
Repeated iterates of (binomial transform of [1,0,0,0,...]) will converge upon (1, 2, 5, 15, 52,...) when each result is prefaced with a "1"; such that the final result is the fixed limit: (binomial transform of [1,1,2,5,15,...] = (1,2,5,15,52,...).  Gary W. Adamson, Jan 14 2009
From Karol A. Penson, May 03 2009: (Start)
Relation between the Bell numbers B(n) and the nth derivative of 1/Gamma(1+x) of such derivatives through seq(subs(x=0, simplify(diff(GAMMA(1+x)^(1),x$n))), n=1..6);
b) leave them expressed in terms of digamma (Psi(k)) and polygamma (Psi(k,n)) functions and unevaluated;
Examples of such expressions, for n=1..5, are:
n=1: Psi(1),
n=2: (Psi(1)^2+Psi(1,1)),
n=3: Psi(1)^3+3*Psi(1)*Psi(1,1)Psi(2,1),
n=4: (Psi(1)^4+6*Psi(1)^2*Psi(1,1)3*Psi(1,1)^24*Psi(1)*Psi(2,1)+Psi(3, 1)),
n=5: Psi(1)^5 +10*Psi(1)^3*Psi(1,1) 15*Psi(1)*Psi(1,1)^2 10*Psi(1)^2*Psi(2,1) +10*Psi(1,1)*Psi(2,1) +5*Psi(1)*Psi(3,1) Psi(4,1);
c) for a given n, read off the sum of absolute values of coefficients of every term involving digamma or polygamma functions.
This sum is equal to B(n). Examples: B(1)=1, B(2)=1+1=2, B(3)=1+3+1=5, B(4)=1+6+3+4+1=15, B(5)=1+10+15+10+10+5+1=52;
d) Observe that this decomposition of the Bell number B(n) apparently does not involve the Stirling numbers of the second kind explicitly.
(End)
The numbers given above by Penson lead to the multinomial coefficients A036040.  Johannes W. Meijer, Aug 14 2009
Column 1 of A162663.  Franklin T. AdamsWatters, Jul 09 2009
Asymptotic expansions (0!+1!+2!+...+(n1)!)/(n1)! = a(0) + a(1)/n + a(2)/n^2 + ... and (0!+1!+2!+...+n!)/n! = 1 + a(0)/n + a(1)/n^2 + a(2)/n^3 + ....  Michael Somos, Jun 28 2009
Starting with offset 1 = row sums of triangle A165194.  Gary W. Adamson, Sep 06 2009
a(n+1) = A165196(2^n); where A165196 begins: (1, 2, 4, 5, 7, 12, 14, 15, ...). such that A165196(2^3) = 15 = A000110(4).  Gary W. Adamson, Sep 06 2009
The divergent series g(x=1,m) = 1^m*1!  2^m*2! + 3^m*3!  4^m*4! + ..., m >= 1, which for m=1 dates back to Euler, is related to the Bell numbers. We discovered that g(x=1,m) = (1)^m * (A040027(m)  A000110(m+1) * A073003). We observe that A073003 is Gompertz's constant and that A040027 was published by Gould, see for more information A163940.  Johannes W. Meijer, Oct 16 2009
a(n)= E(X^n), i.e., the nth moment about the origin of a random variable X that has a Poisson distribution with (rate) parameter, lambda = 1.  Geoffrey Critzer, Nov 30 2009
Let A000110 = S(x), then S(x) = A(x)/A(x^2) when A(x) = A173110; or (1, 1, 2, 5, 15, 52, ...) = (1, 1, 3, 6, 20, 60, ...) / (1, 0, 1, 0, 3, 0, 6, 0, 20, ...).  Gary W. Adamson, Feb 09 2010
The Bell numbers serve as the upper limit for the number of distinct homomorphic images from any given finite universal algebra. Every algebra homomorphism is determined by its kernel, which must be a congruence relation. As the number of possible congruence relations with respect to a finite universal algebra must be a subset of its possible equivalence classes (given by the Bell numbers), it follows naturally.  Max Sills, Jun 01 2010
For a proof of the o.g.f. given in the R. Stephan comment see, e.g., the W. Lang link under A071919.  Wolfdieter Lang, Jun 23 2010
Let B(x) = (1 + x + 2x^2 + 5x^3 + ...). Then B(x) is satisfied by A(x)/A(x^2) where A(x) = polcoeff A173110: (1 + x + 3x^2 + 6x^3 + 20x^4 + 60x^5 + ...) = B(x) * B(x^2) * B(x^4) * B(x^8) * ....  Gary W. Adamson, Jul 08 2010
Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1) equals the number of ways to choose 0 or more balls of each color without choosing any two colors the same positive number of times. (See related comments for A000108, A008277, A016098.)  Matthew Vandermast, Nov 22 2010
A binary counter with faulty bits starts at value 0 and attempts to increment by 1 at each step. Each bit that should toggle may or may not do so. a(n) is the number of ways that the counter can have the value 0 after n steps. E.g., for n=3, the 5 trajectories are 0,0,0,0; 0,1,0,0; 0,1,1,0; 0,0,1,0; 0,1,3,0.  David Scambler, Jan 24 2011
No Bell number is divisible by 8, and no Bell number is congruent to 6 modulo 8; see Theorem 6.4 and Table 1.7 in Lunnon, Pleasants and Stephens.  Jon Perry, Feb 07 2011, clarified by Eric Rowland, Mar 26 2014
a(n+1) is the number of (symmetric) positive semidefinite n X n 01 matrices. These correspond to equivalence relations on {1,...,n+1}, where matrix element M[i,j] = 1 if and only if i and j are equivalent to each other but not to n+1.  Robert Israel, Mar 16 2011
a(n) is the number of monotoniclabeled forests on n vertices with rooted trees of height less than 2. We note that a labeled rooted tree is monotoniclabeled if the label of any parent vertex is greater than the label of any offspring vertex. See link "Counting forests with Stirling and Bell numbers".  Dennis P. Walsh, Nov 11 2011
a(n) = D^n(exp(x)) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf. A000772 and A094198.  Peter Bala, Nov 25 2011
B(n) counts the length n+1 rhyme schemes without repetitions. E.g., for n=2 there are 5 rhyme schemes of length 3 (aaa, aab, aba, abb, abc), and the 2 without repetitions are aba, abc. This is basically O. Munagi's result that the Bell numbers count partitions into subsets of nonconsecutive integers (see comment above dated Mar 20 2005).  Eric Bach, Jan 13 2012
Number n is prime if mod(a(n)2,n) = 0. Dmitry Kruchinin, Feb 14 2012
Right and left borders and row sums of A212431 = A000110 or a shifted variant.  Gary W. Adamson, Jun 21 2012
Number of maps f: [n] > [n] where f(x)<=x and f(f(x))=f(x) (projections).  Joerg Arndt, Jan 04 2013
Permutations of [n] avoiding any given one of the 8 dashed patterns in the equivalence classes (i) 123, 321, 123, 321, and (ii) 132, 312, 213, 231. (See Claesson 2001 reference.)  David Callan, Oct 03 2013
Conjecture: No a(n) has the form x^m with m > 1 and x > 1.  ZhiWei Sun, Dec 02 2013
Sum_{n>=0} a(n)/n! = e^(e1) = 5.57494152476... , see A234473.  Richard R. Forberg, Dec 26 2013 (This is the e.g.f. for x=1.  Wolfdieter Lang, Feb 02 2015)
Sum_{j=0..n} binomial(n,j)*a(j) = (1/e)*Sum_{k>=0} (k+1)^n/k! = (1/e) Sum_{k=1..infinity} k^(n+1)/k! = a(n+1), n >= 0, using the Dobinski formula. See the comment by Gary W. Adamson, Dec 04 2008 on the Pascal eigensequence.  Wolfdieter Lang, Feb 02 2015
In fact it is not really an eigensequence of the Pascal matrix; rather the Pascal matrix acts on the sequence as a shift. It is an eigensequence (the unique eigensequence with eigenvalue 1) of the matrix derived from the Pascal matrix by adding at the top the row [1, 0, 0, 0 ...]. The binomial sum formula may be derived from the definition in terms of partitions: label any element X of a set S of N elements, and let X(k) be the number of subsets of S containing X with k elements. Since each subset has a unique coset, the number of partitions p(N) of S is given by p(N) = Sum_{k=1..N} (X(k) p(Nk)); trivially X(k) = N1 choose k1.  Mason Bogue, Mar 20 2015
a(n) is the number of ways to nest n matryoshkas (Russian nesting dolls): we may identify {1, 2, ..., n} with dolls of ascending sizes and the sets of a set partition with stacks of dolls.  Carlo Sanna, Oct 17 2015


REFERENCES

Stefano Aguzzoli, Brunella Gerla and Corrado Manara, Poset Representation for Goedel and Nilpotent Minimum Logics, in Symbolic and Quantitative Approaches to Reasoning with Uncertainty, Lecture Notes in Computer Science, Volume 3571/2005, SpringerVerlag. [Added by N. J. A. Sloane, Jul 08 2009]
M. Aigner, A characterization of the Bell numbers, Discr. Math., 205 (1999), 207210.
M. Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 25442563.
S. Ainley, Problem 19, QARCH, No. IV, Nov 03, 1980.
J.P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 205.
W. Asakly, A. Blecher, C. Brennan, A. Knopfmacher, T. Mansour, S. Wagner, Set partition asymptotics and a conjecture of Gould and Quaintance, Journal of Mathematical Analysis and Applications, Volume 416, Issue 2, 15 August 2014, Pages 672682.
J. Balogh, B. Bollobas and D. Weinreich, A jump to the Bell numbers for hereditary graph properties, J. Combin. Theory Ser. B 95 (2005), no. 1, 2948.
R. E. Beard, On the coefficients in the expansion of exp(exp(t)) and exp(exp(t)), J. Institute Actuaries, 76 (1951), 152163.
H. W. Becker, Abstracts of two papers related to Bell numbers, Bull. Amer. Math. Soc., 52 (1946), p. 415.
H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 2326.
H. W. Becker and D. H. Browne, Problem E461 and solution, American Mathematical Monthly, Vol. 48 (1941), pp. 701703.
E. T. Bell, Exponential numbers, Amer. Math. Monthly, 41 (1934), 411419.
E. T. Bell, Exponential polynomials, Ann. Math., 35 (1934), 258277.
E. T. Bell, The iterated exponential numbers, Ann. Math., 39 (1938), 539557.
C. M. Bender, D. C. Brody and B. K. Meister, Quantum Field Theory of Partitions, J. Math. Phys., 40,7 (1999), 323945.
E. A. Bender and J. R. Goldman, Enumerative uses of generating functions, Indiana Univ. Math. J., 20 (1971), 753765.
G. Birkhoff, Lattice Theory, Amer. Math. Soc., Revised Ed., 1961, p. 108, Ex. 1.
M. T. L. Bizley, On the coefficients in the expansion of exp(lambda exp(t)), J. Inst. Actuaries, 77 (1952), p. 122.
Borwein, D., Rankin, S. and Renner, L. Enumeration of injective partial transformations. Discrete Math. (1989), 73: 291296. [From Abdullahi Umar, Oct 12 2008]
J. M. Borwein, D. H. Bailey and R. Girgensohn, Experimentation in Mathematics, A K Peters, Ltd., Natick, MA, 2004. x+357 pp. See p. 41.
David Callan, A Combinatorial Interpretation of the Eigensequence for Composition, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.4.
Carlier, Jacques; and Lucet, Corinne; A decomposition algorithm for network reliability evaluation. In First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz). Discrete Appl. Math. 65 (1996), 141156.
M. E. Cesaro, Sur une equation aux differences melees, Nouvelles Annales de Math. (3), Tome 4, (1885), 3640.
S. D. Chatterji, The number of topologies on n points, Manuscript, 1966.
Anders Claesson, Generalized Pattern Avoidance, European Journal of Combinatorics, 22 (2001) 961971.
C. Coker, A family of eigensequences, Discrete Math. 282 (2004), 249250.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 210.
J. H. Conway et al., The Symmetries of Things, Peters, 2008, p. 207.
N. G. de Bruijn, Asymptotic Methods in Analysis, Dover, 1981, Sections 3.3. Case b and 6.16.3.
J.M. De Koninck, Ces nombres qui nous fascinent, Entry 52, p. 19, Ellipses, Paris 2008.
Ayhan Dil and Veli Kurt, Polynomials related to harmonic numbers and evaluation of harmonic number series I, INTEGERS, 12 (2012), #A38.  From N. J. A. Sloane, Feb 08 2013
G. Dobinski, Summierung der Reihe Sum(n^m/n!) fuer m = 1, 2, 3, 4, 5, . . ., Grunert Archiv (Arch. f. Math. und Physik), 61 (1877) 333336.
Doslic, Tomislav and Veljan, Darko. Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 21822212. MR2404544 (2009j:05019).
Branko Dragovich, Andrei Yu. Khrennikov, Natasa Z. Misic, Summation of pAdic Functional Series in Integer Points, arXiv:1508.05079, 2015
B. Dragovich, N. Z. Misic, pAdic invariant summation of some padic functional series, PAdic Numbers, Ultrametric Analysis, and Applications, October 2014, Volume 6, Issue 4, pp 275283. DOI: 10.1134/S2070046614040025.
L. F. Epstein, A function related to the series for exp(exp(z)), J. Math. and Phys., 18 (1939), 153173.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
Flajolet, Philippe and Schott, Rene, Nonoverlapping partitions, continued fractions, Bessel functions and a divergent series, European J. Combin. 11 (1990), no. 5, 421432.
Martin Gardner, Fractal Music, Hypercards and More (Freeman, 1992), Chapter 2.
H. W. Gould, Research bibliography of two special number sequences, Mathematica Monongaliae, Vol. 12, 1971.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, AddisonWesley, 2nd ed., p. 493.
W. S. Gray and M. Thitsa, System Interconnections and Combinatorial Integer Sequences, in: System Theory (SSST), 2013 45th Southeastern Symposium on, Date of Conference: 1111 March 2013, Digital Object Identifier: 10.1109/SSST.2013.6524939.
Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5.  From N. J. A. Sloane, Sep 16 2012
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 26.
M. Klazar, Counting even and odd partitions, Amer. Math. Monthly, 110 (No. 6, 2003), 527532.
D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 418).
Nate Kube and Frank Ruskey, Sequences That Satisfy a(na(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.
Christian Kramp, Der polynomische Lehrsatz (Leipzig: 1796), 113.
G. Labelle et al., Stirling numbers interpolation using permutations with forbidden subsequences, Discrete Math. 246 (2002), 177195.
Labelle, Jacques. "Applications diverses de la théorie combinatoire des especes de structures." Ann. Sci. Math. Québec, 7.1 (1983): 5994.
Lehmer, D. H. Some recursive sequences. Proceedings of the Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1971), pp. 1530. Dept. Comput. Sci., Univ. Manitoba, Winnipeg, Man., 1971. MR0335426 (49 #208)
Levine, Jack. "A binomial identity related to rhyming sequences." Mathematics Magazine, 32 (1958): 7174.
J. Levine and R. E. Dalton, Minimum periods, modulo p, of firstorder Bell exponential integers, Math. Comp., 16 (1962), 416423.
Levinson, H.; Silverman, R. Topologies on finite sets. II. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 699712, Congress. Numer., XXIIIXXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561090 (81c:54006)  From N. J. A. Sloane, Jun 05 2012
S. Linusson, The number of Msequences and fvectors, Combinatorica, 19 (1999), 255266.
L. Lovasz, Combinatorial Problems and Exercises, NorthHolland, 1993, pp. 1415.
W. F. Lunnon, P. A. B. Pleasants and N. M. Stephens, Arithmetic properties of Bell numbers to a composite modulus I, Acta Arithmetica 35 (1979) 116.
Toufik Mansour, Matthias Schork and Mark Shattuck, The Generalized Stirling and Bell Numbers Revisited, Journal of Integer Sequences, Vol. 15 (2012), #12.8.3.
M. Meier, On the number of partitions of a given set, Amer. Math. Monthly, 114 (2007), p. 450.
N. S. Mendelsohn, Number of equivalence relations for n elements, Problem 4340, Amer. Math. Monthly 58 (1951), 4648.
Istvan Mezo, The Dual of Spivey's Bell Number Formula, Journal of Integer Sequences, Vol. 15 (2012), #12.2.4.
N. Moreira and R. Reis, On the Density of Languages Representing Finite Set Partitions, Journal of Integer Sequences, Vol. 8 (2005), Article 05.2.8.
Moser, Leo, and Max Wyman. An asymptotic formula for the Bell numbers. Trans. Royal Soc. Canada, 49 (1955), 4953.
A. O. Munagi, kComplementing Subsets of Nonnegative Integers, International Journal of Mathematics and Mathematical Sciences, 2005:2, (2005), 215224.
A. Murthy, Generalization of partition function, introducing Smarandache factor partition, Smarandache Notions Journal, Vol. 11, No. 123, Spring 2000.
Amarnath Murthy and Charles Ashbacher, Generalized Partitions and Some New Ideas on Number Theory and Smarandache Sequences, Hexis, Phoenix; USA 2005. See Section 1.4,1.8.
P. Peart, Hankel determinants via Stieltjes matrices. Proceedings of the Thirtyfirst Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000). Congr. Numer. 144 (2000), 153159.
Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.
M. Rayburn, On the Borel fields of a finite set, Proc. Amer. Math. Soc., 19 (1968), 885889.
C. Reid, The alternative life of E. T. Bell, Amer. Math. Monthly, 108 (No. 5, 2001), 393402.
A. M. Robert, A Course in padic Analysis, SpringerVerlag, 2000; p. 212.
G.C. Rota, The number of partitions of a set. Amer. Math. Monthly 71 1964 498504.
G.C. Rota, Finite Operator Calculus.
Frank Ruskey, Jennifer Woodcock and Yuji Yamauchi, Counting and computing the Rand and block distances of pairs of set partitions, Journal of Discrete Algorithms, Volume 16, October 2012, Pages 236248.
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; see Section 1.4 and Example 5.2.4.
Umar, A. On the semigroups of orderdecreasing finite full transformations, Proc. Roy. Soc. Edinburgh 120A (1992), 129142. [From Abdullahi Umar, Oct 12 2008]
Umar, A. On the semigroups of partial onetoone orderdecreasing finite transformations, Proc. Roy. Soc. Edinburgh 123A (1993), 355363. [From Abdullahi Umar, Oct 12 2008]
Yang, Winston. Bell numbers and ktrees. Discrete Math. 156(1996), no. 13, 247252. MR1405023 (97c:05004)


LINKS

Simon Plouffe, Table of n, a(n) for n = 0..500
S. Ainley, Problem 19, QARCH, No. IV, Nov 03, 1980. [Annotated scanned copy]
Tewodros Amdeberhan, Valerio de Angelis and Victor H. Moll, Complementary Bell numbers: arithmetical properties and Wilf's conjecture
R. Aldrovandi and L. P. Freitas, Continuous iteration of dynamical maps
Joerg Arndt, Matters Computational (The Fxtbook), p.151, p.358, and p. 368.
J. Arndt, Subsetlex: did we miss an order?, arXiv:1405.6503, 2014
E. Baake, M. Baake, M. Salamat, The general recombination equation in continuous time and its solution, arXiv preprint arXiv:1409.1378, 2014
Pat Ballew, Bell Numbers
C. Banderier, M. BousquetMélou, A. Denise, P. Flajolet, D. Gardy and D. GouyouBeauchamps, Generating Functions for Generating Trees, Discrete Mathematics 246(13), March 2002, pp. 2955.
Elizabeth Banjo, Representation theory of algebras related to the partition algebra, Unpublished Doctoral thesis, City University London, 2013.
J.L. Baril, T. Mansour, and A. Petrossian, Equivalence classes of permutations modulo excedances, 2014.
P. Barry, Invariant number triangles, eigentriangles and Somos4 sequences, arXiv preprint arXiv:1107.5490, 2011.
D. Barsky, Analyse padique et suites classiques de nombres, Sem. Loth. Comb. B05b (1981) 121.
R. E. Beard, On the Coefficients in the Expansion of e^(e^t) and e^(e^t), J. Institute of Actuaries, 76 (1950), 152163. [Annotated scanned copy]
H. W. Becker, Abstracts of two papers from 1946 related to Bell numbers [Annotated scanned copy]
H. W. Becker, Rooks and rhymes, Math. Mag., 22 (1948/49), 2326. [Annotated scanned copy]
E. A. Bender and J. R. Goldman, Enumerative uses of generating functions, Indiana Univ. Math. J., 20 (1971), 753765. [Annotated scanned copy]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226228 (1995), 5772; erratum 320 (2000), 210.
M. T. L. Bizley, On the coefficients in the expansion of exp(lambda exp(t)), J. Inst. Actuaries, 77 (1952), p. 122. [Annotated scanned copy]
P. Blasiak, K. A. Penson and A. I. Solomon, The Boson Normal Ordering Problem and Generalized Bell Numbers
P. Blasiak, K. A. Penson and A. I. Solomon, The general boson normal ordering problem.
H. Bottomley, Illustration of initial terms
A. Burstein and I. Lankham, Combinatorics of patience sorting piles
David Callan, A Combinatorial Interpretation of the Eigensequence for Composition.
David Callan, Cesaro's Integral Formula for the Bell Numbers (Corrected).
David Callan, Cesaro's integral formula for the Bell numbers (corrected).
David Callan and Emeric Deutsch, The Run Transform, arXiv preprint arXiv:1112.3639, 2011
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
S. D. Chatterji, The number of topologies on n points, Manuscript, 1966 [Annotated scanned copy]
K.W. Chen, Algorithms for Bernoulli numbers and Euler numbers, J. Integer Sequences, 4 (2001), #01.1.6.
B. Chern, P. Diaconis, D. M. Kane, and R. C. Rhoades, Central limit theorems for some set partition statistics, 2014.
A. Claesson and T. Mansour, Counting patterns of type (1,2) or (2,1).
Martin Cohn, Shimon Even, Karl Menger, Jr., and Philip K. Hooper, On the Number of Partitionings of a Set of n Distinct Objects, Amer. Math. Monthly 69 (1962), no. 8, 782785. MR1531841.
Martin Cohn, Shimon Even, Karl Menger, Jr., and Philip K. Hooper, On the Number of Partitionings of a Set of n Distinct Objects, Amer. Math. Monthly 69 (1962), no. 8, 782785. MR1531841. [Annotated scanned copy]
C. Cooper and R. E. Kennedy, Patterns, automata and Stirling numbers of the second kind, Mathematics and Computer Education Journal, 26 (1992), 120124. [From Peter Bala, Oct 19 2008]
Éva Czabarka, Péter L. Erdős, Virginia Johnson, Anne Kupczok and László A. Székely, Asymptotically normal distribution of some tree families relevant for phylogenetics, and of partitions without singletons, arXiv preprint arXiv:1108.6015, 2011
Gesualdo Delfino and Jacopo Viti, Potts qcolor field theory and scaling random cluster model, arXiv preprint arXiv:1104.4323, 2011.
R. M. Dickau, Bell number diagrams
R. Ehrenborg and M. Readdy, Juggling and applications to qanalogues, Discrete Math. 157 (1996), 107125.
L. F. Epstein, A function related to the series for exp(exp(z)), J. Math. and Phys., 18 (1939), 153173. [Annotated scanned copy]
M. Erné, Struktur und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221259.
FindStat  Combinatorial Statistic Finder, Set partitions
John Fiorillo, GENJIMON
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 109, 110
H. Fripertinger, The Bell Numbers
Daniel L. Geisler, Combinatorics of Iterated Functions
A. Gertsch and A. M.Robert, Some congruences concerning the Bell numbers
Jekuthiel Ginsburg, Iterated exponentials, Scripta Math., 11 (1945), 340353. [Annotated scanned copy]
H. W. Gould, J. Quaintance, Implications of Spivey's Bell Number formula, JIS 11 (2008) 08.3.7
Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786, 2012.  From N. J. A. Sloane, Sep 17 2012
Gottfried Helms, Bell Numbers, 2008.
A. Hertz and H. Melot, Counting the Number of NonEquivalent Vertex Colorings of a Graph, Les Cahiers du GERAD G201382
M. E. Hoffman, Updown categories: Generating functions and universal covers, arXiv preprint arXiv:1207.1705, 2012.  From N. J. A. Sloane, Dec 22 2012
A. Horzela, P. Blasiak, G. E. H. Duchamp, K. A. Penson and A. I. Solomon, A product formula and combinatorial field theory
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 15, Encyclopedia of Combinatorial Structures 65, Encyclopedia of Combinatorial Structures 73, Encyclopedia of Combinatorial Structures 291 [broken links]
F. Johansson, Computing Bell numbers, Aug 6, 2015
J. Katriel, On a generalized recurrence for Bell Numbers, JIS 11 (2008) 08.3.8
M. Klazar, Bell numbers, their relatives and algebraic differential equations, J. Combin. Theory, A 102 (2003), 6387.
M. Klazar, Bell numbers, their relatives and algebraic differential equations, J. Combin. Theory, A 102 (2003), 6387.
A. Knutson, Siteswap FAQ, Section 5, Working backwards, defines the term "orbit" in siteswap notation.
Kazuhiro Kunii, Genjikoh no zu [Japanese page illustrating a(5) = 52]
W. Lang, On generalizations of Stirling number triangles, J. Integer Seqs., Vol. 3 (2000), #00.2.4.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Peter Luschny, Set partitions and Bell numbers
Toufik Mansour and Mark Shattuck, A recurrence related to the Bell numbers, INTEGERS 11 (2011), #A67.
R. J. Marsh and P. P. Martin, Pascal arrays: counting Catalan sets
MathOverflow, Ordinary Generating Function for Bell Numbers
Romeo Mestrovic, Variations of Kurepa's left factorial hypothesis, arXiv preprint arXiv:1312.7037, 2013
I. Mezo and A. Baricz, On the generalization of the Lambert W function with applications in theoretical physics, arXiv preprint arXiv:1408.3999, 2014
Leo Moser and Max Wyman, An asymptotic formula for the Bell numbers, Trans. Royal Soc. Canada, 49 (1955), 4953. [Annotated scanned copy]
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167176. [Annotated, scanned copy]
A. O. Munagi, kComplementing Subsets of Nonnegative Integers, International Journal of Mathematics and Mathematical Sciences, 2005:2 (2005), 215224.
A. M. Odlyzko, Asymptotic enumeration methods, pp. 10631229 of R. L. Graham et al., eds., Handbook of Combinatorics, 1995; see Examples 5.4 and 12.2. (pdf, ps)
OEIS Wiki, Sorting numbers
K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinskitype relations via substitution and the moment problem
K. A. Penson, P. Blasiak, A. Horzela, G. H. E. Duchamp and A. I. Solomon, Laguerretype derivatives: Dobinski relations and combinatorial identities, J. Math. Phys. vol. 50, 083512 (2009)
K. A. Penson and J.M. Sixdeniers, Integral Representations of Catalan and Related Numbers, J. Integer Sequences, 4 (2001), #01.2.5.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Simon Plouffe, Table of n, a(n) for n = 0..3015
Simon Plouffe, Bell numbers (first 1000 terms)
T. Prellberg, On the asymptotic analysis of a class of linear recurrences (slides).
R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv math.CO.0606404.
Feng Qi, An Explicit Formula for Bell Numbers in Terms of Stirling Numbers and Hypergeometric Functions, arXiv:1402.2361, 2014.
C. Radoux, Determinants de Hankel et theoreme de Sylvester
S. Ramanujan, Notebook entry
M. Rayburn, On the Borel fields of a finite set, Proc. Amer. Math.. Soc., 19 (1968), 885889. [Annotated scanned copy]
M. Rayburn and N. J. A. Sloane, Correspondence, 1974
H. P. Robinson, Letter to N. J. A. Sloane, Jul 12 1971
Ivo Rosenberg; The number of maximal closed classes in the set of functions over a finite domain, J. Combinatorial Theory Ser. A 14 (1973), 17.
A. Ross, PlanetMath.org, Bell number
Eric Rowland, Bell numbers modulo 8, in Combinatorics and Algorithmics of Strings, 2014, page 42
M. Shattuck, Combinatorial proofs of some Bell number formulas, arXiv preprint arXiv:1401.6588, 2014
M. Shattuck, Generalized rLah numbers, arXiv preprint arXiv:1412.8721 [math.CO], 2014.
T. Sillke, Bell numbers
A. I. Solomon, P. Blasiak, G. Duchamp, A. Horzela and K. A. Penson, Combinatorial physics, normal order and model Feynman graphs.
A. I. Solomon, P. Blasiak, G. Duchamp, A. Horzela and K. A. Penson, Partition functions and graphs: A combinatorial approach.
Michael Z. Spivey, A generalized recurrence for Bell numbers, J. Integer Sequences, Vol. 11 (2008), Article 08.2.5.
Z.W. Sun, Conjectures involving arithmetical sequences, Number Theory: Arithmetic in Shangrila (eds., S. Kanemitsu, H.Z. Li and J.Y. Liu), Proc. the 6th ChinaJapan Sem. Number Theory (Shanghai, August 1517, 2011), World Sci., Singapore, 2013, pp. 244258.  From N. J. A. Sloane, Dec 28 2012
J. Touchard, Nombres exponentiels et nombres de Bernoulli, Canad. J. Math., 8 (1956), 305320.
C. G. Wagner, Letter to N. J. A. Sloane, Sep 30 1974
D. P. Walsh, Counting forests with Stirling and Bell numbers
Yi Wang and BaoXuan Zhu, Proofs of some conjectures on monotonicity of numbertheoretic and combinatorial sequences, arXiv preprint arXiv:1303.5595, 2013
F. V. Weinstein, Notes on Fibonacci partitions, arXiv:math/0307150 [math.NT] (see page 16).
Eric Weisstein's World of Mathematics, Bell Number, Bell Triangle, Binomial Transform, Stirling Transform, and Subfactorial
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, pp. 21ff.
Roman Witula, Damian Slota and Edyta Hetmaniok, Bridges between different known integer sequences, Annales Mathematicae et Informaticae, 41 (2013) pp. 255263.
The Wolfram Functions Site, Generalized Incomplete Gamma Function.
Dekai Wu, K. Addanki and M. Saers, Modeling Hip Hop Challenge Response Lyrics as Machine Translation, in Sima'an, K., Forcada, M.L., Grasmick, D., Depraetere, H., Way, A. (eds.) Proceedings of the XIV Machine Translation Summit (Nice, September 26, 2013), p. 109116.
D. Wuilquin, Letters to N. J. A. Sloane, August 1984
Alexander Yong, The Joseph Greenberg problem: combinatorics and comparative linguistics, arXiv preprint arXiv:1309.5883, 2013
Index entries for "core" sequences
Index entries for sequences related to juggling
Index entries for sequences related to partitions
Index entries for sequences related to rooted trees


FORMULA

E.g.f.: exp(exp(x)  1).
Recurrence: a(n+1) = Sum a(k)*binomial(n, k).
a(n) = Sum_{k=0..n} Stirling2(n, k).
a(n) = Sum_{j=0..n1} (1/(n1)!)*A000166(j)*binomial(n1, j)*(nj)^(n1).  André F. Labossière, Dec 01 2004
G.f.: (Sum_{k=0..infinity} 1/((1k*x)*k!))/exp(1) = hypergeom([ 1/x], [(x1)/x], 1)/exp(1) = ((12*x)+LaguerreL(1/x, (x1)/x, 1)+x*LaguerreL(1/x, (2*x1)/x, 1))*Pi/(x^2*sin(Pi*(2*x1)/x)), where LaguerreL(mu, nu, z) =( GAMMA(mu+nu+1)/GAMMA(mu+1)/GAMMA(nu+1))* hypergeom([ mu], [nu+1], z) is the Laguerre function, the analytic extension of the Laguerre polynomials, for mu not equal to a nonnegative integer. This generating function has an infinite number of poles accumulating in the neighborhood of x=0. Karol A. Penson, Mar 25 2002
a(n) = exp(1)*Sum_{k >= 0} k^n/k! [Dobinski].  Benoit Cloitre, May 19 2002
a(n) is asymptotic to n!*(2 Pi r^2 exp(r))^(1/2) exp(exp(r)1) / r^n, where r is the positive root of r exp(r) = n. See, e.g., the Odlyzko reference.
a(n) is asymptotic to b^n*exp(bn1/2)*sqrt(b/(b+n)) where b satisfies b*log(b) = n  1/2 (see Graham, Knuth and Patashnik, Concrete Mathematics, 2nd ed., p. 493).  Benoit Cloitre, Oct 23 2002, corrected by Vaclav Kotesovec, Jan 06 2013
Lovasz (Combinatorial Problems and Exercises, NorthHolland, 1993, Section 1.14, Problem 9) gives another asymptotic formula, quoted by Mezo and Baricz.  N. J. A. Sloane, Mar 26 2015
G.f.: Sum_{k>=0} x^k/(Product_{j=1..k} 1jx) (see Klazar for a proof).  Ralf Stephan, Apr 18 2004
a(n+1) = exp(1)*Sum_{k>=0} (k+1)^(n)/k!.  Gerald McGarvey, Jun 03 2004
For n>0, a(n) = Aitken(n1, n1) [i.e., a(n1, n1) of Aiken's array (A011971)].  Gerald McGarvey, Jun 26 2004
a(n) = Sum_{k=1..n} (1/k!)*(Sum_{i=1..k} (1)^(ki)*binomial(k, i)*i^n+0^n).  Paul Barry, Apr 18 2005
a(n) = A032347(n) + A040027(n+1).  Jon Perry, Apr 26 2005
a(n) = 2*n!/(Pi*e)*Im( integral_{0}^{Pi} e^(e^(e^(ix))) sin(nx) dx ) where Im denotes imaginary part [Cesaro].  David Callan, Sep 03 2005
O.g.f.: 1/(1xx^2/(12*x2*x^2/(13*x3*x^2/(.../(1n*xn*x^2/(...)))))) (continued fraction due to Ph. Flajolet).  Paul D. Hanna, Jan 17 2006
From Karol A. Penson, Jan 14 2007: (Start)
Representation of Bell numbers B(n), n=1,2..., as special values of hypergeometric function of type (n1)F(n1), in Maple notation: B(n)=exp(1)*hypergeom([2,2,...,2],[1,1,...,1],1), n=1,2..., i.e. having n1 parameters all equal to 2 in the numerator, having n1 parameters all equal to 1 in the denominator and the value of the argument equal to 1.
Examples:
B(1)=exp(1)*hypergeom([],[],1)=1
B(2)=exp(1)*hypergeom([2],[1],1)=2
B(3)=exp(1)*hypergeom([2,2],[1,1],1)=5
B(4)=exp(1)*hypergeom([2,2,2],[1,1,1],1)=15
B(5)=exp(1)*hypergeom([2,2,2,2],[1,1,1,1],1)=52
(Warning: this formula is correct but its application by a computer may not yield exact results, especially with a large number of parameters.)
(End)
a(n+1) = 1 + Sum_{k=0..n1} Sum_{i=0..k} binomial(k,i))*(2^(ki))*a(i).  Yalcin Aktar, Feb 27 2007
a(n) = [1,0,0,...,0] T^(n1) [1,1,1,...,1]', where T is the n X n matrix with main diagonal {1,2,3,...,n}, 1's on the diagonal immediately above and 0's elsewhere. [Meier]
a(n) = ((2*n!)/(Pi * e)) * ImaginaryPart(Integral[from 0 to Pi](e^e^e^(i*theta))*sin(n*theta) dtheta).  Jonathan Vos Post, Aug 27 2007
From Tom Copeland, Oct 10 2007: (Start)
a(n) = T(n,1) = Sum_{j=0...n} S2(n,j) = Sum_{j=0...n} E(n,j) * Lag(n,1,jn) = Sum_{j=0...n} [ E(n,j)/n! ] * [ n!*Lag(n,1, jn) ] where T(n,x) are the Bell / Touchard / exponential polynomials; S2(n,j), the Stirling numbers of the second kind; E(n,j), the Eulerian numbers; and Lag(n,x,m), the associated Laguerre polynomials of order m. Note that E(n,j)/n! = E(n,j) / (Sum_{k=0...n} E(n,k)).
The Eulerian numbers count the permutation ascents and the expression [n!*Lag(n,1, jn)] is A086885 with a simple combinatorial interpretation in terms of seating arrangements, giving a combinatorial interpretation to n!*a(n) = Sum_{j=0..n} E(n,j) * [n!*Lag(n,1, jn)].
(End)
Define f_1(x),f_2(x),... such that f_1(x)=e^x and for n=2,3,... f_{n+1}(x)=diff(x*f_n(x),x). Then for Bell numbers B_n we have B_n=1/e*f_n(1).  Milan Janjic, May 30 2008
a(n) = (n1)! Sum_{k=1..n} a(nk)/((nk)! (k1)!) where a(0)=1.  Thomas Wieder, Sep 09 2008
a(n+k) = Sum_{m=0..n} Stirling2(n,m) Sum_{r=0..k} binomial(k,r) m^r a(kr).  David Pasino (davepasino(AT)yahoo.com), Jan 25 2009. (Umbrally, this may be written as a(n+k) = Sum_{m=0..n} Stirling2(n,m) (a+m)^k.  N. J. A. Sloane, Feb 07 2009.)
From Thomas Wieder, Feb 25 2009: (Start)
a(n) = Sum_{k_1=0..n+1} Sum_{k_2=0..n}...Sum_{k_i=0..ni}...Sum_{k_n=0..1}
delta(k_1,k_2,...,k_i,...,k_n)
where delta(k_1,k_2,...,k_i,...,k_n) = 0 if any k_i > k_(i+1) and k_(i+1) <> 0
and delta(k_1,k_2,...,k_i,...,k_n) = 1 otherwise.
(End)
Let A be the upper Hessenberg matrix of order n defined by: A[i,i1]=1, A[i,j]:=binomial(j1,i1), (i<=j), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det(A).  Milan Janjic, Jul 08 2010
G.f. satisfies A(x)=(x/(1x))*A(x/(1x)) + 1.  Vladimir Kruchinin, Nov 28 2011
G.f.: 1 / (1  x / (1  1*x / (1  x / (1  2*x / (1  x / (1  3*x / ... )))))).  Michael Somos, May 12 2012
a(n+1) = Sum_{m=0..n} Stirling2(n, m)*(m+1), n >= 0. Compare with the third formula for a(n) above. Here Stirling2 = A048993.  Wolfdieter Lang, Feb 03 2015
G.f.: (1)^(1/x)*((1/x)!/e + (!(11/x))/x) where z! and !z are factorial and subfactorial generalized to complex arguments.  Vladimir Reshetnikov, Apr 24 2013
The following formulas were proposed during the period Dec 2011  Oct 2013 by Sergei N. Gladkovskii. (Start)
E.g.f.: exp(exp(x)1) = 1+x/(G(0)x); G(k) = (k+1)*Bell(k)+x*Bell(k+1)x*(k+1)*Bell(k)*Bell(k+2)/G(k+1) (continued fraction).
G.f.: W(x)=(11/(G(0)+1))/exp(1) ; G(k)= x*k^2 + (3*x1)*k  2 + x  (k+1)*(x*k+x1)^2/G(k+1); (continued fraction Euler's kind, 1step).
G.f.: W(x)= (1 + G(0)/(x^23*x+2))/exp(1); G(k)= 1 (x*k+x1)/( ((k+1)!) (((k+1)!)^2)*(1xk*x+(k+1)!)/( ((k+1)!)*(1xk*x+(k+1)!)  (x*k+2*x1)*(12*xk*x+(k+2)!)/G(k+1))); (continued fraction).
G.f.: A(x)= 1/(1  x/(1x/(1 + x/G(0)))); G(k)= x  1 + x*k + x*(x1+x*k)/G(k+1); (continued fraction, 1step).
G.f.: 1/U(0) where U(k)= x*k  1 + x  x^2*(k+1)/U(k+1); (continued fraction, 1step).
G.f.: 1 + x/U(0) where U(k) = 1  x*(k+2)  x^2*(k+1)/U(k+1); (continued fraction, 1step).
G.f.: 1 + 1/(U(0)  x) where U(k) = 1 + x  x*(k+1)/(1  x/U(k+1)); (continued fraction, 2step).
G.f.: 1 + x/(U(0)x) where U(k) = 1  x*(k+1)/(1  x/U(k+1)); (continued fraction, 2step).
G.f.: 1/G(0) where G(k) = 1  x/(1  x*(2*k+1)/(1  x/(1  x*(2*k+2)/G(k+1) ))); (continued fraction).
G.f.: G(0)/(1+x) where G(k) = 1  2*x*(k+1)/((2*k+1)*(2*x*k1)  x*(2*k+1)*(2*k+3)*(2*x*k1)/(x*(2*k+3)  2*(k+1)*(2*x*k+x1)/G(k+1) )); (continued fraction).
G.f.: (1+2*x) * Sum(k >= 0, x^(2*k)*(4*x*k^22*k2*x1) / ((2*k+1) * (2*x*k1)) * A(k) / B(k) where A(k) = prod(p=0...k, (2*p+1)), B(k) = prod(p=0..k, (2*p1) * (2*x*px1) * (2*x*p2*x1)).
G.f.: (G(0)  1)/(x1) where G(k) = 1  1/(1k*x)/(1x/(x1/G(k+1) )); (continued fraction).
G.f.: 1 + x*(S1) where S=sum(k>=0, ( 1 + (1x)/(1xx*k) )*(x/(1x))^k/prod(i=0..k1, (1xx*i)/(1x) ) ).
G.f.: (G(0)  2)/(2*x1) where G(k) = 2  1/(1k*x)/(1x/(x1/G(k+1) )); (continued fraction).
G.f.: G(0) where G(k) = 1  (x*k  2)/(x*k  1  x*(x*k  1)/(x + (x*k  2)/G(k+1) )); (continued fraction).
G.f.: G(0) where G(k) = 2  (2*x*k  1)/(x*k  1  x*(x*k  1)/(x + (2*x*k  1)/G(k+1) )); (continued fraction).
G.f.: (G(0)  1)/(1+x) where G(k) = 1 + 1/(1k*x)/(1x/(x+1/G(k+1) )); (continued fraction).
G.f.: 1/(x*(1x)*G(0))  1/x where G(k) = 1  x/(x  1/(1 + 1/(x*k1)/G(k+1) )); (continued fraction).
G.f.: 1 + x/( Q(0)  x ) where Q(k) = 1 + x/( x*k  1 )/Q(k+1); (continued fraction).
G.f.: 1+x/Q(0), where Q(k)= 1  x  x/(1  x*(k+1)/Q(k+1)); (continued fraction).
G.f.: 1/(1x*Q(0)), where Q(k)= 1 + x/(1  x + x*(k+1)/(x  1/Q(k+1))); (continued fraction).
G.f.: Q(0)/(1x), where Q(k) = 1  x^2*(k+1)/( x^2*(k+1)  (1x*(k+1))*(1x*(k+2))/Q(k+1) ); (continued fraction).
(End)
a(n) ~ exp(exp(W(n))n1)*n^n/W(n)^(n+1/2), where W(x) is the Lambert Wfunction.  Vladimir Reshetnikov, Nov 01 2015
a(n) ~ n^n * exp(n/LambertW(n)1n) / (sqrt(1+LambertW(n)) * LambertW(n)^n).  Vaclav Kotesovec, Nov 13 2015
a(n) are the coefficients in the asymptotic expansion of exp(1)*(1)^x*x*Gamma(x,0,1), where Gamma(a,z0,z1) is the generalized incomplete Gamma function.  Vladimir Reshetnikov, Nov 12 2015
a(n) = 1 + floor(exp(1) * Sum_{k=1..2*n} k^n/k!).  Vladimir Reshetnikov, Nov 13 2015


EXAMPLE

From Neven Juric, Oct 19 2009: (Start)
The a(4)=15 rhyme schemes for n=4 are
aaaa, aaab, aaba, aabb, aabc, abaa, abab, abac, abba, abbb, abbc, abca, abcb, abcc, abcd
The a(5)=52 rhyme schemes for n=5 are
aaaaa, aaaab, aaaba, aaabb, aaabc, aabaa, aabab, aabac, aabba, aabbb, aabbc, aabca, aabcb, aabcc, aabcd, abaaa, abaab, abaac, ababa, ababb, ababc, abaca, abacb, abacc, abacd, abbaa, abbab, abbac, abbba, abbbb, abbbc, abbca, abbcb, abbcc, abbcd, abcaa, abcab, abcac, abcad, abcba, abcbb, abcbc, abcbd, abcca, abccb, abccc, abccd, abcda, abcdb, abcdc, abcdd, abcde
(End)
From Joerg Arndt, Apr 30 2011: (Start)
Restricted growth strings (RGS):
For n=0 there is one empty string;
for n=1 there is one string [0];
for n=2 there are 2 strings [00], [01];
for n=3 there are a(3)=5 strings [000], [001], [010], [011], and [012];
for n=4 there are a(4)=15 strings
1: [0000], 2: [0001], 3: [0010], 4: [0011], 5: [0012], 6: [0100], 7: [0101], 8: [0102], 9: [0110], 10: [0111], 11: [0112], 12: [0120], 13: [0121], 14: [0122], 15: [0123].
These are onetoone with the rhyme schemes (identify a=0, b=1, c=2, etc.).
(End)


MAPLE

A000110 := proc(n) option remember; if n <= 1 then 1 else add( binomial(n1, i)*A000110(n1i), i=0..n1); fi; end; # version 1
A := series(exp(exp(x)1), x, 60); A000110 := n>n!*coeff(A, x, n); # version 2
with(combinat); A000110:=n>sum(stirling2(n, k), k=0..n): seq(A000110(n), n=1..22); # version 3, from Zerinvary Lajos, Jun 28 2007
A000110 := n > combinat[bell](n): # version 4, from Peter Luschny, Mar 30 2011
a:=array(0..200); a[0]:=1; a[1]:=1; lprint(0, 1); lprint(1, 1); M:=200; for n from 2 to M do a[n]:=add(binomial(n1, i)*a[n1i], i=0..n1); lprint(n, a[n]); od:
with(combstruct); spec := [S, {S=Set(U, card >= 1), U=Set(Z, card >= 1)}, labeled]; [seq(combstruct[count](spec, size=n), n=0..40)]; G:={P=Set(Set(Atom, card>0))}: combstruct[gfsolve](G, unlabeled, x): seq(combstruct[count]([P, G, labeled], size=i), i=0..22); # Zerinvary Lajos, Dec 16 2007
A000110 := proc(n::integer) local k, Resultat; if n = 0 then Resultat:=1: return Resultat; end if; Resultat:=0: for k from 1 to n do Resultat:=Resultat+A000110(nk)/((nk)!*(k1)!): od; Resultat:=Resultat*(n1)!; return Resultat; end proc; # Thomas Wieder, Sep 09 2008


MATHEMATICA

f[n_] := Sum[ StirlingS2[n, k], {k, 1, n}]; Table[ f[n], {n, 0, 21}] (* Robert G. Wilson v *)
Table[BellB[n], {n, 0, 26}] (* Harvey P. Dale, Mar 01 2011 *)
For n>=1, B[n_] := 1/E Sum[k^(n  1)/(k1)!, {k, 1, Infinity}] (* Dimitri Papadopoulos, Mar 10 2015 *)


PROG

(PARI) {a(n) = local(m); if( n<0, 0, m = contfracpnqn( matrix(2, n\2, i, k, if( i==1, k*x^2, 1  (k+1)*x))); polcoeff(1 / (1  x + m[2, 1] / m[1, 1]) + x * O(x^n), n))}; /* Michael Somos */
(PARI) {a(n) = polcoeff( sum( k=0, n, prod( i=1, k, x / (1  i*x)), x^n * O(x)), n)}; /* Michael Somos, Aug 22 2004 */
(PARI) a(n)=round(exp(1)*suminf(k=0, 1.0*k^n/k!)) \\ Gottfried Helms, Mar 30 2007
(Sage) from sage.combinat.expnums import expnums2; expnums2(30, 1) # Zerinvary Lajos, Jun 26 2008
(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp( exp( x + x * O(x^n))  1), n))}; /* Michael Somos, Jun 28 2009 */
(PARI) a(n) = polcoeff( exp(exp(x)), n1) / polcoeff( exp(x+1), n1) \\ Gottfried Helms, Jul 25 2009
(Python) # The objective of this implementation is efficiency.
# m > [a(0), a(1), ..., a(m)] for m > 0.
def A000110_list(m):
....A = [0 for i in range(0, m)]
....A[0] = 1
....R = [1, 1]
....for n in range(1, m):
........A[n] = A[0]
........for k in range(n, 0, 1):
............A[k1] += A[k]
........R.append(A[0])
....return R
A000110_list(100) # example call  Peter Luschny, Jan 18 2011
(MAGMA) [Bell(n): n in [0..80]]; // Vincenzo Librandi, Feb 07 2011
(Maxima) makelist(belln(n), n, 0, 80); /* Emanuele Munarini, Jul 04 2011 */
(PARI) Vec(serlaplace(exp(exp('x+O('x^66))1))) /* Joerg Arndt, May 26 2012 */
(Haskell)
type N = Integer
n_partitioned_k :: N > N > N
1 `n_partitioned_k` 1 = 1
1 `n_partitioned_k` _ = 0
n `n_partitioned_k` k = k * (pred n `n_partitioned_k` k) + (pred n `n_partitioned_k` pred k)
n_partitioned :: N > N
n_partitioned 0 = 1
n_partitioned n = sum $ map (\k > n `n_partitioned_k` k) $ [1 .. n]
 Felix Denis, Oct 16 2012
(Haskell)
a000110 = sum . a048993_row  Reinhard Zumkeller, Jun 30 2013
(Python)
# requires python 3.2 or higher. Otherwise use def'n of accumulate in python docs.
from itertools import accumulate
A000110, blist, b = [1, 1], [1], 1
for _ in range(20):
....blist = list(accumulate([b]+blist))
....b = blist[1]
....A000110.append(b) # Chai Wah Wu, Sep 02 2014, updated Chai Wah Wu, Sep 19 2014


CROSSREFS

Partial sums give A005001. See A061462 for powers of 2 dividing a(n).
Rightmost diagonal of triangle A121207. A144293 gives largest prime factor. a(n) = A123158(n, 0).
Cf. A000045, A000108, A000166, A000204, A000255, A000311, A000296, A003422, A008277, A024716, A029761, A049020, A058692, A060719, A084423, A087650, A094262, A103293, A165194, A165196, A173110, A227840.
Equals row sums of triangle A152432.
Row sums, right and left borders of A212431.
A diagonal of A011971.  N. J. A. Sloane, Jul 31 2012
Cf. A054767 (period of this sequence mod n).
Cf. A048993 (row sums).  Wolfdieter Lang, Oct 16 2014
Sequences in the Erné (1974) paper: A000110, A000798, A001035, A001927, A001929, A006056, A006057, A006058, A006059.
Bell polynomials B(n,x): A001861 (x=2), A027710 (x=3), A078944 (x=4), A144180 (x=5), A144223 (x=6), A144263 (x=7), A221159 (x=8).
Cf. A243991 (sum of reciprocals).
Sequence in context: A203644 A203645 A203646 * A186001 A134381 A107589
Adjacent sequences: A000107 A000108 A000109 * A000111 A000112 A000113


KEYWORD

core,nonn,easy,nice


AUTHOR

N. J. A. Sloane


STATUS

approved



