cp's OEIS Frontend

A378163 Triangle read by rows: T(n,k) is the number of subgroups of S_n isomorphic to S_k, where S_n is the n-th symmetric group.

%I A378163 #29 Nov 29 2024 23:50:57
%S A378163 1,1,1,1,3,1,1,9,4,1,1,25,20,5,1,1,75,160,60,12,1,1,231,910,560,84,7,
%T A378163 1,1,763,5936,5740,560,56,8,1,1,2619,53424,58716,3276,336,72,9,1,1,
%U A378163 9495,397440,734160,79632,4620,480,90,10,1,1,35695,3304620,8337120,1105104,39732,3300,660,110,11,1,1,140151,35023120,133212420,16571808,1400784,20592,4950,880,132,12,1,1,568503,322852816,1769490580,176344740,16253952,130416,33462,7150,1144,156,13,1
%N A378163 Triangle read by rows: T(n,k) is the number of subgroups of S_n isomorphic to S_k, where S_n is the n-th symmetric group.
%C A378163 The number of monomorphisms (i.e., injective homomorphisms) S_k -> S_n is thus |Aut(S_k)|*T(n,k). Note that |Aut(S_k)| = 1 for k = 2, 1440 for k = 6 and k! otherwise.
%C A378163 T(n,k) is related to the number of homomorphisms S_k -> S_n:
%C A378163      k     | trivial kernel | kernel S_k (k>=2) | kernel A_k (k>=3) | kernel V (k=4) |       total number
%C A378163 -----------+----------------+-------------------+-------------------+----------------+-------------------------
%C A378163      1     |        1       |         -         |         -         |        -       |            1
%C A378163 -----------+----------------+-------------------+-------------------+----------------+-------------------------
%C A378163      2     |     b(n)-1     |         1         |         -         |        -       |           b(n)
%C A378163 -----------+----------------+-------------------+-------------------+----------------+-------------------------
%C A378163      4     |    24*T(n,4)   |         1         |       b(n)-1      |    6*T(n,3)    | 24*T(n,4)+6*T(n,3)+b(n)
%C A378163 -----------+----------------+-------------------+-------------------+----------------+-------------------------
%C A378163      6     |   1440*T(n,6)  |         1         |       b(n)-1      |         -      |     1440*T(n,6)+b(n)
%C A378163 -----------+----------------+-------------------+-------------------+----------------+-------------------------
%C A378163  3, 5, >=7 |    k!*T(n,k)   |         1         |       b(n)-1      |         -      |      k!*T(n,k)+b(n)
%C A378163 Here A_n is the n-th alternating group, V = {e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)} is the Klein-four group in S_4, b = A000085, and T(n,k) = 0 for k > n.
%C A378163 In particular, the number of homomorphisms S_n -> S_n is 1 for n = 1, 2 for n = 2, 58 for n = 4, 1440 + b(6) = 1516 for n = 6, and n! + b(n) otherwise.
%H A378163 Mathematics Stack Exchange, <a href="https://math.stackexchange.com/questions/2339571/subgroups-in-gap">Subgroups in GAP</a>
%F A378163 T(n,2) = A001189(n).
%e A378163 Table reads
%e A378163   1
%e A378163   1, 1
%e A378163   1, 3, 1
%e A378163   1, 9, 4, 1
%e A378163   1, 25, 20, 5, 1
%e A378163   1, 75, 160, 60, 12, 1
%e A378163   1, 231, 910, 560, 84, 7, 1
%e A378163   1, 763, 5936, 5740, 560, 56, 8, 1
%e A378163   1, 2619, 53424, 58716, 3276, 336, 72, 9, 1
%e A378163   1, 9495, 397440, 734160, 79632, 4620, 480, 90, 10, 1
%o A378163 (GAP) A378163 := function(n,k)
%o A378163 local S;
%o A378163 S := SymmetricGroup(n);
%o A378163 return Sum(IsomorphicSubgroups(S,SymmetricGroup(k)),x->Index(S,Normalizer(S,Image(x))));
%o A378163 end; # program given in the Math Stack Exchange link
%o A378163 (GAP) A378163_row_n := function(n)
%o A378163 local L, C, G, N, k;
%o A378163 N := ListWithIdenticalEntries( n, 0 );
%o A378163 L := ConjugacyClassesSubgroups( SymmetricGroup(n) );
%o A378163 for C in L do
%o A378163 G := Representative(C);
%o A378163 for k in [1..n] do
%o A378163 if not IsomorphismGroups( G, SymmetricGroup(k) ) = fail then
%o A378163 N[k] := N[k]+Size(C);
%o A378163 fi;
%o A378163 od;
%o A378163 od;
%o A378163 return N;
%o A378163 end;
%Y A378163 Cf. A000085, A001189, A378279, A378280, A378281, A281097.
%K A378163 nonn,tabl,hard
%O A378163 1,5
%A A378163 _Jianing Song_, Nov 18 2024