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

1, 1, 2, 4, 13, 46, 184, 805, 3840, 19775, 109180, 642382, 4007712, 26399764, 182939900, 1329327991, 10100670183, 80053631844, 660328296777, 5657449573120, 50255253534312, 462096537041953, 4391648990609487, 43079839534282880

Offset: 0

Author

Emeric Deutsch, Feb 09 2011

Keywords

• nonn

Comments

a(n) = A184176(n,0).

Examples

			a(3) = 4 because we have 1-2-3, 1-23, 12-3, and 13-2.
a(4) = 13 because among the 15 (= Bell(4)) partitions of {1,2,3,4} only 123-4 and 1-234 have adjacent blocks of size 3.
		

Crossrefs

Cf. A184176, A124323, A000296, A184174, A184175.

Programs

Maple

with(combinat): seq(add((-1)^j*binomial(n-2*j, j)*bell(n-3*j), j = 0 .. floor((1/3)*n)), n = 0 .. 23);

Formula

a(n) = Sum_{j=0..floor(n/3)} (-1)^j * binomial(n-2j,j) * Bell(n-3j,j).