cp's OEIS Frontend

A007359 Number of partitions of n into pairwise coprime parts that are >= 2.

%I A007359 M0143 #53 Dec 31 2020 18:31:06
%S A007359 1,0,1,1,1,2,1,3,2,3,3,5,4,6,5,5,8,9,10,11,11,10,14,18,19,18,20,20,25,
%T A007359 30,35,34,32,32,43,43,57,56,51,55,67,78,87,87,80,82,97,125,128,127,
%U A007359 128,127,146,182,191,185,184,193,213,263,290,279,258,271,312,354,404,402
%N A007359 Number of partitions of n into pairwise coprime parts that are >= 2.
%C A007359 This sequence is of interest for group theory. The partitions counted by a(n) correspond to conjugacy classes of optimal order of the symmetric group of n elements: they have no fixed point, their order is the direct product of their cycle lengths and they are not contained in a subgroup of Sym_p for p < n. A123131 gives the maximum order (LCM) reachable by these partitions.
%D A007359 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007359 Fausto A. C. Cariboni, <a href="/A007359/b007359.txt">Table of n, a(n) for n = 0..750</a> (terms 0..400 from Alois P. Heinz)
%H A007359 M. LeBrun & D. Hoey, <a href="/A007359/a007359.pdf">Emails</a>
%F A007359 a(n) = A051424(n) - A051424(n-1). - _Vladeta Jovovic_, Dec 11 2004
%e A007359 The a(17) = 9 strict partitions into pairwise coprime parts that are greater than 1 are (17), (15,2), (14,3), (13,4), (12,5), (11,6), (10,7), (9,8), (7,5,3,2). - _Gus Wiseman_, Apr 14 2018
%p A007359 with(numtheory):
%p A007359 b:= proc(n, i, s) option remember; local f;
%p A007359       if n=0 then 1
%p A007359     elif i<2 then 0
%p A007359     else f:= factorset(i);
%p A007359          b(n, i-1, select(x-> is(x<i), s)) +`if`(i<=n and f intersect s={},
%p A007359          b(n-i, i-1, select(x-> is(x<i), s union f)), 0)
%p A007359       fi
%p A007359     end:
%p A007359 a:= n-> b(n, n, {}):
%p A007359 seq(a(n), n=0..80);  # _Alois P. Heinz_, Mar 14 2012
%t A007359 b[n_, i_, s_] := b[n, i, s] = Module[{f}, If[n == 0 || i == 1, 1, If[i<2, 0, f = FactorInteger[i][[All, 1]]; b[n, i-1, Select[s, #<i&]]+If[i <= n && f ~Intersection~ s == {}, b[n-i, i-1, Select[s ~Union~ f, #<i&]], 0]]]]; a[n_] := b[n, n, {}]-b[n-1, n-1, {}]; Table[a[n], {n, 0, 80}] (* _Jean-François Alcover_, Feb 17 2014, after _Alois P. Heinz_ *)
%t A007359 Table[Length[Select[IntegerPartitions[n],FreeQ[#,1]&&(Length[#]===1||CoprimeQ@@#)&]],{n,20}] (* _Gus Wiseman_, Apr 14 2018 *)
%Y A007359 Cf. A000837, A007359, A007360, A051424, A101268, A123131, A184956, A187718, A289508, A289509, A298748, A302569, A302696, A302698, A302797.
%K A007359 nonn,easy
%O A007359 0,6
%A A007359 _N. J. A. Sloane_ and _Mira Bernstein_, following a suggestion from _Marc LeBrun_, Apr 28 1994
%E A007359 More precise definition from _Vladeta Jovovic_, Dec 11 2004
%E A007359 More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 13 2005