A363429 Number of set partitions of [n] such that each block has at most one even element.

1, 1, 2, 5, 10, 37, 77, 372, 799, 4736, 10427, 73013, 163967, 1322035, 3017562, 27499083, 63625324, 646147067, 1512354975, 16926317722, 40012800675, 489109544320, 1166271373797, 15455199988077, 37134022033885, 530149003318273, 1282405154139046, 19619325078384593

Offset

0,3

Links

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

Wikipedia, Partition of a set

Formula

a(n) = Sum_{k=0..ceiling(n/2)} floor(n/2)^k * binomial(ceiling(n/2),k) * Bell(ceiling(n/2)-k).

Example

a(0) = 1: () the empty partition.
a(1) = 1: 1.
a(2) = 2: 12, 1|2.
a(3) = 5: 123, 12|3, 13|2, 1|23, 1|2|3.
a(4) = 10: 123|4, 12|34, 12|3|4, 134|2, 13|2|4, 14|23, 1|23|4, 14|2|3, 1|2|34, 1|2|3|4.

Maple

b:= proc(n, m) option remember; `if`(n=0, 1,
      b(n-1, m+1)+m*b(n-1, m))
    end:
a:= n-> (h-> b(n-h, h))(iquo(n, 2)):
seq(a(n), n=0..30);

Crossrefs

Bisection gives: A134980 (even part).

Cf. A000110, A110132 (exactly one even), A124421 (at least one even), A363430 (at most one odd).

Sequence in context: A144636 A320430 A018418 * A290032 A155217 A004143

Adjacent sequences: A363426 A363427 A363428 * A363430 A363431 A363432

Keyword

nonn

Author

Alois P. Heinz, Jun 01 2023

Status

approved