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!)
A007359 Number of partitions of n into pairwise coprime parts that are >= 2.
(Formerly M0143)
30
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 (list; graph; refs; listen; history; text; internal format)
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

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

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: A319318 A029164 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

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 17 18:14 EST 2020. Contains 332005 sequences. (Running on oeis4.)