|
| |
|
|
A005493
|
|
a(n) = number of partitions of [n+1] with a distinguished block. For example, a(1) counts (12), (1)-2, 1-(2) where dashes separate blocks and the distinguished block is parenthesized.
(Formerly M2851)
|
|
47
| |
|
|
1, 3, 10, 37, 151, 674, 3263, 17007, 94828, 562595, 3535027, 23430840, 163254885, 1192059223, 9097183602, 72384727657, 599211936355, 5150665398898, 45891416030315, 423145657921379, 4031845922290572, 39645290116637023, 401806863439720943
(list; graph; refs; listen; history; internal format)
|
|
|
|
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 (jorgecoveiro(AT)yahoo.com), 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 (deutsch(AT)duke.poly.edu), 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 GERARD (olivier.gerard(AT)gmail.com), Oct 29 2007
Comment from Philippe Leroux, Nov 17 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.
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 (qntmpkt(AT)yahoo.com), Jan 31 2008
Prefaced with a "1" = row sums of triangle A152433. [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 04 2008]
Equals row sums of triangle A159573 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 16 2009]
Number of embedded coalitions in an (n+1)-person game. - David Yeung (wkyeung(AT)hkbu.edu.hk), May 08 2008
|
|
|
REFERENCES
| Olivier Gerard and Karol A. Penson, A budget of set partition statistics, in preparation.
Toufik Mansour and Mark Shattuck, A RECURRENCE RELATED TO THE BELL NUMBERS, INTEGERS 11 (2011), #A67; http://www.emis.de/journals/INTEGERS/papers/l67/l67.pdf.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..100
S. Getu et al., How to guess a generating function, SIAM J. Discrete Math., 5 (1992), 497-499.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 152
S. Kitaev, Generalized pattern avoidance with additional restrictions, Sem. Lothar. Combinat. B48e (2003).
S. Kitaev and T. Mansour, Simultaneous avoidance of generalized patterns.
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
Philippe Leroux, An equivalence of categories motivated by weighted directed graphs
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)
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
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/prod[l=1..k, 1-(l+1)x]}. - R. 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 (njas(AT)research.att.com), Feb 07 2009.
Representation as an infinite series: a(n-1)=sum(k^n*(k-1)/k!, k=2..infinity)/exp(1), n=1, 2... This is a Dobinski-type summation formula. - Karol A. Penson (penson(AT)lptl.jussieu.fr), Mar 14, 2002.
Row sums of A011971 (Aitken's array, also called Bell triangle) - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), Nov 15 2003
a(n) = EXP(-1)*sum(k=>0, (k+2)^(n)/k!) - Gerald McGarvey (Gerald.McGarvey(AT)comcast.net), Jun 03 2004
Recurrence : a(n+1) = 1 + sum { j=1, n, (1+binomial(n, j))*a(j) } - Jon Perry (perry(AT)globalnet.co.uk), Apr 25 2005
a(n) = A000296(n+3) - A000296(n+1) . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), Jul 31 2005
a(n) = B(n+2) - B(n+1), where B(n) are Bell numbers (A000110). - Frank Adams-Watters (FrankTAW(AT)Netscape.net), Jul 13 2006
a(n) = A123158(n,2) . - Philippe DELEHAM (kolotoko(AT)wanadoo.fr), 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)=diff(x*f_n(x),x), for n=2,3,.... Then a(n-1)=e^{-1}*f_n(1). - Milan R. Janjic (agnus(AT)blic.net), 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 (penson(AT)lptl.jussieu.fr), 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). [From Milan R. Janjic (agnus(AT)blic.net), 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
|
|
|
MAPLE
| with(combinat): seq(bell(n+2)-bell(n+1), n=0..22); - Emeric Deutsch (deutsch(AT)duke.poly.edu), Nov 13 2006
seq(add(binomial(n, k)*(bell(n-k)), k=1..n), n=1..23); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), 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
|
|
|
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 *)
|
|
|
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 */
|
|
|
CROSSREFS
| Cf. A000110, A005494, A049020, A011968, A011971.
Cf. A008277, A137650.
A152433 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 04 2008]
A159573 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 16 2009]
Cf. Row sums of triangle A143494. [Wolfdieter Lang, Sep 29 2011]
Sequence in context: A086444 A064613 A138378 * A123636 A092816 A078109
Adjacent sequences: A005490 A005491 A005492 * A005494 A005495 A005496
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Simon Plouffe (simon.plouffe(AT)gmail.com)
|
|
|
EXTENSIONS
| Definition revised by David Callan (callan(AT)stat.wisc.edu), Oct 11 2005
|
| |
|
|
