A006505 Number of partitions of an n-set into boxes of size >2. (Formerly M4789)

1, 0, 0, 1, 1, 1, 11, 36, 92, 491, 2557, 11353, 60105, 362506, 2169246, 13580815, 91927435, 650078097, 4762023647, 36508923530, 292117087090, 2424048335917, 20847410586719, 185754044235873, 1711253808769653, 16272637428430152

Offset

0,7

References

J. Riordan, A budget of rhyme scheme counts, pp. 455 - 465 of Second International Conference on Combinatorial Mathematics, New York, April 4-7, 1978. Edited by Allan Gewirtz and Louis V. Quintas. Annals New York Academy of Sciences, 319, 1979.

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

Links

Seiichi Manyama, Table of n, a(n) for n = 0..579 (terms 0..250 from Alois P. Heinz)

E. A. Enneking and J. C. Ahuja, Generalized Bell numbers, Fib. Quart., 14 (1976), 67-73.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 102

Vladimir Victorovich Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.

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

J. Riordan, Cached copy of paper [With permission]

Formula

E.g.f.: exp ( exp x - 1 - x - (1/2)*x^2 ).

a(n) = Sum_{k=1..[n/3]} A059022(n,k), n>=3. - R. J. Mathar, Nov 08 2008

a(n) = n! * sum(m=1..n, sum(k=0..m, k!*(-1)^(m-k) *binomial(m,k) *sum(i=0..n-m, stirling2(i+k,k) *binomial(m-k,n-m-i) *2^(-n+m+i)/ (i+k)!))/m!); a(0)=1. - Vladimir Kruchinin, Feb 01 2011

Define polynomials g_n by g_0=1, g_1=g_2=0, g_3=g_4=g_5=x; g(n) = x*Sum_{i=0..n-3} binomial(n-1,i)*g_i; then a(n) = g_n(1). [Riordan]

a(0) = 1; a(n) = Sum_{k=0..n-3} binomial(n-1,k+2) * a(n-k-3). - Seiichi Manyama, Sep 22 2023

Maple

Copy ZL := [ B, {B=Set(Set(Z, card>=3))}, labeled ]: [seq(combstruct[count](ZL, size=n), n=0..25)]; # Zerinvary Lajos, Mar 13 2007
G:={P=Set(Set(Atom, card>=3))}:combstruct[gfsolve](G, unlabeled, x):seq(combstruct[count]([P, G, labeled], size=i), i=0..25); # Zerinvary Lajos, Dec 16 2007
g:=proc(n) option remember; if n=0 then RETURN(1); fi; if n<=2 then RETURN(0); fi; if n<=5 then RETURN(x); fi; expand(x*add(binomial(n-1, i)*g(i), i=0..n-3)); end; [seq(subs(x=1, g(n)), n=0..60)]; # N. J. A. Sloane, Jul 20 2011

Mathematica

a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[ Exp @ x - 1 - x - x^2 / 2], {x, 0, n}]] (* Michael Somos, Jul 20 2011 *)
a[0] = 1; a[n_] := n!*Sum[Sum[k!*(-1)^(m-k)*Binomial[m, k]*Sum[StirlingS2[i+k, k]* Binomial[m-k, n-m-i]*2^(-n+m+i)/(i+k)!, {i, 0, n-m}], {k, 0, m}]/m!, {m, 1, n}]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Apr 03 2015, after Vladimir Kruchinin *)
Table[Sum[(-1)^j * Binomial[n, j] * BellB[n-j] * 2^((j-1)/2) * HypergeometricU[(1 - j)/2, 3/2, 1/2], {j, 0, n}], {n, 0, 25}] (* Vaclav Kotesovec, Feb 09 2020 *)

Prog

(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp( exp( x + x * O(x^n)) - 1 - x - x^2 / 2), n))} /* Michael Somos, Jul 20 2011 */

Crossrefs

Column k=2 of A293024.

Cf. A000110, A000296, A057814, A057837, A059022.

Cf. A293038.

Sequence in context: A160483 A034309 A005000 * A004637 A191296 A052526

Adjacent sequences: A006502 A006503 A006504 * A006506 A006507 A006508

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

More terms from Christian G. Bower, Nov 09 2000

Edited by N. J. A. Sloane, Jul 20 2011

Status

approved