cp's OEIS Frontend

A184175 Number of set partitions of {1,2,...,n} having no blocks of the form {i, i+1}.

%I A184175 #20 Jun 14 2025 11:21:56
%S A184175 1,1,1,3,10,35,139,611,2925,15128,83903,495929,3108129,20565721,
%T A184175 143134606,1044489265,7968879387,63407648443,525016067171,
%U A184175 4514661402304,40245681692885,371319303282381,3540506731807277,34840411462506887,353394158240095874,3690577066014598575
%N A184175 Number of set partitions of {1,2,...,n} having no blocks of the form {i, i+1}.
%C A184175 a(n) = A184174(n,0).
%H A184175 Alois P. Heinz, <a href="/A184175/b184175.txt">Table of n, a(n) for n = 0..550</a>
%F A184175 a(n) = Sum((-1)^j*binomial(n-j,j)*bell(n-2j), j=0..floor(n/2)).
%F A184175 G.f.: Sum_{n>=0} x^n / Product_{k=0..n} (1 - k*x + x^2). - _Paul D. Hanna_, Sep 03 2017
%e A184175 a(3)=3 because we have 1-2-3, 13-2, and 123. a(4)=10 because among the 15 (=bell(4)) partitions of {1,2,3,4} only 12-34, 14-23, 12-3-4, 1-23-4, and 1-2-34, have adjacent blocks of size 2.
%e A184175 Contribution from _Paul D. Hanna_, Sep 03 2017: (Start)
%e A184175 G.f.: A(x) = 1 + x + x^2 + 3*x^3 + 10*x^4 + 35*x^5 + 139*x^6 + 611*x^7 + 2925*x^8 + 15128*x^9 + 83903*x^10 + 495929*x^11 + 3108129*x^12 +...
%e A184175 where
%e A184175 G.f.: A(x) = 1/(1+x^2) + x/((1+x^2)*(1-x+x^2)) + x^2/((1+x^2)*(1-x+x^2)*(1-2*x+x^2)) + x^3/((1+x^2)*(1-x+x^2)*(1-2*x+x^2)*(1-3*x+x^2)) +... (End)
%p A184175 with(combinat): seq(add((-1)^j*binomial(n-j, j)*bell(n-2*j), j = 0 .. floor((1/2)*n)), n = 0 .. 25);
%t A184175 Table[Sum[(-1)^j*Binomial[n-j, j]*BellB[n-2*j], {j, 0, Floor[n/2]}], {n, 0, 25}] (* _Jean-François Alcover_, Feb 22 2017, translated from Maple *)
%o A184175 (PARI) {a(n) = my(A = sum(m=0,n, x^m/prod(k=0,m,1-k*x+x^2 +x*O(x^n)))); polcoeff(A,n)}
%o A184175 for(n=0,30,print1(a(n),", ")) \\ _Paul D. Hanna_, Sep 03 2017
%Y A184175 Cf. A184174, A184175, A184176, A000296.
%K A184175 nonn
%O A184175 0,4
%A A184175 _Emeric Deutsch_, Feb 09 2011