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,5

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

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

Formula

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

Example

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

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

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.

Sequence in context: A083711 A339619 A018783 * A328187 A331885 A298971

Adjacent sequences: A200973 A200974 A200975 * A200977 A200978 A200979

Keyword

nonn

Author

Alois P. Heinz, Nov 29 2011

Status

approved