A327885 Number of set partitions of [n] such that at least one of the block sizes is 2.

0, 0, 1, 3, 9, 35, 150, 672, 3269, 17271, 97155, 578985, 3654750, 24331320, 170074177, 1244911605, 9520843575, 75890001665, 629104453236, 5413637745144, 48277814341765, 445463898405225, 4246785220234557, 41775507558584283, 423516880995944532

Offset: 0

Author

Alois P. Heinz, Sep 28 2019

Keywords

• nonn

Examples

			a(2) = 1: 12.
a(3) = 3: 12|3, 13|2, 1|23.
a(4) = 9: 12|34, 12|3|4, 13|24, 13|2|4, 14|23, 1|23|4, 14|2|3, 1|24|3, 1|2|34.
a(5) = 35: 123|45, 124|35, 125|34, 12|345, 12|34|5, 12|35|4, 12|3|45, 12|3|4|5, 134|25, 135|24, 13|245, 13|24|5, 13|25|4, 13|2|45, 13|2|4|5, 145|23, 14|235, 14|23|5, 15|234, 15|23|4, 1|23|45, 1|23|4|5, 14|25|3, 14|2|35, 14|2|3|5, 15|24|3, 1|24|35, 1|24|3|5, 15|2|34, 1|25|34, 1|2|34|5, 15|2|3|4, 1|25|3|4, 1|2|35|4, 1|2|3|45.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..576
• Wikipedia, Partition of a set

Crossrefs

Column k=2 of A327884.

Cf. A000110, A097514.

Programs

Maple

b:= proc(n, k) option remember; `if`(n=0, 1, add(
      `if`(j=k, 0, b(n-j, k)*binomial(n-1, j-1)), j=1..n))
    end:
a:= n-> b(n, 0)-b(n, 2):
seq(a(n), n=0..27);

Mathematica

b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[If[j == k, 0, b[n - j, k]* Binomial[n - 1, j - 1]], {j, n}]];
a[n_] := b[n, 0] - b[n, 2];
a /@ Range[0, 27] (* Jean-François Alcover, May 04 2020, after Maple *)

Formula

E.g.f.: exp(exp(x)-1) - exp(exp(x)-1-x^2/2).

a(n) = A000110(n) - A097514(n).