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,5

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.

Links

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

Mathematics Stack Exchange, Subgroups in GAP

Formula

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

Example

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

Prog

(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;

Crossrefs

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

Sequence in context: A100537 A069605 A080510 * A350772 A350783 A124496

Adjacent sequences: A378160 A378161 A378162 * A378164 A378165 A378166

Keyword

nonn,tabl,hard,changed

Author

Jianing Song, Nov 18 2024

Status

approved