OFFSET
0,4
COMMENTS
a(n) is the number of set partitions of {1,2,...,n} such that the size of each block divides 3. - Geoffrey Critzer, Sep 23 2011
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..666
FORMULA
a(n) = n!*sum(k=0..n/3, 1/((k)!*(n-3*k)!*6^(k))), n>0, a(0)=1.
E.g.f.: E(0)/2, where E(k)= 1 + 1/(1 - x*(6+x^2)/(x*(6+x^2)+ 6*(k+1)/E(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 01 2013
Recurrence: 2*a(n) = 2*a(n-1) + (n-2)*(n-1)*a(n-3). - Vaclav Kotesovec, Jun 27 2013
a(n) ~ n^(2*n/3) * exp(-2*n/3+(2*n)^(1/3)) / (sqrt(3)*2^(n/3)) * (1 - 2^(2/3)/(6*n^(1/3)) + 13*2^(1/3)/(36*n^(2/3))). - Vaclav Kotesovec, Jun 27 2013
a(n) = hypergeom([-n/3, (1 - n)/3, (2 - n)/3], [], -9/2). - Peter Luschny, Jun 04 2021
EXAMPLE
a(0) = 1 because (vacuously) all sizes of the blocks in the unique set partition of {} divide 3.
a(4) = 5 because there are 5 such set partitions of {1,2,3,4}: ({1},{2,3,4}) ({2},{1,3,4}) ({3},{1,2,4}) ({4},{1,2,3}) ({1},{2},{3},{4}).
MAPLE
a:= proc(n) option remember; `if`(n=0, 1, add(
`if`(j>n, 0, a(n-j)*binomial(n-1, j-1)), j=[1, 3]))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Jul 27 2016
MATHEMATICA
Range[0, 25]! CoefficientList[Series[Exp[x + x^3/6] , {x, 0, 25}], x]
PROG
(Maxima)
a(n):=n!*sum(1/((k)!*(n-3*k)!*6^(k)), k, 0, n/3);
CROSSREFS
KEYWORD
nonn
AUTHOR
Vladimir Kruchinin, May 22 2011
STATUS
approved