A332398 Number of set partitions of [n] where all prime-indexed blocks are singletons.

1, 1, 2, 4, 8, 17, 40, 105, 304, 958, 3255, 11851, 46096, 191648, 854551, 4101826, 21213282, 117747119, 695773801, 4332490151, 28149712546, 189300600481, 1309755334070, 9286984108299, 67327505784439, 498502290046850, 3769028024302567, 29115361551715499

Offset: 0

Author

Alois P. Heinz, Feb 10 2020

Keywords

• nonn

Examples

			a(2) = 2: 12, 1|2.
a(3) = 4: 123, 12|3, 13|2, 1|2|3.
a(4) = 8: 1234, 123|4, 124|3, 12|3|4, 134|2, 13|2|4, 14|2|3, 1|2|3|4.
a(5) = 17: 12345, 1234|5, 1235|4, 123|4|5, 1245|3, 124|3|5, 125|3|4, 12|3|4|5, 1345|2, 134|2|5, 135|2|4, 13|2|4|5, 145|2|3, 14|2|3|5, 15|2|3|4, 1|2|3|45, 1|2|3|4|5.
		

Links

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

Crossrefs

Cf. A000040, A000110, A007476, A332248.

Programs

Maple

b:= proc(n, m) option remember; `if`(n=0, 1, add(`if`(j<=m
       and isprime(j), 0, b(n-1, max(j, m))), j=1..m+1))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..32);
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, add(b(n-j, i+1)*
       binomial(n-1, j-1), j=1..`if`(isprime(i+1), 1, n)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..32);

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[b[n-j, i+1] Binomial[n-1, j-1], {j, 1, If[PrimeQ[i+1], 1, n]}]];
a[n_] := b[n, 0];
a /@ Range[0, 32] (* Jean-François Alcover, May 07 2020, after 2nd Maple program *)