A274547 Number of set partitions of [n] with alternating parity of elements.

1, 1, 2, 4, 8, 18, 40, 101, 254, 723, 2064, 6586, 21143, 74752, 266078, 1029983, 4013425, 16843526, 71136112, 321150717, 1458636308, 7038678613, 34161890155, 175261038904, 904125989974, 4909033438008, 26795600521492, 153376337926066, 882391616100249

Offset: 0

Author

Alois P. Heinz, Jun 27 2016

Keywords

• nonn

Examples

			a(5) = 18: 12345, 1234|5, 123|45, 123|4|5, 12|345, 12|34|5, 12|3|45, 12|3|4|5, 145|23, 1|2345, 1|234|5, 1|23|45, 1|23|4|5, 145|2|3, 1|2|345, 1|2|34|5, 1|2|3|45, 1|2|3|4|5.
a(6) = 40: 123456, 12345|6, 1234|56, 1234|5|6, 123|456, 123|45|6, 123|4|56, 123|4|5|6, 1256|34, 12|3456, 12|345|6, 12|34|56, 12|34|5|6, 1256|3|4, 12|3|456, 12|3|45|6, 12|3|4|56, 12|3|4|5|6, 145|236, 145|23|6, 1|23456, 1|2345|6, 1|234|56, 1|234|5|6, 1|23|456, 1|23|45|6, 1|23|4|56, 1|23|4|5|6, 145|2|36, 145|2|3|6, 1|256|34, 1|2|3456, 1|2|345|6, 1|2|34|56, 1|2|34|5|6, 1|256|3|4, 1|2|3|456, 1|2|3|45|6, 1|2|3|4|56, 1|2|3|4|5|6.
		

Links

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

Crossrefs

Row sums of A274581.

Cf. A124419, A274310 (parities alternate within blocks), A363519.

Column k=2 of A274859.

Programs

Maple

b:= proc(l, i, t) option remember; `if`(l=[], 1, add(`if`(l[j]=t,
       b(subsop(j=[][], l), j, 1-t), 0), j=[1, $i..nops(l)]))
    end:
a:= n-> b([seq(irem(i, 2), i=2..n)], 1, 0):
seq(a(n), n=0..25);

Mathematica

b[l_, i_, t_] := b[l, i, t] = If[l == {}, 1, Sum[If[l[[j]] == t, b[ReplacePart[l, j -> Sequence[]], j, 1-t], 0], {j, Prepend[Range[i, Length[l]], 1]}]]; a[n_] := b[Table[Mod[i, 2], {i, 2, n}], 1, 0]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 15 2017, translated from Maple *)

Formula

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

a(n) = A363519(n,max(0,n-1)). - Alois P. Heinz, Jun 07 2023