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

Author

Richard Stanley, Nov 25 2009

Keywords

• easy
• nonn

Comments

Some similar results appear in Klazar (see links).

Examples

			For n=5 the a(5) = 5 partitions are 13-245, 14-235, 24-135, 25-135, 35-124.
		

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.

Crossrefs

Column k=0 of A177254.

Programs

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

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 *)

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

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

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

Extensions

Added more terms, Joerg Arndt, Jun 01 2013