A274538 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

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

LINKS

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

Wikipedia, Partition of a set

FORMULA

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

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

EXAMPLE

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.

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

CROSSREFS

Row sums of A274537.