cp's OEIS Frontend

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

%I A202425 #24 Jan 21 2021 03:00:22
%S A202425 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,
%T A202425 5,19,2,35,8,14,6,44,4,55,13,16,19,64,6,82,17,39,31,108,10,105,40,66,
%U A202425 46,161,14,182,61,97,72,207,37,287,85,144,93,357,59
%N A202425 Number of partitions of n into parts having pairwise common factors but no overall common factor.
%H A202425 Fausto A. C. Cariboni, <a href="/A202425/b202425.txt">Table of n, a(n) for n = 31..400</a> (terms 31..251 from Alois P. Heinz)
%F A202425 a(n > 0) = A328672(n) - 1. - _Gus Wiseman_, Nov 04 2019
%e A202425 a(31) = 1: [6,10,15] = [2*3,2*5,3*5].
%e A202425 a(37) = 2: [6,6,10,15], [10,12,15].
%e A202425 a(41) = 3: [6,10,10,15], [6,15,20], [6,14,21].
%e A202425 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].
%e A202425 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].
%p A202425 with(numtheory):
%p A202425 w:= (m, h)-> mul(`if`(j>=h, 1, j), j=factorset(m)):
%p A202425 b:= proc(n, i, g, s) option remember; local j, ok, si;
%p A202425       if n<0 then 0
%p A202425     elif n=0 then `if`(g>1, 0, 1)
%p A202425     elif i<2 or member(1, s) then 0
%p A202425     else ok:= evalb(i<=n);
%p A202425          si:= map(x->w(x, i), s);
%p A202425          for j in s while ok do ok:= igcd(i, j)>1 od;
%p A202425          b(n, i-1, g, si) +`if`(ok, add(b(n-t*i, i-1, igcd(i, g),
%p A202425                       si union {w(i,i)} ), t=1..iquo(n, i)), 0)
%p A202425       fi
%p A202425     end:
%p A202425 a:= n-> b(n, n, 0, {}):
%p A202425 seq(a(n), n=31..100);
%t A202425 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 *)
%t A202425 Table[Length[Select[IntegerPartitions[n],GCD@@#==1&&And@@(GCD[##]>1&)@@@Tuples[#,2]&]],{n,0,40}] (* _Gus Wiseman_, Nov 04 2019 *)
%Y A202425 Cf. A202385, A018783.
%Y A202425 The version with only distinct parts compared is A328672.
%Y A202425 The Heinz numbers of these partitions are A328868.
%Y A202425 The strict case is A202385, which is essentially the same as A318715.
%Y A202425 The version for non-isomorphic multiset partitions is A319759.
%Y A202425 The version for set-systems is A326364.
%Y A202425 Intersecting partitions are A200976.
%Y A202425 Cf. A000837, A305148, A305843, A306006, A318717, A328673, A328867.
%K A202425 nonn
%O A202425 31,7
%A A202425 _Alois P. Heinz_, Dec 19 2011