OFFSET
0,3
COMMENTS
Two parts are coprime if they have no common divisor greater than 1.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..500
EXAMPLE
The a(6) = 10 partitions whose parts are all equal or whose distinct parts are pairwise coprime are (6), (51), (411), (33), (321), (3111), (222), (2211), (21111), (111111).
MAPLE
g:= proc(n, i, s) `if`(n=0, 1, `if`(i<1, 0,
b(n, i, select(x-> x<=i, s))))
end:
b:= proc(n, i, s) option remember; g(n, i-1, s)+(f->
`if`(f intersect s={}, add(g(n-i*j, i-1, s union f)
, j=1..n/i), 0))(numtheory[factorset](i))
end:
a:= n-> g(n$2, {}):
seq(a(n), n=0..60); # Alois P. Heinz, May 17 2018
MATHEMATICA
Table[Select[IntegerPartitions[n], Or[SameQ@@#, CoprimeQ@@Union[#]]&]//Length, {n, 20}]
(* Second program: *)
g[n_, i_, s_] := If[n == 0, 1, If[i < 1, 0, b[n, i, Select[s, # <= i &]]]];
b[n_, i_, s_] := b[n, i, s] = g[n, i - 1, s] + Function[f,
If[f ~Intersection~ s == {}, Sum[g[n - i*j, i - 1, s ~Union~ f],
{j, 1, n/i}], 0]][FactorInteger[i][[All, 1]]];
a[n_] := g[n, n, {}];
a /@ Range[0, 60] (* Jean-François Alcover, May 10 2021, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 17 2018
STATUS
approved