A218970 Number of connected cyclic conjugacy classes of subgroups of the symmetric group.

1, 1, 1, 1, 2, 1, 4, 1, 5, 3, 8, 2, 14, 3, 17, 11, 24, 10, 40, 16, 53, 35, 71, 43, 112, 68, 144, 112, 203, 152, 301, 219, 393, 342, 540, 474, 770, 661, 1022, 967, 1397, 1313, 1928, 1821, 2565, 2564, 3439, 3445, 4676, 4687, 6186, 6406, 8215, 8543, 10974, 11435

Offset

0,5

Comments

a(n) is also the number of connected partitions of n in the following sense. Given a partition of n, the vertices are the parts of the partition and two vertices are connected if and only if their gcd is greater than 1. We call a partition connected if the graph is connected.

Links

Table of n, a(n) for n=0..55.

Liam Naughton and Goetz Pfeiffer, Integer sequences realized by the subgroup pattern of the symmetric group, arXiv:1211.1911 [math.GR], 2012-2013.

Liam Naughton, CountingSubgroups.g

Liam Naughton and Goetz Pfeiffer, Tomlib, The GAP table of marks library

Formula

For n > 1, a(n) = A304716(n) - 1. - Gus Wiseman, Dec 03 2018

Example

From Gus Wiseman, Dec 03 2018: (Start)
The a(12) = 14 connected integer partitions of 12:
  (12)  (6,6)   (4,4,4)  (3,3,3,3)  (4,2,2,2,2)  (2,2,2,2,2,2)
        (8,4)   (6,3,3)  (4,4,2,2)
        (9,3)   (6,4,2)  (6,2,2,2)
        (10,2)  (8,2,2)
(End)

Mathematica

zsm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[Less@@#, GCD@@s[[#]]]>1&]}, If[c=={}, s, zsm[Sort[Append[Delete[s, List/@c[[1]]], LCM@@s[[c[[1]]]]]]]]];
Table[Length[Select[IntegerPartitions[n], Length[zsm[#]]==1&]], {n, 10}]

Crossrefs

Cf. A018783, A200976, A286518, A286520, A290103, A304714, A304716, A305078, A305079, A322306, A322307.

Sequence in context: A331885 A298971 A328602 * A216952 A114326 A308175

Adjacent sequences: A218967 A218968 A218969 * A218971 A218972 A218973

Keyword

nonn

Author

Liam Naughton, Nov 26 2012

Extensions

More terms from Gus Wiseman, Dec 03 2018

Status

approved