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

1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 2, 0, 0, 0, 2, 0, 2, 0, 1, 0, 4, 0, 3, 0, 1, 0, 5, 0, 8, 0, 2, 0, 5, 0, 10, 0, 4, 0, 13, 0, 15, 0, 3, 1, 13, 0, 19, 0, 9, 1, 24, 0, 20, 2, 13, 2, 29, 0, 34, 2, 17, 2, 34, 1, 49, 2, 21, 3, 58, 2, 63, 3, 20, 7, 72, 2, 81, 3

Offset

31,11

Links

Alois P. Heinz, Table of n, a(n) for n = 31..251

Example

a(31) = 1: [6,10,15] = [2*3,2*5,3*5].
a(37) = 1: [10,12,15] = [2*5,2*2*3,3*5].
a(41) = 2: [6,15,20], [6,14,21].
a(43) = 2: [6,10,12,15], [10,15,18].
a(53) = 4: [6,12,15,20], [15,18,20], [6,12,14,21], [14,18,21].
a(55) = 3: [10,12,15,18], [6,10,15,24], [6,21,28].

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;
      if n<0 then 0
    elif n=0 then `if`(g>1, 0, 1)
    elif i<2 then 0
    else ok:= evalb(i<=n);
         for j in s while ok do ok:= igcd(i, j)>1 od;
         b(n, i-1, g, map(x->w(x, i), s)) +`if`(ok,
         b(n-i, i-1, igcd(i, g), map(x->w(x, i), {s[], 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}, Which[n<0, 0, n==0, If[g>1, 0, 1], i<2, 0, True, ok = i <= n; For[j = 1, ok && j <= Length[s], j++, ok = GCD[i, s[[j]]]>1]; b[n, i-1, g, Map[w[#, i]&, s]] + If[ok, b[n-i, i-1, GCD[i, g], Map[w[#, i]&, Union @ Append[s, i]]], 0]]]; a[n_] := b[n, n, 0, {}]; Table[a[n], {n, 31, 100}] (* Jean-François Alcover, Feb 15 2017, translated from Maple *)

Crossrefs

Cf. A200976, A018783.

Sequence in context: A359300 A029834 A318715 * A029833 A050948 A282695

Adjacent sequences: A202382 A202383 A202384 * A202386 A202387 A202388

Keyword

nonn

Author

Alois P. Heinz, Dec 18 2011

Status

approved