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

Column k=2 of A274835.

Cf. A011655.

Sequence in context: A296417 A296418 A006785 * A113182 A165433 A238728

Adjacent sequences: A274535 A274536 A274537 * A274539 A274540 A274541

Keyword

nonn

Author

Alois P. Heinz, Jun 27 2016

Status

approved