cp's OEIS Frontend

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

%I A168444 #34 Jun 02 2025 02:12:37
%S A168444 1,0,0,0,1,5,21,91,422,2103,11226,63879,385691,2461004,16535820,
%T A168444 116628147,861033654,6637143698,53297137552,444940442553,
%U A168444 3854539901147,34592812084693,321125878230123,3079144039478532,30457076370822777,310407099470429818,3255972198123974137,35114803641531204063
%N A168444 Number of partitions of the set {1,2,...,n} such that no block is a sequence of consecutive integers (including 1-element blocks).
%C A168444 Some similar results appear in Klazar (see links).
%D A168444 Richard Stanley, Enumerative Combinatorics, volume 1, second edition, Cambridge Univ Press, 2011, page 192, solution 111.
%H A168444 Alois P. Heinz, <a href="/A168444/b168444.txt">Table of n, a(n) for n = 0..500</a>
%H A168444 Martin Klazar, <a href="http://dx.doi.org/10.1016/S0097-3165(03)00014-1">Bell numbers, their relatives and algebraic differential equations</a>, J. Combin. Theory, A 102 (2003), 63-87.
%F A168444 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)
%F A168444 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
%e A168444 For n=5 the a(5) = 5 partitions are 13-245, 14-235, 24-135, 25-135, 35-124.
%p A168444 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);
%t A168444 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 *)
%o A168444 (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 */
%o A168444 (PARI)
%o A168444 N=66;  x = 'x+O('x^N);
%o A168444 B = serlaplace(exp(exp(x)-1));
%o A168444 gf = (1-x)*subst(B,'x, x*(1-x));
%o A168444 Vec(gf) \\ _Joerg Arndt_, Jun 01 2013
%o A168444 (Magma)
%o A168444 b:= func< n | n eq 0 select 1 else (&+[(-1)^(n+j)*Binomial(j,n-j)*Bell(j): j in [Ceiling(n/2)..n]]) >;
%o A168444 A168444:= func< n | n eq 0 select 1 else b(n)-b(n-1) >;
%o A168444 [A168444(n): n in [0..30]]; // _G. C. Greubel_, May 12 2024
%o A168444 (SageMath)
%o A168444 @CachedFunction
%o A168444 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))
%o A168444 def A168444(n): return 1 if (n==0) else b(n) - b(n-1)
%o A168444 [A168444(n) for n in range(31)] # _G. C. Greubel_, May 12 2024
%Y A168444 Column k=0 of A177254.
%K A168444 easy,nonn
%O A168444 0,6
%A A168444 _Richard Stanley_, Nov 25 2009
%E A168444 Added more terms, _Joerg Arndt_, Jun 01 2013