login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A200976 Number of partitions of n such that each pair of parts (if any) has a common factor. 9
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 (list; graph; refs; listen; history; text; internal format)
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

Alois P. Heinz, Table of n, a(n) for n = 0..250

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: A214579 A083711 A018783 * A328187 A331885 A298971

Adjacent sequences:  A200973 A200974 A200975 * A200977 A200978 A200979

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Nov 29 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 19 00:35 EST 2020. Contains 332028 sequences. (Running on oeis4.)