login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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

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.

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

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 are A074881.

Cf. A000010, A000110, A051636, A058161.

Sequence in context: A166474 A054769 A003510 * A056098 A239201 A027361

Adjacent sequences:  A051622 A051623 A051624 * A051626 A051627 A051628

KEYWORD

nonn

AUTHOR

Vladeta Jovovic

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 18 19:30 EDT 2021. Contains 347534 sequences. (Running on oeis4.)