A274538 Number of set partitions of [n] such that each element is contained in a block whose index parity coincides with the parity of the element.

1, 1, 1, 2, 3, 7, 14, 39, 95, 304, 865, 3103, 10038, 39773, 143473, 620382, 2461099, 11504723, 49658054, 249102263, 1159930119, 6205900348, 30959905841, 175763987955, 934068692102, 5602484594053, 31563436487785, 199267671153562, 1185224170637619

Offset: 0

Author

Alois P. Heinz, Jun 27 2016

Keywords

• nonn

Comments

All odd elements are in blocks with an odd index and all even elements are in blocks with an even index.

Examples

			a(3) = 2: 13|2, 1|2|3.
a(4) = 3: 13|24, 1|24|3, 1|2|3|4.
a(5) = 7: 135|24, 13|24|5, 15|24|3, 1|24|35, 15|2|3|4, 1|2|35|4, 1|2|3|4|5.
a(6) = 14: 135|246, 13|246|5, 13|24|5|6, 15|246|3, 15|24|3|6, 1|246|35, 1|24|35|6, 15|26|3|4, 15|2|3|46, 1|26|35|4, 1|2|35|46, 1|26|3|4|5, 1|2|3|46|5, 1|2|3|4|5|6.
		

Links

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

Crossrefs

Row sums of A274537.

Column k=2 of A274835.

Cf. A011655.

Programs

Maple

b:= proc(n, m, t) option remember; `if`(n=0, 1, add(
      `if`(irem(j, 2)=t, b(n-1, max(m, j), 1-t), 0), j=1..m+1))
    end:
a:= n-> b(n, 0, 1):
seq(a(n), n=0..30);

Mathematica

b[n_, m_, t_] := b[n, m, t] = If[n == 0, 1, Sum[If[Mod[j, 2] == t, b[n - 1, Max[m, j], 1 - t], 0], {j, 1, m + 1}]];
a[n_] := b[n, 0, 1];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 23 2018, translated from Maple *)

Formula

a(n) = Sum_{k=0..n} A274537(n,k).

a(n) mod 2 = A011655(n) for n>=1.