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

 

Logo

Annual Appeal: Today, Nov 11 2014, is the 4th anniversary of the launch of the new OEIS web site. 70,000 sequences have been added in these four years, all edited by volunteers. Please make a donation (tax deductible in the US) to help keep the OEIS running.

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 A109454 A000640

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

Content is available under The OEIS End-User License Agreement .

Last modified December 18 15:59 EST 2014. Contains 252163 sequences.