A051625 Number of "labeled" cyclic subgroups of symmetric group S_n.
1, 2, 5, 17, 67, 362, 2039, 14170, 109694, 976412, 8921002, 101134244, 1104940280, 13914013024, 191754490412, 2824047042632, 41304021782824, 708492417746000, 11629404776897384, 222093818836736752, 4351196253952132832, 88481681599705382144, 1781763397966126421200
Offset: 1
Keywords
Examples
The 5 cyclic subgroups of symmetric group S_3 are: {Id}, the 3 subgroups {Id,(a,b)}, {Id,(b,c)}, {Id,(a,c)} and the Alternating group A_3: <Id, (a,b,c), (a,c,b)>.
The 17 cyclic subgroups of symmetric group S_4 are: {Id}, the 6 subgroups of type <(a,b)>, the 3 subgroups of type <(a,b)(c,d)>, the 4 subgroups of type <(a,b,c)> and the 3 subgroups of type <(a,b,c,d)>. - _Bernard Schott_, Feb 25 2019
References
- V. Jovovic, Some combinatorial characteristics of symmetric and alternating groups (in Russian), Belgrade, 1980, unpublished.
Links
- Alois P. Heinz, Table of n, a(n) for n = 1..130
- Peter J. Cameron, Andrea Lucchini and Colva M. Roney-Dougal, Generating sets of finite groups, arXiv:1609.06077 [math.GR], 2016.
- Adam Chojecki, Paweł Morgen, and Bartosz Kołodziejek, Learning permutation symmetries with gips in R, arXiv:2307.00790 [stat.CO], 2023.
- Piotr Graczyk, Hideyuki Ishi, Kołodziejek Bartosz, and Hélène Massam, Model selection in the space of Gaussian models invariant by symmetry, arXiv:2004.03503 [math.ST], 2020.
- L. Naughton and G. Pfeiffer, Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group, J. Int. Seq. 16 (2013) #13.5.8.
- Index entries for sequences related to groups
Programs
-
Maple
parts:= proc(n,k) option remember; if k = 1 then return {[n]} fi; `union`(seq(map(t -> [op(t),j], procname(n-j*k,k-1)), j=0..floor(n/k))) end proc: F:= n -> add(n!/mul(p[k]!*k^p[k],k=1..nops(p)) / numtheory:-phi(ilcm(op(select(t -> p[t]<>0, [$1..n])))), p = parts(n,n)): seq(F(n),n=1..30); # Robert Israel, Oct 04 2015 -
Mathematica
cc = {}; Do[aa = {}; kk = Table[n, {n, 1, ord}]; pp = Permutations[kk]; Do[per17 = {}; AppendTo[per17, pp[[p]]]; run = 0; ile = Length[per17]; min = 1; max = ile; While[ile < ord!, run = run + 1; if = False; Do[Do[vec0 = Table[0, {n, 1, ord}]; Do[vec0[[per17[[k]][[n]]]] = per17[[m]][[n]], {n, 1, ord}]; bp = vec0; If[Position[per17, bp] == {}, ile = ile + 1; Print[ile]; if = True; AppendTo[per17, bp]]; vec0 = Table[0, {n, 1, ord}]; Do[vec0[[per17[[m]][[n]]]] = per17[[k]][[n]], {n, 1, ord}]; bl = vec0; If[Position[per17, bl] == {}, ile = ile + 1; if = True; AppendTo[per17, bl]]; If[ile == ord!, Break[]], {k, 1, max}], {m, min, max}]; If[if == False, Break[], min = max + 1; max = ile]]; AppendTo[aa, Sort[per17]], {p, 1, ord!}]; AppendTo[cc, Length[Union[aa]]], {ord, 1, 7}]; cc (* Artur Jasinski, Oct 27 2011 *) permcount[v_] := Module[{m=1, s=0, k=0, t}, For[i=1, i <= Length[v], i++, t = v[[i]]; k = If[i>1 && t == v[[i-1]], k+1, 1]; m *= t*k; s += t]; s!/m]; a[n_] := Module[{s = 0}, Do[s += permcount[p]/EulerPhi[LCM @@ p], {p, IntegerPartitions[n]}]; s]; Array[a, 23] (* Jean-François Alcover, Feb 25 2019, after Andrew Howroyd *); content[li_List] := Table[Count[li, i], {i, Tr[li]}]; Table[Tr[(n!/(Times @@ (Range[Tr[#1]]^content[#1]*content[#1]!)*EulerPhi[LCM @@ Flatten[Position[content[#1], ?Positive]]]) & ) /@ IntegerPartitions[n] ], {n, 23}] (* _Wouter Meeussen, Jan 06 2021 *); -
PARI
\\ permcount is number of permutations of given type. permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m} a(n)={my(s=0); forpart(p=n, s+=permcount(p)/eulerphi(lcm(Vec(p)))); s} \\ Andrew Howroyd, Jul 03 2018
Formula
a(n) = Sum_{pi} n!/(k_1!*1^k_1*k_2!*2^k_2*...*k_n!*n^k_n*phi(lcm{i:k_i != 0})), where pi runs through all partitions k_1+2*k_2+...+n*k_n=n and phi is Euler's function.
Comments