A200976 Number of partitions of n such that each pair of parts (if any) has a common factor.

1, 0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 14, 1, 16, 9, 22, 1, 38, 1, 45, 17, 57, 1, 94, 7, 102, 30, 138, 1, 218, 2, 231, 58, 298, 21, 451, 3, 491, 103, 644, 4, 919, 4, 1005, 203, 1257, 7, 1784, 20, 1993, 301, 2441, 10, 3365, 70, 3737, 496, 4569, 17, 6252, 23, 6848

Offset: 0

Author

Alois P. Heinz, Nov 29 2011

Keywords

• nonn

Comments

a(n) is different from A018783(n) for n = 0, 31, 37, 41, 43, 46, 47, 49, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, ... .

Every pair of (possibly equal) parts has a common factor > 1. These partitions are said to be (pairwise) intersecting. - Gus Wiseman, Nov 04 2019

Examples

			a(0) = 1: [];
a(4) = 2: [2,2], [4];
a(9) = 3: [3,3,3], [3,6], [9];
a(31) = 2: [6,10,15], [31];
a(41) = 4: [6,10,10,15], [6,15,20], [6,14,21], [41].
		

Links

• Fausto A. C. Cariboni, Table of n, a(n) for n = 0..350 (terms 0..250 from Alois P. Heinz)
• L. Naughton, G. Pfeiffer, Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group, J. Int. Seq. 16 (2013) #13.5.8

Crossrefs

Cf. A018783.

The version with only distinct parts compared is A328673.

The relatively prime case is A202425.

The strict case is A318717.

The version for non-isomorphic multiset partitions is A319752.

The version for set-systems is A305843.

Cf. A000837, A305148, A305854, A306006, A316476, A328672, A328867, A328868.

Programs

Maple

b:= proc(n, j, s) local ok, i;
      if n=0 then 1
    elif j<2 then 0
    else ok:= true;
         for i in s while ok do ok:= evalb(igcd(i, j)<>1) od;
         `if`(ok, add(b(n-j*k, j-1, [s[], j]), k=1..n/j), 0) +b(n, j-1, s)
      fi
    end:
a:= n-> b(n, n, []):
seq(a(n), n=0..62);

Mathematica

b[n_, j_, s_] := Module[{ok, i, is}, Which[n == 0, 1, j < 2, 0, True, ok = True; For[is = 1, is <= Length[s] && ok, is++, i = s[[is]]; ok = GCD[i, j] != 1]; If[ok, Sum[b[n-j*k, j-1, Append[s, j]], {k, 1, n/j}], 0] + b[n, j-1, s]]]; a[n_] := b[n, n, {}]; Table[a[n], {n, 0, 62}] (* Jean-François Alcover, Dec 26 2013, translated from Maple *)
Table[Length[Select[IntegerPartitions[n],And[And@@(GCD[##]>1&)@@@Select[Tuples[Union[#],2],LessEqual@@#&]]&]],{n,0,20}] (* Gus Wiseman, Nov 04 2019 *)

Formula

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