login
Number of permutation groups of degree n (or, number of distinct subgroups of symmetric group S_n, counting conjugates as distinct).
(Formerly M1690)
16

%I M1690 #62 Dec 22 2023 12:10:43

%S 1,1,2,6,30,156,1455,11300,151221,1694723,29594446,404126228,

%T 10594925360,175238308453,5651774693595,117053117995400,

%U 5320744503742316,125889331236297288,7598016157515302757

%N Number of permutation groups of degree n (or, number of distinct subgroups of symmetric group S_n, counting conjugates as distinct).

%C Labeled version of A000638.

%C L. Pyber shows c^(n^2(1+o(1))) <= a(n) <= d^(n^2(1+o(1))), c=2^(1/16), d=24^(1/6); conjectures lower bound is accurate.

%D C. C. Sims, Computational methods in the study of permutation groups, pp. 169-183 of J. Leech, editor, Computational Problems in Abstract Algebra. Pergamon, Oxford, 1970.

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

%H Piotr Graczyk, Hideyuki Ishi, Kołodziejek Bartosz, Hélène Massam, <a href="https://arxiv.org/abs/2004.03503">Model selection in the space of Gaussian models invariant by symmetry</a>, arXiv:2004.03503 [math.ST], 2020.

%H D. F. Holt, <a href="http://homepages.warwick.ac.uk/~mareg/download/papers/symsubs/symsubs.pdf">Enumerating subgroups of the symmetric group</a>.

%H D. Holt, <a href="/A000019/a000019_1.pdf">Enumerating subgroups of the symmetric group</a>, in Computational Group Theory and the Theory of Groups, II, edited by L.-C. Kappe, A. Magidin and R. Morse. AMS Contemporary Mathematics book series, vol. 511, pp. 33-37. [Annotated copy]

%H J. Labelle and Y. N. Yeh, <a href="http://dx.doi.org/10.1016/0097-3165(89)90019-8">The relation between Burnside rings and combinatorial species</a>, J. Combin. Theory, A 50 (1989), 269-284.

%H L. Naughton and G. Pfeiffer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Naughton/naughton2.html">Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group</a>, J. Int. Seq. 16 (2013) #13.5.8.

%H Götz Pfeiffer, <a href="http://schmidt.nuigalway.ie/subgroups">Numbers of subgroups of various families of groups</a>

%H L. Pyber, <a href="https://www.jstor.org/stable/2946623">Enumerating Finite Groups of Given Order</a>, Ann. Math. 137 (1993), 203-220.

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H Dashiell Stander, Qinan Yu, Honglu Fan, and Stella Biderman, <a href="https://arxiv.org/abs/2312.06581">Grokking Group Multiplication with Cosets</a>, arXiv:2312.06581 [cs.LG], 2023. See footnote, p. 25.

%H <a href="/index/Gre#groups">Index entries for sequences related to groups</a>

%F Exponential transform of A116655. Binomial transform of A116693. - _Christian G. Bower_, Feb 23 2006

%o (Magma) n := 5; &+[ Length(s):s in SubgroupLattice(Sym(n)) ];

%o (GAP) List([2..5],n->Sum( List( ConjugacyClassesSubgroups( SymmetricGroup(n)), Size))); [Alexander Hulpke]

%Y Cf. A000001, A000019, A000638.

%K nonn,hard,more,nice

%O 0,3

%A _N. J. A. Sloane_, _Simon Plouffe_

%E a(9) and a(10) from _Alexander Hulpke_, Dec 03 2004

%E More terms from a(11) and a(12) added by _Christian G. Bower_, Feb 23 2006 based on Goetz Pfeiffer's web page.

%E a(13) added by _Liam Naughton_, Jun 09 2011

%E a(14)-a(18) from Holt reference, _Wouter Meeussen_, Jul 02 2013