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

1, 1, 0, 0, 1, 2, 0, 0, 20, 48, 0, 0, 1147, 3968, 0, 0, 173203, 709488, 0, 0, 53555964, 246505600, 0, 0, 28368601065, 148963383616, 0, 0, 24044155851601, 141410718244864, 0, 0, 30934515698084780, 198914201874983936, 0, 0, 57215369885233295955, 398742900995358584320

Offset: 0

Author

Alois P. Heinz, May 17 2023

Keywords

• nonn

Comments

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

Examples

			a(0) = 1: (), the empty partition.
a(1) = 1: 1.
a(4) = 1: 1|24|3.
a(5) = 2: 135|24, 1|24|3|5.
a(8) = 20: 135|2468|7, 135|24|68|7, 137|2468|5, 137|24|5|68, 135|26|48|7, 135|28|46|7, 137|26|48|5, 137|28|46|5, 157|2468|3, 157|24|3|68, 1|2468|357, 1|24|357|68, 1|2468|3|5|7, 1|24|3|5|68|7, 157|26|3|48, 157|28|3|46, 1|26|357|48, 1|28|357|46, 1|26|3|48|5|7, 1|28|3|46|5|7.
		

Links

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

Crossrefs

Cf. A000110, A003724, A005046, A124419, A274538, A275679.

Programs

Maple

b:= proc(n, t) option remember; `if`(n=0, 1, add(
     `if`((j+t)::even, b(n-j, t)*binomial(n-1, j-1), 0), j=1..n))
    end:
a:= n-> (h-> b(n-h, 1)*b(h, 0))(iquo(n, 2)):
seq(a(n), n=0..40);

Mathematica

b[n_, t_] := b[n, t] = If[n == 0, 1, Sum[If[EvenQ[j + t], b[n - j, t]* Binomial[n - 1, j - 1], 0], {j, 1, n}]];
a[n_] := b[n - #, 1]*b[#, 0]&[Quotient[n, 2]];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 18 2023, after Alois P. Heinz *)

Formula

a(n) = A003724(ceiling(n/2)) * A005046(floor(n/4)) if (n mod 4) in {0,1}.

a(n) = 0 if (n mod 4) in {2,3}.