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.
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
KEYWORD
nonn
AUTHOR
STATUS
approved