|
| |
|
|
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
|
|
|
|
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)):
|
|
|
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];
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|