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

Author

Chad Brewbaker, Feb 14 2011

Keywords

• nonn
• nice

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]

Examples

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

Links

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

Crossrefs

Cf. A181949, A181951.

Programs

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

PARI

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

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