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.

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, 1, 1, 763, 5936, 5740, 560, 56, 8, 1, 1, 2619, 53424, 58716, 3276, 336, 72, 9, 1, 1, 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

Offset: 1

Author

Jianing Song, Nov 18 2024

Keywords

• nonn
• tabl
• hard

Comments

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.

T(n,k) is related to the number of homomorphisms S_k -> S_n:

k | trivial kernel | kernel S_k (k>=2) | kernel A_k (k>=3) | kernel V (k=4) | total number

-----------+----------------+-------------------+-------------------+----------------+-------------------------

1 | 1 | - | - | - | 1

-----------+----------------+-------------------+-------------------+----------------+-------------------------

2 | b(n)-1 | 1 | - | - | b(n)

-----------+----------------+-------------------+-------------------+----------------+-------------------------

4 | 24*T(n,4) | 1 | b(n)-1 | 6*T(n,3) | 24*T(n,4)+6*T(n,3)+b(n)

-----------+----------------+-------------------+-------------------+----------------+-------------------------

6 | 1440*T(n,6) | 1 | b(n)-1 | - | 1440*T(n,6)+b(n)

-----------+----------------+-------------------+-------------------+----------------+-------------------------

3, 5, >=7 | k!*T(n,k) | 1 | b(n)-1 | - | k!*T(n,k)+b(n)

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.

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.

Examples

			Table reads
  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, 1
  1, 763, 5936, 5740, 560, 56, 8, 1
  1, 2619, 53424, 58716, 3276, 336, 72, 9, 1
  1, 9495, 397440, 734160, 79632, 4620, 480, 90, 10, 1
		

Links

• Mathematics Stack Exchange, Subgroups in GAP

Crossrefs

Cf. A000085, A001189, A378279, A378280, A378281, A281097.

Programs

GAP

A378163 := function(n,k)
local S;
S := SymmetricGroup(n);
return Sum(IsomorphicSubgroups(S,SymmetricGroup(k)),x->Index(S,Normalizer(S,Image(x))));
end; # program given in the Math Stack Exchange link

GAP

A378163_row_n := function(n)
local L, C, G, N, k;
N := ListWithIdenticalEntries( n, 0 );
L := ConjugacyClassesSubgroups( SymmetricGroup(n) );
for C in L do
G := Representative(C);
for k in [1..n] do
if not IsomorphismGroups( G, SymmetricGroup(k) ) = fail then
N[k] := N[k]+Size(C);
fi;
od;
od;
return N;
end;

Formula

T(n,2) = A001189(n).