A005493 2-Bell numbers: a(n) = number of partitions of [n+1] with a distinguished block. (Formerly M2851)

1, 3, 10, 37, 151, 674, 3263, 17007, 94828, 562595, 3535027, 23430840, 163254885, 1192059223, 9097183602, 72384727657, 599211936355, 5150665398898, 45891416030315, 423145657921379, 4031845922290572, 39645290116637023, 401806863439720943, 4192631462935194064

Offset

0,2

Comments

Number of Boolean sublattices of the Boolean lattice of subsets of {1..n}.

a(n) = p(n+1) where p(x) is the unique degree n polynomial such that p(k) = A000110(k+1) for k = 0, 1, ..., n. - Michael Somos, Oct 07 2003

With offset 1, number of permutations beginning with 12 and avoiding 21-3.

Rows sums of Bell's triangle (A011971). - Jorge Coveiro, Dec 26 2004

Number of blocks in all set partitions of an (n+1)-set. Example: a(2)=10 because the set partitions of {1,2,3} are 1|2|3, 1|23, 12|3, 13|2 and 123, with a total of 10 blocks. - Emeric Deutsch, Nov 13 2006

Number of partitions of n+3 with at least one singleton and with the smallest element in a singleton equal to 2. - Olivier Gérard, Oct 29 2007

See page 29, Theorem 5.6 of my paper on the arXiv: These numbers are the dimensions of the homogeneous components of the operad called ComTrip associated with commutative triplicial algebras. (Triplicial algebras are related to even trees and also to L-algebras, see A006013.) - Philippe Leroux, Nov 17 2007

Number of set partitions of (n+2) elements where two specific elements are clustered separately. Example: a(1)=3 because 1/2/3, 1/23, 13/2 are the 3 set partitions with 1, 2 clustered separately. - Andrey Goder (andy.goder(AT)gmail.com), Dec 17 2007

Equals A008277 * [1,2,3,...], i.e., the product of the Stirling number of the second kind triangle and the natural number vector. a(n+1) = row sums of triangle A137650. - Gary W. Adamson, Jan 31 2008

Prefaced with a "1" = row sums of triangle A152433. - Gary W. Adamson, Dec 04 2008

Equals row sums of triangle A159573. - Gary W. Adamson, Apr 16 2009

Number of embedded coalitions in an (n+1)-person game. - David Yeung (wkyeung(AT)hkbu.edu.hk), May 08 2008

If prefixed with 0, gives first differences of Bell numbers A000110 (cf. A106436). - N. J. A. Sloane, Aug 29 2013

Sum_{n>=0} a(n)/n! = e^(e+1) = 41.19355567... (see A235214). Contrast with e^(e-1) = Sum_{n>=0} A000110(n)/n!. - Richard R. Forberg, Jan 05 2014

References

Olivier Gérard and Karol A. Penson, A budget of set partition statistics, in preparation. Unpublished as of 2017.

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

Links

Chai Wah Wu, Table of n, a(n) for n = 0..574 (first 101 terms from T. D. Noe)

V. E. Adler, Set partitions and integrable hierarchies, arXiv:1510.02900 [nlin.SI], 2015.

M. Brookes, J. East, C. Miller, J.D. Mitchell, and N. Ruskuc, Heights of one- and two-sided congruence lattices of semigroups, arXiv:2310.08229 [math.GR], 2023.

Giulio Cerbai, Modified ascent sequences and Bell numbers, arXiv:2305.10820 [math.CO], 2023. See p. 11.

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, 782--785. 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, 782--785. MR1531841. [Annotated scanned copy]

R. B. Corcino and C. B. Corcino, On generalized Bell polynomials, Discrete Dyn. Nat. Soc. Article ID: 623456 (2011).

C. B. Corcino and R. B. Corcino, An asymptotic formula for r-Bell numbers with real arguments, ISRN Discrete Math, 2013 (2013), Article ID 274697.

