This site is supported by donations to The OEIS Foundation.



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

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



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]


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)


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

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


a(2): (0,1).

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



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


Cf. A181949, A181951.

Sequence in context: A005002 A085507 A121654 * A036366 A255836 A109454

Adjacent sequences:  A186199 A186200 A186201 * A186203 A186204 A186205




Chad Brewbaker, Feb 14 2011



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 November 29 10:31 EST 2015. Contains 264643 sequences.