login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A186202 The maximal set of disjoint prime cycle permutations on n elements which generate unique subgroups of S(n). 4
0, 1, 4, 13, 41, 151, 652, 2675, 10579, 59071, 711536, 6180307, 76629775, 873676259, 7496233396, 49493077951, 1571673343007, 24729597043375, 584039297226784, 8662254974851091, 87570847718549791, 1147293660298060507, 66175019781864421220, 1378758199197350367079 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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]

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..200

Chad Brewbaker, The exact classical query complexity of the hidden subgroup detection problem, (2008)

FORMULA

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

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

EXAMPLE

a(2): (0,1).

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

MAPLE

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

MATHEMATICA

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 *)

CROSSREFS

Cf. A181949, A181951.

Sequence in context: A005002 A085507 A121654 * A036366 A255836 A109454

Adjacent sequences:  A186199 A186200 A186201 * A186203 A186204 A186205

KEYWORD

nonn,nice

AUTHOR

Chad Brewbaker, Feb 14 2011

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 4 21:33 EST 2016. Contains 278755 sequences.