Gábor Czédli, Lattices with lots of congruence energy, arXiv:2205.02294 [math.RA], 2022.

A. Dil and V. Kurt, Polynomials related to harmonic numbers and evaluation of harmonic number series II, Appl. Anal. Discrete Math. 5 (2011), 212-229.

Eldar Fischer, Johann A. Makowsky, and Vsevolod Rakita, MC-finiteness of restricted set partition functions, arXiv:2302.08265 [math.CO], 2023.

A. L. L. Gao, S. Kitaev, and P. B. Zhang, On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.

S. Getu et al., How to guess a generating function, SIAM J. Discrete Math., 5 (1992), 497-499.

S. K. Ghosal and J. K. Mandal, Stirling Transform Based Color Image Authentication, Procedia Technology, 2013 Volume 10, 2013, Pages 95-104.

Alain Hertz, Hadrien Mélot, Sébastien Bonte, Gauvain Devillez, and Pierre Hauweele, Upper bounds on the average number of colors in the non-equivalent colorings of a graph, arXiv:2105.01120 [math.CO], 2021.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 152

R. Jakimczuk, Successive Derivatives and Integer Sequences, J. Int. Seq. 14 (2011) # 11.7.3.

S. Kitaev, Generalized pattern avoidance with additional restrictions, Sem. Lothar. Combinat. B48e (2003).

S. Kitaev and T. Mansour, Simultaneous avoidance of generalized patterns, arXiv:math/0205182 [math.CO], 2002.

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.

Philippe Leroux, L-algebras, triplicial-algebras, within an equivalence of categories motivated by graphs (formerly "An equivalence of categories motivated by weighted directed graphs"), arXiv:0709.3453 [math-ph], 2007-2008.

Toufik Mansour and Mark Shattuck, A recurrence related to the Bell numbers, INTEGERS 11 (2011), #A67.

I. Mezo, The r-Bell numbers, J. Integer Seq. 14(1) (2011), Article 11.1.1.

I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637 [math.CO], 2013.

A. M. Odlyzko, Asymptotic enumeration methods, pp. 1063-1229 of R. L. Graham et al., eds., Handbook of Combinatorics, 1995; see Example 12.16 (pdf, ps)

Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.

J. Riordan, Letter, Oct 31 1977

Eric Weisstein's World of Mathematics, Stirling Transform.

Eric Weisstein's World of Mathematics, Bell Triangle

E. G. Whitehead, Jr., Stirling number identities from chromatic polynomials, J. Combin. Theory, A 24 (1978), 314-317.

David W. K. Yeung, Recursive sequence identifying the number of embedded coalitions, International Game Theory Review 10 (1) (2008), 129-136.

Formula

a(n-1) = Sum_{k=1..n} k*Stirling2(n, k) for n>=1.

E.g.f.: exp(exp(x) + 2*x - 1). First differences of Bell numbers (if offset 1). - Michael Somos, Oct 09 2002

G.f.: Sum_{k>=0} (x^k/Product_{l=1..k} (1-(l+1)x)). - Ralf Stephan, Apr 18 2004

a(n) = Sum_{i=0..n} 2^(n-i)*B(i)*binomial(n,i) where B(n) = Bell numbers A000110(n). - Fred Lunnon, Aug 04 2007 [Written umbrally, a(n) = (B+2)^n. - N. J. A. Sloane, Feb 07 2009]

Representation as an infinite series: a(n-1) = Sum_{k>=2} (k^n*(k-1)/k!)/exp(1), n=1, 2, ... This is a Dobinski-type summation formula. - Karol A. Penson, Mar 14 2002

