A007359 Number of partitions of n into pairwise coprime parts that are >= 2. (Formerly M0143)

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, 30, 35, 34, 32, 32, 43, 43, 57, 56, 51, 55, 67, 78, 87, 87, 80, 82, 97, 125, 128, 127, 128, 127, 146, 182, 191, 185, 184, 193, 213, 263, 290, 279, 258, 271, 312, 354, 404, 402

Offset

0,6

Comments

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.

References

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..750 (terms 0..400 from Alois P. Heinz)

M. LeBrun & D. Hoey, Emails

Formula

a(n) = A051424(n) - A051424(n-1). - Vladeta Jovovic, Dec 11 2004

Example

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

Maple

with(numtheory):
b:= proc(n, i, s) option remember; local f;
      if n=0 then 1
    elif i<2 then 0
    else f:= factorset(i);
         b(n, i-1, select(x-> is(x<i), s)) +`if`(i<=n and f intersect s={},
         b(n-i, i-1, select(x-> is(x<i), s union f)), 0)
      fi
    end:
a:= n-> b(n, n, {}):
seq(a(n), n=0..80);  # Alois P. Heinz, Mar 14 2012

Mathematica

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 *)
Table[Length[Select[IntegerPartitions[n], FreeQ[#, 1]&&(Length[#]===1||CoprimeQ@@#)&]], {n, 20}] (* Gus Wiseman, Apr 14 2018 *)

Crossrefs

Cf. A000837, A007359, A007360, A051424, A101268, A123131, A184956, A187718, A289508, A289509, A298748, A302569, A302696, A302698, A302797.

Sequence in context: A029164 A364350 A053262 * A213424 A174427 A158206

Adjacent sequences: A007356 A007357 A007358 * A007360 A007361 A007362

Keyword

nonn,easy

Author

N. J. A. Sloane and Mira Bernstein, following a suggestion from Marc LeBrun, Apr 28 1994

Extensions

More precise definition from Vladeta Jovovic, Dec 11 2004

More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 13 2005

Status

approved