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