|
%I #51 Jan 19 2021 21:54:49
%S 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,
%T 138,1,218,2,231,58,298,21,451,3,491,103,644,4,919,4,1005,203,1257,7,
%U 1784,20,1993,301,2441,10,3365,70,3737,496,4569,17,6252,23,6848
%N Number of partitions of n such that each pair of parts (if any) has a common factor.
%C 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, ... .
%C Every pair of (possibly equal) parts has a common factor > 1. These partitions are said to be (pairwise) intersecting. - _Gus Wiseman_, Nov 04 2019
%H Fausto A. C. Cariboni, <a href="/A200976/b200976.txt">Table of n, a(n) for n = 0..350</a> (terms 0..250 from Alois P. Heinz)
%H L. Naughton, G. Pfeiffer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Naughton/naughton2.html">Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group</a>, J. Int. Seq. 16 (2013) #13.5.8
%F a(n > 0) = A328673(n) - 1. - _Gus Wiseman_, Nov 04 2019
%e a(0) = 1: [];
%e a(4) = 2: [2,2], [4];
%e a(9) = 3: [3,3,3], [3,6], [9];
%e a(31) = 2: [6,10,15], [31];
%e a(41) = 4: [6,10,10,15], [6,15,20], [6,14,21], [41].
%p b:= proc(n, j, s) local ok, i;
%p if n=0 then 1
%p elif j<2 then 0
%p else ok:= true;
%p for i in s while ok do ok:= evalb(igcd(i, j)<>1) od;
%p `if`(ok, add(b(n-j*k, j-1, [s[], j]), k=1..n/j), 0) +b(n, j-1, s)
%p fi
%p end:
%p a:= n-> b(n, n, []):
%p seq(a(n), n=0..62);
%t 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 *)
%t Table[Length[Select[IntegerPartitions[n],And[And@@(GCD[##]>1&)@@@Select[Tuples[Union[#],2],LessEqual@@#&]]&]],{n,0,20}] (* _Gus Wiseman_, Nov 04 2019 *)
%Y Cf. A018783.
%Y The version with only distinct parts compared is A328673.
%Y The relatively prime case is A202425.
%Y The strict case is A318717.
%Y The version for non-isomorphic multiset partitions is A319752.
%Y The version for set-systems is A305843.
%Y Cf. A000837, A305148, A305854, A306006, A316476, A328672, A328867, A328868.
%K nonn
%O 0,5
%A _Alois P. Heinz_, Nov 29 2011
|
