|
%I M2851 #266 Oct 18 2023 11:50:09
%S 1,3,10,37,151,674,3263,17007,94828,562595,3535027,23430840,163254885,
%T 1192059223,9097183602,72384727657,599211936355,5150665398898,
%U 45891416030315,423145657921379,4031845922290572,39645290116637023,401806863439720943,4192631462935194064
%N 2-Bell numbers: a(n) = number of partitions of [n+1] with a distinguished block.
%C Number of Boolean sublattices of the Boolean lattice of subsets of {1..n}.
%C 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
%C With offset 1, number of permutations beginning with 12 and avoiding 21-3.
%C Rows sums of Bell's triangle (A011971). - _Jorge Coveiro_, Dec 26 2004
%C 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
%C 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
%C 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
%C 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
%C 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
%C Prefaced with a "1" = row sums of triangle A152433. - _Gary W. Adamson_, Dec 04 2008
%C Equals row sums of triangle A159573. - _Gary W. Adamson_, Apr 16 2009
%C Number of embedded coalitions in an (n+1)-person game. - David Yeung (wkyeung(AT)hkbu.edu.hk), May 08 2008
%C If prefixed with 0, gives first differences of Bell numbers A000110 (cf. A106436). - _N. J. A. Sloane_, Aug 29 2013
%C 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
%D Olivier Gérard and Karol A. Penson, A budget of set partition statistics, in preparation. Unpublished as of 2017.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Chai Wah Wu, <a href="/A005493/b005493.txt">Table of n, a(n) for n = 0..574</a> (first 101 terms from T. D. Noe)
%H V. E. Adler, <a href="http://arxiv.org/abs/1510.02900">Set partitions and integrable hierarchies</a>, arXiv:1510.02900 [nlin.SI], 2015.
%H M. Brookes, J. East, C. Miller, J.D. Mitchell, and N. Ruskuc, <a href="https://arxiv.org/abs/2310.08229">Heights of one- and two-sided congruence lattices of semigroups</a>, arXiv:2310.08229 [math.GR], 2023.
%H Giulio Cerbai, <a href="https://arxiv.org/abs/2305.10820">Modified ascent sequences and Bell numbers</a>, arXiv:2305.10820 [math.CO], 2023. See p. 11.
%H Martin Cohn, Shimon Even, Karl Menger, Jr., and Philip K. Hooper, <a href="http://www.jstor.org/stable/2310780">On the Number of Partitionings of a Set of n Distinct Objects</a>, Amer. Math. Monthly 69 (1962), no. 8, 782--785. MR1531841.
%H Martin Cohn, Shimon Even, Karl Menger, Jr., and Philip K. Hooper, <a href="/A011965/a011965.pdf">On the Number of Partitionings of a Set of n Distinct Objects</a>, Amer. Math. Monthly 69 (1962), no. 8, 782--785. MR1531841. [Annotated scanned copy]
%H R. B. Corcino and C. B. Corcino, <a href="http://dx.doi.org/10.1155/2011/623456">On generalized Bell polynomials</a>, Discrete Dyn. Nat. Soc. Article ID: 623456 (2011).
%H C. B. Corcino and R. B. Corcino, <a href="http://dx.doi.org/10.1155/2013/274697">An asymptotic formula for r-Bell numbers with real arguments</a>, ISRN Discrete Math, 2013 (2013), Article ID 274697.
%H Gábor Czédli, <a href="https://arxiv.org/abs/2205.02294">Lattices with lots of congruence energy</a>, arXiv:2205.02294 [math.RA], 2022.
%H A. Dil and V. Kurt, <a href="http://pefmath.etf.rs/vol5num2/AADM-Vol5-No2-212-229.pdf">Polynomials related to harmonic numbers and evaluation of harmonic number series II</a>, Appl. Anal. Discrete Math. 5 (2011), 212-229.
%H Eldar Fischer, Johann A. Makowsky, and Vsevolod Rakita, <a href="https://arxiv.org/abs/2302.08265">MC-finiteness of restricted set partition functions</a>, arXiv:2302.08265 [math.CO], 2023.
%H A. L. L. Gao, S. Kitaev, and P. B. Zhang, <a href="https://arxiv.org/abs/1605.05490">On pattern avoiding indecomposable permutations</a>, arXiv:1605.05490 [math.CO], 2016.
%H S. Getu et al., <a href="http://dx.doi.org/10.1137/0405040">How to guess a generating function</a>, SIAM J. Discrete Math., 5 (1992), 497-499.
%H S. K. Ghosal and J. K. Mandal, <a href="http://dx.doi.org/10.1016/j.protcy.2013.12.341">Stirling Transform Based Color Image Authentication</a>, Procedia Technology, 2013 Volume 10, 2013, Pages 95-104.
%H Alain Hertz, Hadrien Mélot, Sébastien Bonte, Gauvain Devillez, and Pierre Hauweele, <a href="https://arxiv.org/abs/2105.01120">Upper bounds on the average number of colors in the non-equivalent colorings of a graph</a>, arXiv:2105.01120 [math.CO], 2021.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=152">Encyclopedia of Combinatorial Structures 152</a>
%H R. Jakimczuk, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Jakimczuk2/jakimczuk17.html">Successive Derivatives and Integer Sequences</a>, J. Int. Seq. 14 (2011) # 11.7.3.
%H S. Kitaev, <a href="http://www.mat.univie.ac.at/users/slc/public_html/wpapers/s48kitaev.html">Generalized pattern avoidance with additional restrictions</a>, Sem. Lothar. Combinat. B48e (2003).
%H S. Kitaev and T. Mansour, <a href="https://arxiv.org/abs/math/0205182">Simultaneous avoidance of generalized patterns</a>, arXiv:math/0205182 [math.CO], 2002.
%H J. W. Layman, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5.
%H Philippe Leroux, <a href="https://arxiv.org/abs/0709.3453">L-algebras, triplicial-algebras, within an equivalence of categories motivated by graphs</a> (formerly "An equivalence of categories motivated by weighted directed graphs"), arXiv:0709.3453 [math-ph], 2007-2008.
%H Toufik Mansour and Mark Shattuck, <a href="https://www.emis.de/journals/INTEGERS/papers/l67/l67.Abstract.html">A recurrence related to the Bell numbers</a>, INTEGERS 11 (2011), #A67.
%H I. Mezo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Mezo/mezo9.html">The r-Bell numbers</a>, J. Integer Seq. 14(1) (2011), Article 11.1.1.
%H I. Mezo, <a href="http://arxiv.org/abs/1308.1637">Periodicity of the last digits of some combinatorial sequences</a>, arXiv preprint arXiv:1308.1637 [math.CO], 2013.
%H A. M. Odlyzko, Asymptotic enumeration methods, pp. 1063-1229 of R. L. Graham et al., eds., Handbook of Combinatorics, 1995; see Example 12.16 (<a href="http://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.pdf">pdf</a>, <a href="http://www.dtc.umn.edu/~odlyzko/doc/asymptotic.enum.ps">ps</a>)
%H Jocelyn Quaintance and Harris Kwong, <a href="http://www.emis.de/journals/INTEGERS/papers/n29/n29.Abstract.html">A combinatorial interpretation of the Catalan and Bell number difference tables</a>, Integers, 13 (2013), #A29.
%H J. Riordan, <a href="/A001861/a001861_1.pdf">Letter, Oct 31 1977</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/StirlingTransform.html">Stirling Transform.</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BellTriangle.html">Bell Triangle</a>
%H E. G. Whitehead, Jr., <a href="http://dx.doi.org/10.1016/0097-3165(78)90061-4">Stirling number identities from chromatic polynomials</a>, J. Combin. Theory, A 24 (1978), 314-317.
%H David W. K. Yeung, <a href="http://www.worldscinet.com/cgi-bin/details.cgi?id=pii:S0219198908001819&type=html">Recursive sequence identifying the number of embedded coalitions</a>, International Game Theory Review 10 (1) (2008), 129-136.
%F a(n-1) = Sum_{k=1..n} k*Stirling2(n, k) for n>=1.
%F E.g.f.: exp(exp(x) + 2*x - 1). First differences of Bell numbers (if offset 1). - _Michael Somos_, Oct 09 2002
%F G.f.: Sum_{k>=0} (x^k/Product_{l=1..k} (1-(l+1)x)). - _Ralf Stephan_, Apr 18 2004
%F 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]
%F 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
%F Row sums of A011971 (Aitken's array, also called Bell triangle). - _Philippe Deléham_, Nov 15 2003
%F a(n) = exp(-1)*Sum_{k>=0} ((k+2)^n)/k!. - _Gerald McGarvey_, Jun 03 2004
%F Recurrence: a(n+1) = 1 + Sum_{j=1..n} (1+binomial(n, j))*a(j). - _Jon Perry_, Apr 25 2005
%F a(n) = A000296(n+3) - A000296(n+1). - _Philippe Deléham_, Jul 31 2005
%F a(n) = B(n+2) - B(n+1), where B(n) are Bell numbers (A000110). - _Franklin T. Adams-Watters_, Jul 13 2006
%F a(n) = A123158(n,2). - _Philippe Deléham_, Oct 06 2006
%F Binomial transform of Bell numbers 1, 2, 5, 15, 52, 203, 877, 4140, ... (see A000110).
%F 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
%F 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
%F 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
%F 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
%F From _Sergei N. Gladkovskii_, Oct 11 2012 to Jan 26 2014: (Start)
%F Continued fractions:
%F G.f.: 1/U(0) where U(k) = 1 - x*(k+3) - x^2*(k+1)/U(k+1).
%F G.f.: 1/(U(0)-x) where U(k) = 1 - x - x*(k+1)/(1 - x/U(k+1)).
%F 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) )).
%F G.f.: (G(0) - 1)/(x-1) where G(k) = 1 - 1/(1-2*x-k*x)/(1-x/(x-1/G(k+1) )).
%F G.f.: -G(0)/x where G(k) = 1 - 1/(1-k*x-x)/(1-x/(x-1/G(k+1) )).
%F 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) ) ).
%F G.f.: (1-x)/x/(G(0)-x) - 1/x where G(k) = 1 - x*(k+1)/(1 - x/G(k+1) ).
%F G.f.: (1/G(0) - 1)/x^3 where G(k) = 1 - x/(x - 1/(1 + 1/(x*k-1)/G(k+1) )).
%F G.f.: 1/Q(0), where Q(k)= 1 - 2*x - x/(1 - x*(k+1)/Q(k+1)).
%F 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)
%F 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
%F 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
%F a(n) ~ n^2 * Bell(n) / LambertW(n)^2 * (1 - LambertW(n)/n). - _Vaclav Kotesovec_, Jul 28 2021
%F a(n) = Sum_{k=0..n} 3^k*A124323(n, k). - _Mélika Tebni_, Jun 02 2022
%e For example, a(1) counts (12), (1)-2, 1-(2) where dashes separate blocks and the distinguished block is parenthesized.
%p with(combinat): seq(bell(n+2)-bell(n+1),n=0..22); # _Emeric Deutsch_, Nov 13 2006
%p seq(add(binomial(n, k)*(bell(n-k)), k=1..n), n=1..23); # _Zerinvary Lajos_, Dec 01 2006
%p A005493 := proc(n) local a,b,i;
%p a := [seq(3,i=1..n)]; b := [seq(2,i=1..n)];
%p 2^n*exp(-x)*hypergeom(a,b,x); round(evalf(subs(x=1,%),66)) end:
%p seq(A005493(n),n=0..22); # _Peter Luschny_, Mar 30 2011
%p BT := proc(n,k) option remember; if n = 0 and k = 0 then 1
%p elif k = n then BT(n-1,0) else BT(n,k+1)+BT(n-1,k) fi end:
%p A005493 := n -> add(BT(n,k),k=0..n):
%p seq(A005493(i),i=0..22); # _Peter Luschny_, Aug 04 2011
%p # For Maple code for r-Bell numbers, etc., see A232472. - _N. J. A. Sloane_, Nov 27 2013
%t a=Exp[x]-1; Rest[CoefficientList[Series[a Exp[a],{x,0,20}],x] * Table[n!,{n,0,20}]]
%t a[ n_] := If[ n<0, 0, With[ {m = n+1}, m! SeriesCoefficient[ # Exp@# &[ Exp@x - 1], {x, 0, m}]]]; (* _Michael Somos_, Nov 16 2011 *)
%t Differences[BellB[Range[30]]] (* _Harvey P. Dale_, Oct 16 2014 *)
%o (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 */
%o (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 */
%o (Python)
%o # requires python 3.2 or higher. Otherwise use def'n of accumulate in python docs.
%o from itertools import accumulate
%o A005493_list, blist, b = [], [1], 1
%o for _ in range(1001):
%o blist = list(accumulate([b]+blist))
%o b = blist[-1]
%o A005493_list.append(blist[-2])
%o # _Chai Wah Wu_, Sep 02 2014, updated _Chai Wah Wu_, Sep 20 2014
%Y Cf. A000110, A005494, A008277, A011971, A011968, A049020, A106436, A124323, A137650, A152433, A159573.
%Y A row or column of the array A108087.
%Y Row sums of triangle A143494. - _Wolfdieter Lang_, Sep 29 2011. And also of triangle A362924. - _N. J. A. Sloane_, Aug 10 2023
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_, _Simon Plouffe_
%E Definition revised by _David Callan_, Oct 11 2005
|