Row sums of A011971 (Aitken's array, also called Bell triangle). - Philippe Deléham, Nov 15 2003

a(n) = exp(-1)*Sum_{k>=0} ((k+2)^n)/k!. - Gerald McGarvey, Jun 03 2004

Recurrence: a(n+1) = 1 + Sum_{j=1..n} (1+binomial(n, j))*a(j). - Jon Perry, Apr 25 2005

a(n) = A000296(n+3) - A000296(n+1). - Philippe Deléham, Jul 31 2005

a(n) = B(n+2) - B(n+1), where B(n) are Bell numbers (A000110). - Franklin T. Adams-Watters, Jul 13 2006

a(n) = A123158(n,2). - Philippe Deléham, Oct 06 2006

Binomial transform of Bell numbers 1, 2, 5, 15, 52, 203, 877, 4140, ... (see A000110).

Define f_1(x), f_2(x), ... such that f_1(x)=x*e^x, f_{n+1}(x) = (d/dx)(x*f_n(x)), for n=2,3,.... Then a(n-1) = e^(-1)*f_n(1). - Milan Janjic, May 30 2008

Representation of numbers a(n), n=0,1..., as special values of hypergeometric function of type (n)F(n), in Maple notation: a(n)=exp(-1)*2^n*hypergeom([3,3...3],[2.2...2],1), n=0,1..., i.e., having n parameters all equal to 3 in the numerator, having n parameters all equal to 2 in the denominator and the value of the argument equal to 1. Examples: a(0)= 2^0*evalf(hypergeom([],[],1)/exp(1))=1 a(1)= 2^1*evalf(hypergeom([3],[2],1)/exp(1))=3 a(2)= 2^2*evalf(hypergeom([3,3],[2,2],1)/exp(1))=10 a(3)= 2^3*evalf(hypergeom([3,3,3],[2,2,2],1)/exp(1))=37 a(4)= 2^4*evalf(hypergeom([3,3,3,3],[2,2,2,2],1)/exp(1))=151 a(5)= 2^5*evalf(hypergeom([3,3,3,3,3],[2,2,2,2,2],1)/exp(1)) = 674. - Karol A. Penson, Sep 28 2007

Let A be the upper Hessenberg matrix of order n defined by: A[i,i-1]=-1, A[i,j]=binomial(j-1,i-1), (i <= j), and A[i,j]=0 otherwise. Then, for n >= 1, a(n) = (-1)^(n)charpoly(A,-2). - Milan Janjic, Jul 08 2010

a(n) = D^(n+1)(x*exp(x)) evaluated at x = 0, where D is the operator (1+x)*d/dx. Cf. A003128, A052852 and A009737. - Peter Bala, Nov 25 2011

From Sergei N. Gladkovskii, Oct 11 2012 to Jan 26 2014: (Start)

Continued fractions:

G.f.: 1/U(0) where U(k) = 1 - x*(k+3) - x^2*(k+1)/U(k+1).

G.f.: 1/(U(0)-x) where U(k) = 1 - x - x*(k+1)/(1 - x/U(k+1)).

G.f.: G(0)/(1-x) where G(k) = 1 - 2*x*(k+1)/((2*k+1)*(2*x*k+2*x-1) - x*(2*k+1)*(2*k+3)*(2*x*k+2*x-1)/(x*(2*k+3) - 2*(k+1)*(2*x*k+3*x-1)/G(k+1) )).

G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-2*x-k*x)/(1-x/(x-1/G(k+1) )).

G.f.: -G(0)/x where G(k) = 1 - 1/(1-k*x-x)/(1-x/(x-1/G(k+1) )).

G.f.: 1 - 2/x + (1/x-1)*S where S = sum(k>=0, ( 1 + (1-x)/(1-x-x*k) )*(x/(1-x))^k / prod(i=0..k-1, (1-x-x*i)/(1-x) ) ).

G.f.: (1-x)/x/(G(0)-x) - 1/x where G(k) = 1 - x*(k+1)/(1 - x/G(k+1) ).

G.f.: (1/G(0) - 1)/x^3 where G(k) = 1 - x/(x - 1/(1 + 1/(x*k-1)/G(k+1) )).

G.f.: 1/Q(0), where Q(k)= 1 - 2*x - x/(1 - x*(k+1)/Q(k+1)).

