A181951 -id:A181951 - cp's OEIS frontend

A186202 The maximal set of disjoint prime cycle permutations on n elements which generate unique subgroups of S(n).

0, 1, 4, 13, 41, 151, 652, 2675, 10579, 59071, 711536, 6180307, 76629775, 873676259, 7496233396, 49493077951, 1571673343007, 24729597043375, 584039297226784, 8662254974851091, 87570847718549791, 1147293660298060507, 66175019781864421220, 1378758199197350367079

Offset: 1

Chad Brewbaker, Feb 14 2011

Given an subgroup g of S(n) that is unknown and an oracle which takes as input a permutation on n elements, and returns true IFF the permutation is a member of the subgroup; a(n) is the minimum number of permutations that need to be queried to prove g consists of only the identity permutation.
a(n) is the size of a minimum dominating set in the permutation detection graph G(n) with loops removed. Let G(n) have n! vertices, each labeled with unique permutation from S(n). There is a directed edge from i->j IFF the permutation label on vertex j is in the group generated by the single permutation designated by the label on i.
a(n) is an exact bound on the worst case complexity of nontrivial automorphism detection for a generic combinatorial object on n elements. For tractable problem sizes this can yield significant savings over the brute force testing of all n!-1 nontrivial permutations. [Chad Brewbaker]
Number of cyclic subgroups of prime order in the symmetric group. [Olivier Gérard, Apr 03 2012]

			a(2): (0,1).
a(3): (1,2), (0,1), (0,1,2), (0,2).

Alois P. Heinz, Table of n, a(n) for n = 1..452
Chad Brewbaker, The exact classical query complexity of the hidden subgroup detection problem, (2008)

Cf. A181949, A181951.

with(numtheory):
a:= n-> n! *add(add(1/(p^i *i! *(n-i*p)! *(p-1)),
            i=1..floor(n/p)), p={ithprime(k) $k=1..pi(n)}):
seq(a(n), n=1..25);  # Alois P. Heinz, Apr 07 2011

a[n_] := n!*Sum[ 1/(p^i*i!*(n-i*p)!*(p-1)), {p, Prime /@ Range[ PrimePi[n] ] }, {i, 1, Floor[n/p]}]; Table[a[n], {n, 1, 24}] (* Jean-François Alcover, Aug 20 2013, after Alois P. Heinz *)

a(n)={sum(p=2, n, if(isprime(p), sum(k=1, n\p, n!/(k!*(n-k*p)!*p^k))/(p-1)))} \\ Andrew Howroyd, Jul 04 2018

a(n) = n! * Sum_{p|p prime, p<=n}

Sum_{i=1..floor(n/p)} 1 /(p^i*i!*(n-i*p)!*(p-1)).

A181955 Weighted sum of all cyclic subgroups of prime order in the Alternating group.

Original entry on oeis.org

0, 0, 3, 18, 90, 390, 2205, 10878, 45318, 256350, 5530305, 55869330, 865551258, 9892489698, 78223384785, 470010394350, 24530527675230, 409760923017198, 10595007772540113, 160826214447439770, 1585844008081570650, 16787211082925012730, 1362379219330719093273

Offset: 1

Olivier Gérard, Apr 03 2012

nonn

Sum of p for all p-subgroups in Alt_n.

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A181951 (number of such subgroups).
Cf. A181954 (symmetric case).
Cf. A001465.

a(n)={sum(p=2, n, if(isprime(p), sum(k=1, n\p, if(p>2||k%2==0, n!/(k!*(n-k*p)!*p^k)))*p/(p-1)))} \\ Andrew Howroyd, Jul 03 2018

a(n) = A181954(n) - 2*A001465(n). - Andrew Howroyd, Jul 03 2018

Terms a(9) and beyond from Andrew Howroyd, Jul 03 2018

A181967 Sum of the sizes of the normalizers of all prime order cyclic subgroups of the alternating group A_n.

Original entry on oeis.org

0, 0, 3, 24, 180, 1440, 12600, 120960, 1270080, 14515200, 179625600, 2634508800, 37362124800, 566658892800, 9807557760000, 167382319104000, 3023343138816000, 57621363351552000, 1155628453883904000, 25545471085854720000, 587545834974658560000, 13488008733331292160000

Offset: 1

Olivier Gérard, Apr 04 2012

nonn

The first 11 terms of this sequence are the same as A317527. - Andrew Howroyd, Jul 30 2018

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A181951 for the number of such subgroups.
Cf. A181966 is the symmetric group case.
Cf. A013939, A317527.

List([1..7], n->Sum(Filtered( ConjugacyClassesSubgroups( AlternatingGroup(n)), x->IsPrime( Size( Representative(x))) ), x->Size(x)*Size( Normalizer( AlternatingGroup(n), Representative(x))) )); # Andrew Howroyd, Jul 30 2018

a:=function(n) local total, perm, g, p, k;
  total:= 0; g:= AlternatingGroup(n);
  for p in Filtered([2..n], IsPrime) do for k in [1..QuoInt(n,p)] do
     if p>2 or IsEvenInt(k) then
       perm:=PermList(List([0..p*k-1], i->i - (i mod p) + ((i + 1) mod p) + 1));
       total:=total + Size(Normalizer(g, perm)) * Factorial(n) / (p^k * (p-1) * Factorial(k) * Factorial(n-k*p));
     fi;
  od; od;
  return total;
end; # Andrew Howroyd, Jul 30 2018

a(n)={n!*sum(p=2, n, if(isprime(p), if(p==2, n\4, n\p)))/2} \\ Andrew Howroyd, Jul 30 2018

a(n) = n! * (A013939(n) - floor((n + 2)/4)) / 2. - Andrew Howroyd, Jul 30 2018

Some incorrect conjectures removed by Andrew Howroyd, Jul 30 2018

Terms a(9) and beyond from Andrew Howroyd, Jul 30 2018

cp's OEIS Frontend

A186202 The maximal set of disjoint prime cycle permutations on n elements which generate unique subgroups of S(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A181955 Weighted sum of all cyclic subgroups of prime order in the Alternating group.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A181967 Sum of the sizes of the normalizers of all prime order cyclic subgroups of the alternating group A_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

GAP

PARI

Formula

Extensions