login
A202425
Number of partitions of n into parts having pairwise common factors but no overall common factor.
8
1, 0, 0, 0, 0, 0, 2, 0, 0, 0, 3, 0, 3, 0, 0, 1, 6, 0, 5, 0, 2, 2, 9, 0, 8, 2, 4, 3, 16, 0, 22, 5, 6, 5, 19, 2, 35, 8, 14, 6, 44, 4, 55, 13, 16, 19, 64, 6, 82, 17, 39, 31, 108, 10, 105, 40, 66, 46, 161, 14, 182, 61, 97, 72, 207, 37, 287, 85, 144, 93, 357, 59
OFFSET
31,7
LINKS
Fausto A. C. Cariboni, Table of n, a(n) for n = 31..400 (terms 31..251 from Alois P. Heinz)
FORMULA
a(n > 0) = A328672(n) - 1. - Gus Wiseman, Nov 04 2019
EXAMPLE
a(31) = 1: [6,10,15] = [2*3,2*5,3*5].
a(37) = 2: [6,6,10,15], [10,12,15].
a(41) = 3: [6,10,10,15], [6,15,20], [6,14,21].
a(47) = 6: [6,6,10,10,15], [10,10,12,15], [6,6,15,20], [12,15,20], [6,6,14,21], [12,14,21].
a(49) = 5: [6,6,6,6,10,15], [6,6,10,12,15], [10,12,12,15], [6,10,15,18], [10,15,24].
MAPLE
with(numtheory):
w:= (m, h)-> mul(`if`(j>=h, 1, j), j=factorset(m)):
b:= proc(n, i, g, s) option remember; local j, ok, si;
if n<0 then 0
elif n=0 then `if`(g>1, 0, 1)
elif i<2 or member(1, s) then 0
else ok:= evalb(i<=n);
si:= map(x->w(x, i), s);
for j in s while ok do ok:= igcd(i, j)>1 od;
b(n, i-1, g, si) +`if`(ok, add(b(n-t*i, i-1, igcd(i, g),
si union {w(i, i)} ), t=1..iquo(n, i)), 0)
fi
end:
a:= n-> b(n, n, 0, {}):
seq(a(n), n=31..100);
MATHEMATICA
w[m_, h_] := Product[If[j >= h, 1, j], {j, FactorInteger[m][[All, 1]]}]; b[n_, i_, g_, s_] := b[n, i, g, s] = Module[{j, ok, si}, Which[n<0, 0, n == 0, If[g>1, 0, 1], i<2 || MemberQ[s, 1], 0, True, ok = (i <= n); si = w[#, i]& /@ s; Do[If[ok, ok = (GCD[i, j]>1)], {j, s}]; b[n, i-1, g, si] + If[ok, Sum[b[n-t*i, i-1, GCD[i, g], si ~Union~ {w[i, i]}], {t, 1, Quotient[n, i]}], 0]]]; a[n_] := b[n, n, 0, {}]; Table[a[n], {n, 31, 100}] (* Jean-François Alcover, Feb 16 2017, translated from Maple *)
Table[Length[Select[IntegerPartitions[n], GCD@@#==1&&And@@(GCD[##]>1&)@@@Tuples[#, 2]&]], {n, 0, 40}] (* Gus Wiseman, Nov 04 2019 *)
CROSSREFS
The version with only distinct parts compared is A328672.
The Heinz numbers of these partitions are A328868.
The strict case is A202385, which is essentially the same as A318715.
The version for non-isomorphic multiset partitions is A319759.
The version for set-systems is A326364.
Intersecting partitions are A200976.
Sequence in context: A330936 A284687 A046268 * A292374 A292376 A257685
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Dec 19 2011
STATUS
approved