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,4

Links

Alois P. Heinz, Table of n, a(n) for n = 0..576

Wikipedia, Partition of a set

Formula

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

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

Example

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.

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

Crossrefs

Column k=2 of A327884.

Cf. A000110, A097514.

Sequence in context: A369389 A225041 A335642 * A074507 A217924 A030268

Adjacent sequences: A327882 A327883 A327884 * A327886 A327887 A327888

Keyword

nonn

Author

Alois P. Heinz, Sep 28 2019

Status

approved