login
A168444
Number of partitions of the set {1,2,...,n} such that no block is a sequence of consecutive integers (including 1-element blocks)
2
1, 0, 0, 0, 1, 5, 21, 91, 422, 2103, 11226, 63879, 385691, 2461004, 16535820, 116628147, 861033654, 6637143698, 53297137552, 444940442553, 3854539901147, 34592812084693, 321125878230123, 3079144039478532, 30457076370822777, 310407099470429818, 3255972198123974137, 35114803641531204063
OFFSET
0,6
COMMENTS
Some similar results appear in Klazar (see links).
REFERENCES
Richard Stanley, Enumerative Combinatorics, volume 1, second edition, Cambridge Univ Press, 2011, page 192, solution 111.
LINKS
Martin Klazar, Bell numbers, their relatives and algebraic differential equations, J. Combin. Theory, A 102 (2003), 63-87.
FORMULA
Ordinary g.f.: (1-x)F(x(1-x)), where F(x) = sum_{n>=0} B(n)x^n (the ordinary g.f. for the Bell numbers)
a(n) = b(n)-b(n-1), b(n) = if n=0 then 1 else sum(binomial(k,n-k)*(-1)^(n-k)*B(k),k=ceiling(n/2)..n). - Vladimir Kruchinin, Sep 09 2010
EXAMPLE
For n=5 the a(5) = 5 partitions are 13-245, 14-235, 24-135, 25-135, 35-124.
MAPLE
with(combinat): y:=sum(bell(n)*x^n, n=0..20): z:=(1-x)*subs(x=x*(1-x), y): taylor(z, x=0, 21);
MATHEMATICA
nn = 20; b := Sum[BellB[n] (x - x^2)^n, {n, 0, nn}]; CoefficientList[ Series[ (1-x) b, {x, 0, nn}], x] (* Geoffrey Critzer, Jun 01 2013 *)
PROG
(Maxima) b(n):=if n=0 then 1 else sum(binomial(k, n-k)*(-1)^(n-k)*belln(k), k, ceiling(n/2), n); a(n):=if n=0 then 1 else b(n)-b(n-1); /* Vladimir Kruchinin, Sep 09 2010 */
(PARI)
N=66; x = 'x+O('x^N);
B = serlaplace(exp(exp(x)-1));
gf = (1-x)*subst(B, 'x, x*(1-x));
Vec(gf) \\ Joerg Arndt, Jun 01 2013
(Magma)
b:= func< n | n eq 0 select 1 else (&+[(-1)^(n+j)*Binomial(j, n-j)*Bell(j): j in [Ceiling(n/2)..n]]) >;
A168444:= func< n | n eq 0 select 1 else b(n)-b(n-1) >;
[A168444(n): n in [0..30]]; // G. C. Greubel, May 12 2024
(SageMath)
@CachedFunction
def b(n): return 1 if (n==0) else sum((-1)^(n+j)*binomial(j, n-j)*bell_number(j) for j in range((n//2), n+1))
def A168444(n): return 1 if (n==0) else b(n) - b(n-1)
[A168444(n) for n in range(31)] # G. C. Greubel, May 12 2024
CROSSREFS
Column k=0 of A177254.
Sequence in context: A333538 A164037 A218961 * A125784 A218964 A373958
KEYWORD
easy,nonn
AUTHOR
Richard Stanley, Nov 25 2009
EXTENSIONS
Added more terms, Joerg Arndt, Jun 01 2013
STATUS
approved