|
%I #78 Jul 05 2023 17:04:57
%S 1,2,5,17,67,362,2039,14170,109694,976412,8921002,101134244,
%T 1104940280,13914013024,191754490412,2824047042632,41304021782824,
%U 708492417746000,11629404776897384,222093818836736752,4351196253952132832,88481681599705382144,1781763397966126421200
%N Number of "labeled" cyclic subgroups of symmetric group S_n.
%C Number of unordered lists of powers of permutation of length n (equivalent to the definition). - _Olivier Gérard_, Jul 04 2011
%C Number of subgroups of S_n with different permutations generated by single permutation (see Mathematica procedure). - _Artur Jasinski_, Oct 27 2011
%D V. Jovovic, Some combinatorial characteristics of symmetric and alternating groups (in Russian), Belgrade, 1980, unpublished.
%H Alois P. Heinz, <a href="/A051625/b051625.txt">Table of n, a(n) for n = 1..130</a>
%H Peter J. Cameron, Andrea Lucchini and Colva M. Roney-Dougal, <a href="https://arxiv.org/abs/1609.06077">Generating sets of finite groups</a>, arXiv:1609.06077 [math.GR], 2016.
%H Adam Chojecki, Paweł Morgen, and Bartosz Kołodziejek, <a href="https://arxiv.org/abs/2307.00790">Learning permutation symmetries with gips in R</a>, arXiv:2307.00790 [stat.CO], 2023.
%H Piotr Graczyk, Hideyuki Ishi, Kołodziejek Bartosz, and Hélène Massam, <a href="https://arxiv.org/abs/2004.03503">Model selection in the space of Gaussian models invariant by symmetry</a>, arXiv:2004.03503 [math.ST], 2020.
%H L. Naughton and G. Pfeiffer, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Naughton/naughton2.html">Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group</a>, J. Int. Seq. 16 (2013) #13.5.8.
%H <a href="/index/Gre#groups">Index entries for sequences related to groups</a>
%F 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.
%e 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)>.
%e 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
%p parts:= proc(n,k) option remember;
%p if k = 1 then return {[n]} fi;
%p `union`(seq(map(t -> [op(t),j], procname(n-j*k,k-1)), j=0..floor(n/k)))
%p end proc:
%p 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)):
%p seq(F(n),n=1..30); # _Robert Israel_, Oct 04 2015
%t 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 *)
%t 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];
%t a[n_] := Module[{s = 0}, Do[s += permcount[p]/EulerPhi[LCM @@ p], {p, IntegerPartitions[n]}]; s];
%t Array[a, 23] (* _Jean-François Alcover_, Feb 25 2019, after _Andrew Howroyd_ *);
%t 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 *);
%o (PARI) \\ permcount is number of permutations of given type.
%o 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}
%o a(n)={my(s=0); forpart(p=n, s+=permcount(p)/eulerphi(lcm(Vec(p)))); s} \\ _Andrew Howroyd_, Jul 03 2018
%Y Row sums of A074881.
%Y Cf. A000010, A000110, A051636, A058161.
%K nonn
%O 1,2
%A _Vladeta Jovovic_
|