G.f.: G(0)/(1-3*x), where G(k) = 1 - x^2*(k+1)/( x^2*(k+1) - (1 - x*(k+3))*(1 - x*(k+4))/G(k+1) ). (End)

a(n) ~ exp(n/LambertW(n) + 3*LambertW(n)/2 - n - 1) * n^(n + 1/2) / LambertW(n)^(n+1). - Vaclav Kotesovec, Jun 09 2020

a(0) = 1; a(n) = 2 * a(n-1) + Sum_{k=0..n-1} binomial(n-1,k) * a(k). - Ilya Gutkovskiy, Jul 02 2020

a(n) ~ n^2 * Bell(n) / LambertW(n)^2 * (1 - LambertW(n)/n). - Vaclav Kotesovec, Jul 28 2021

a(n) = Sum_{k=0..n} 3^k*A124323(n, k). - Mélika Tebni, Jun 02 2022

Example

For example, a(1) counts (12), (1)-2, 1-(2) where dashes separate blocks and the distinguished block is parenthesized.

Maple

with(combinat): seq(bell(n+2)-bell(n+1), n=0..22); # Emeric Deutsch, Nov 13 2006
seq(add(binomial(n, k)*(bell(n-k)), k=1..n), n=1..23); # Zerinvary Lajos, Dec 01 2006
A005493  := proc(n) local a, b, i;
a := [seq(3, i=1..n)]; b := [seq(2, i=1..n)];
2^n*exp(-x)*hypergeom(a, b, x); round(evalf(subs(x=1, %), 66)) end:
seq(A005493(n), n=0..22); # Peter Luschny, Mar 30 2011
BT := proc(n, k) option remember; if n = 0 and k = 0 then 1
elif k = n then BT(n-1, 0) else BT(n, k+1)+BT(n-1, k) fi end:
A005493 := n -> add(BT(n, k), k=0..n):
seq(A005493(i), i=0..22); # Peter Luschny, Aug 04 2011
# For Maple code for r-Bell numbers, etc., see A232472. - N. J. A. Sloane, Nov 27 2013

Mathematica

a=Exp[x]-1; Rest[CoefficientList[Series[a Exp[a], {x, 0, 20}], x] * Table[n!, {n, 0, 20}]]
a[ n_] := If[ n<0, 0, With[ {m = n+1}, m! SeriesCoefficient[ # Exp@# &[ Exp@x - 1], {x, 0, m}]]]; (* Michael Somos, Nov 16 2011 *)
Differences[BellB[Range[30]]] (* Harvey P. Dale, Oct 16 2014 *)

Prog

(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp( exp( x + x * O(x^n)) + 2*x - 1), n))}; /* Michael Somos, Oct 09 2002 */
(PARI) {a(n) = if( n<0, 0, n+=2; subst( polinterpolate( Vec( serlaplace( exp( exp( x + O(x^n)) - 1) - 1))), x, n))}; /* Michael Somos, Oct 07 2003 */
(Python)
# requires python 3.2 or higher. Otherwise use def'n of accumulate in python docs.
from itertools import accumulate
A005493_list, blist, b = [], [1], 1
for _ in range(1001):
    blist = list(accumulate([b]+blist))
    b = blist[-1]
    A005493_list.append(blist[-2])
# Chai Wah Wu, Sep 02 2014, updated Chai Wah Wu, Sep 20 2014

Crossrefs

Cf. A000110, A005494, A008277, A011971, A011968, A049020, A106436, A124323, A137650, A152433, A159573.

A row or column of the array A108087.

Row sums of triangle A143494. - Wolfdieter Lang, Sep 29 2011. And also of triangle A362924. - N. J. A. Sloane, Aug 10 2023

Sequence in context: A086444 A064613 A270789 * A138378 A250307 A363294

Adjacent sequences: A005490 A005491 A005492 * A005494 A005495 A005496

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, Simon Plouffe

Extensions

Definition revised by David Callan, Oct 11 2005

Status

approved