login
Number of distinct transitive subgroups of S_n, counting conjugates as distinct.
1

%I #64 Dec 15 2020 00:00:26

%S 1,1,2,9,20,279,512,19087,71602,636365,1517042,321965982,240609602,

%T 8809543877,144729615032,26818608209252,6603755558402,2737593592637477

%N Number of distinct transitive subgroups of S_n, counting conjugates as distinct.

%C 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,

%C 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.

%C 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.

%H John Erickson, <a href="/A337015/a337015_3.pdf">COUNTING TRANSITIVE SUBGROUPS OF Sn</a>

%H L. Pyber, <a href="https://www.jstor.org/stable/2946623">Enumerating Finite Groups of Given Order</a>, Ann. Math. 137 (1993), 203-220.

%e For n = 4 the following 9 subgroups of S_4 are transitive:

%e Group( [ (1,4)(2,3), (1,3)(2,4) ] )

%e Group( [ (1,3,2,4), (1,2)(3,4) ] )

%e Group( [ (1,4,3,2), (1,3)(2,4) ] )

%e Group( [ (1,2,4,3), (1,4)(2,3) ] )

%e Group( [ (1,4)(2,3), (1,3)(2,4), (3,4) ] )

%e Group( [ (1,2)(3,4), (1,3)(2,4), (1,4) ] )

%e Group( [ (1,2)(3,4), (1,4)(2,3), (2,4) ] )

%e Group( [ (1,4)(2,3), (1,3)(2,4), (2,4,3) ] )

%e Group( [ (1,4)(2,3), (1,3)(2,4), (2,4,3), (3,4) ] )

%o (GAP)

%o NrTransSubSn:=function(n)

%o local s,cnt,i,u,no;

%o s:=SymmetricGroup(n);

%o cnt:=0;

%o for i in [1..NrTransitiveGroups(n)] do

%o u:=TransitiveGroup(n,i);

%o no:=Normalizer(s,u);

%o cnt:=cnt+IndexNC(s,no);

%o Print("Class ",i,", found ",IndexNC(s,no)," new, total: ",cnt,"\n");

%o od;

%o return cnt;

%o end; # Alexander Hulpke

%Y Cf. A005432, A002106.

%K nonn,more

%O 1,3

%A _John Erickson_ and _Alexander Hulpke_, Nov 21 2020