A168444 Number of partitions of the set {1,2,...,n} such that no block is a sequence of consecutive integers (including 1-element blocks)

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

Alois P. Heinz, Table of n, a(n) for n = 0..500

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 A154964

Adjacent sequences: A168441 A168442 A168443 * A168445 A168446 A168447

Keyword

easy,nonn

Author

Richard Stanley, Nov 25 2009

Extensions

Added more terms, Joerg Arndt, Jun 01 2013

Status

approved