The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A051625 Number of "labeled" cyclic subgroups of symmetric group S_n. 12
1, 2, 5, 17, 67, 362, 2039, 14170, 109694, 976412, 8921002, 101134244, 1104940280, 13914013024, 191754490412, 2824047042632, 41304021782824, 708492417746000, 11629404776897384, 222093818836736752, 4351196253952132832, 88481681599705382144, 1781763397966126421200 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
COMMENTS
Number of unordered lists of powers of permutation of length n (equivalent to the definition). - Olivier Gérard, Jul 04 2011
Number of subgroups of S_n with different permutations generated by single permutation (see Mathematica procedure). - Artur Jasinski, Oct 27 2011
REFERENCES
V. Jovovic, Some combinatorial characteristics of symmetric and alternating groups (in Russian), Belgrade, 1980, unpublished.
LINKS
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.
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.
EXAMPLE
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
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 *);
PROG
(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
CROSSREFS
Row sums of A074881.
Sequence in context: A166474 A054769 A003510 * A056098 A239201 A027361
KEYWORD
nonn
AUTHOR
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 21:38 EDT 2024. Contains 372758 sequences. (Running on oeis4.)