A337015 Number of distinct transitive subgroups of S_n, counting conjugates as distinct.

1, 1, 2, 9, 20, 279, 512, 19087, 71602, 636365, 1517042, 321965982, 240609602, 8809543877, 144729615032, 26818608209252, 6603755558402, 2737593592637477

Offset

1,3

Comments

This sequence is the labeled version of A002106. I have proven that A005432(p)-a(p) == 1 (mod p) if p is prime. Based on n<= 18,

I have conjectured that log(A005432(n)/a(n)) > (n-1)/2 for n prime and log(A005432(n)/a(n)) < (n-1)/2 for n composite.

L. Pyber shows c^{n^2(1+o(1))} <= a(n) <= d^{n^2(1+o(1)}, c=2^{1/16}, d=24^{1/6}; conjectures lower bound is accurate.

Links

Table of n, a(n) for n=1..18.

John Erickson, COUNTING TRANSITIVE SUBGROUPS OF Sn

L. Pyber, Enumerating Finite Groups of Given Order, Ann. Math. 137 (1993), 203-220.

Example

For n = 4 the following 9 subgroups of S_4 are transitive:
Group( [ (1,4)(2,3), (1,3)(2,4) ] )
Group( [ (1,3,2,4), (1,2)(3,4) ] )
Group( [ (1,4,3,2), (1,3)(2,4) ] )
Group( [ (1,2,4,3), (1,4)(2,3) ] )
Group( [ (1,4)(2,3), (1,3)(2,4), (3,4) ] )
Group( [ (1,2)(3,4), (1,3)(2,4), (1,4) ] )
Group( [ (1,2)(3,4), (1,4)(2,3), (2,4) ] )
Group( [ (1,4)(2,3), (1,3)(2,4), (2,4,3) ] )
Group( [ (1,4)(2,3), (1,3)(2,4), (2,4,3), (3,4) ] )

Prog

(GAP)
NrTransSubSn:=function(n)
local s, cnt, i, u, no;
  s:=SymmetricGroup(n);
  cnt:=0;
  for i in [1..NrTransitiveGroups(n)] do
    u:=TransitiveGroup(n, i);
    no:=Normalizer(s, u);
    cnt:=cnt+IndexNC(s, no);
    Print("Class ", i, ", found ", IndexNC(s, no), " new, total: ", cnt, "\n");
  od;
  return cnt;
end; # Alexander Hulpke

Crossrefs

Cf. A005432, A002106.

Sequence in context: A041007 A002360 A100516 * A041285 A002888 A041963

Adjacent sequences: A337012 A337013 A337014 * A337016 A337017 A337018

Keyword

nonn,more

Author

John Erickson and Alexander Hulpke, Nov 21 2020

Status

approved