

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(n1).  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, i1, select(x> is(x<i), s)) +`if`(i<=n and f intersect s={},
b(ni, i1, 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, i1, Select[s, #<i&]]+If[i <= n && f ~Intersection~ s == {}, b[ni, i1, Select[s ~Union~ f, #<i&]], 0]]]]; a[n_] := b[n, n, {}]b[n1, n1, {}]; Table[a[n], {n, 0, 80}] (* JeanFrançois Alcover, Feb 17 2014, after Alois P. Heinz *)
Table[Length[Select[IntegerPartitions[n], FreeQ[#, 1]&&(Length[#]===1CoprimeQ@@#)&]], {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



