A202425 Number of partitions of n into parts having pairwise common factors but no overall common factor.

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

Author

Alois P. Heinz, Dec 19 2011

Keywords

• nonn

Examples

			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].
		

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 31..400 (terms 31..251 from Alois P. Heinz)

Crossrefs

Cf. A202385, A018783.

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.

Cf. A000837, A305148, A305843, A306006, A318717, A328673, A328867.

Programs

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

Formula

a(n > 0) = A328672(n) - 1. - Gus Wiseman, Nov 04 2019