Integer Sequences Realized by the Subgroup Pattern of the Symmetric Group

L. Naughton and G. Pfeiffer School of Mathematics Applied Mathematics and Statistics National University of Ireland Galway Ireland

                  liam.naughton@nuigalway.ie

Abstract The subgroup pattern of a finite group G is the table of marks of G together with a list of representatives of the conjugacy classes of subgroups of G. In this article we describe a collection of sequences realized by the subgroup pattern of the symmetric group.

1 Introduction

The table of marks of a finite group G was introduced by Burnside [2]. It is a matrix whose rows and columns are indexed by a list of representatives of the conjugacy classes of subgroups of G, where, for two subgroups H, K ≤ G the (H, K) entry in the table of marks of G is the number of fixed points of K in the transitive action of G on the cosets of H, (β_{G/H}(K)). If H_{1}, …, H_{r} is a list of representatives of the conjugacy classes of subgroups of G, the table of marks is then the (r × r)-matrix

M(G) = (β_{G/H_{i}}(H_{j}))_{i,j=1.,...,r}.

In much the same fashion as the character table of G classifies matrix representations of G up to isomorphism, the table of marks of G classifies permutation representations of G up to equivalence. It also encodes a wealth of information about the subgroup lattice of G in a compact way. The GAP [4] library of tables of marks Tomlib [11] provides ready access to the tables of marks and conjugacy classes of subgroups of some 400 groups. These tables have been produced using the methods described in [8] and [7]. The data exhibited in later sections has been computed using this library. The purpose of this article is to illustrate how interesting integer sequences related to the subgroup structure of the symmetric group S_{n}, and the alternating group A_{n}, can be computed from this data. This paper is organized as follows. In Section 2 we study the conjugacy classes of subgroups of S_{n} for n ≤ 13. In Section 3 we examine the tables of marks of S_{n} for n ≤ 13 and describe how much more information regarding the subgroup structure of S_{n} can be obtained. In Section 4 we discuss the Euler Transform and its applications in counting subgroups of S_{n}.

2 Counting subgroups

Given a list of representatives {H_{1}, …, H_{r}} of Sub(G)/G, the conjugacy classes of subgroups of G, we can enumerate those subgroups which satisfy particular properties. The numbers of conjugacy classes of subgroups of S_{n} and A_{n} are sequences \underline{A000638} and \underline{A029726} respectively in Sloane’s encyclopedia [9]. The GAP table of marks library Tomlib provides access to the conjugacy classes of subgroups of the symmetric and alternating groups for n ≤ 13. Table 1 records the number of conjugacy classes of subgroups of S_{n} which are abelian, cyclic, nilpotent, solvable and supersolvable (SupSol). A similar table for the conjugacy classes of subgroups of the alternating groups can be found in Appendix A.

\underline{A000638}  \underline{A218909}  \underline{A000041}  \underline{A218910}  \underline{A218911}  \underline{A218912}
n  |Sub(S_{n})/S_{n}|  Abelian  Cyclic  Nilpotent  Solvable  SupSol
1  1  1  1  1  1  1
2  2  2  2  2  2  2
3  4  3  3  3  4  4
4  11  7  5  8  11  9
5  19  9  7  10  17  15
6  56  20  11  25  50  38
7  96  26  15  32  84  65
8  296  61  22  127  268  187
9  554  82  30  156  485  341
10  1593  180  42  531  1418  923
11  3094  236  56  648  2691  1789
12  10723  594  77  3727  9725  6118
13  20832  762  101  4221  18286  11616

Table 1: Sequences in S_{n}

2.1 Subgroup Orders

A question of historical interest concerns the orders of subgroups of S_{n}. In [3] Cameron writes: The Grand Prix question of the Academie des Sciences, Paris, in 1860 asked “How many distinct values can a function of n variables take?” In other words what are the possible indices of subgroups of S_{n}. For n ≤ 13, Table 2 records the numbers of different orders O(S_{n}), O(A_{n}) of subgroups of S_{n} and A_{n}. One might as well also enumerate the number of “missing” subgroup orders, that is, the number, d(S_{n}), of divisors d such that d | |S_{n}| but S_{n} has no subgroup of order d. Table 3 records the number of missing subgroup orders of S_{n} and A_{n} for n ≤ 13.

\underline{A218913} \underline{A218914}
n  O(S_{n}) O(A_{n})
1  1  1
2  2  1
3  4  2
4  8  5
5  13  9
6  21  15
7  31  22
8  49  38
9  74  59
10  113  89
11  139  115
12  216  180
13  268  226

Table 2: Subgroup Orders

\underline{A218915} \underline{A218916}
n  d(S_{n})  d(A_{n})
1  0  0
2  0  0
3  0  0
4  0  1
5  3  3
6  9  9
7  29  26
8  47  46
9  86  81
10  157  151
11  401  365
12  576  540
13  1316  1214

Table 3: Missing Subgroup Orders

3 Counting using the table of marks

If in addition to a list of conjugacy classes of subgroups of G, the table of marks of G is also available, or can be computed, one can say quite a lot about the structure of the lattice of subgroups of G. We begin this section by giving some basic information about tables of marks and then go on to describe how we can count incidences and edges in the lattice of subgroups.

3.1 About Tables of Marks

Let G be a finite group and let Sub(G) denote the set of subgroups of G. By Sub(G)/G we denote the set of conjugacy classes of subgroups of G. For H, K ∈ Sub(G) let

β_{G/H}(K) = #{Hg ∈ G/H : (Hg)k = Hg for all k ∈ K} = #{g ∈ G : K ≤ H^{g}}/|H|

denote the mark of K on H. This number depends only on the G-conjugacy classes of H and K. Note that β_{G/H}(K) ≠ 0 ⇒ |K| ≤ |H|. If H_{1}, …, H_{r} is a list of representatives of the conjugacy classes of subgroups of G, the table of marks of G is then the (r × r)-matrix

M(G) = (β_{G/H_{i}}(H_{j}))_{i,j=1,...,r}.

If the subgroups in the transversal are listed by increasing group order the table of marks is a lower triangular matrix. The table of marks M(S_{4}) of the symmetric group S_{4} is shown in Figure 1.

S_{4}/1 24
S_{4}/2 12 4
S_{4}/2 12 . 2
S_{4}/3 8 . . 2
S_{4}/2^{2} 6 6 . . 6
S_{4}/2^{2} 6 2 2 . . 2
S_{4}/4 6 2 …. 2
S_{4}/S_{3} 4 . 2 1 … 1
S_{4}/D_{8} 3 3 1 . 3 1 1 . 1
S_{4}/A_{4} 2 2 . 2 2 …. 2
S_{4}/S_{4} 1 1 1 1 1 1 1 1 1 1 1
1 2 2 3 2^{2} 2^{2} 4 S_{3} D_{8} A_{4} S_{4}

Figure 1: Table of Marks M(S_{4})

As a matrix, we can extract a variety of sequences from the table of marks, the most obvious of which is the sum of the entries. The sum of the entries of M(S_{n}) for n ≤ 13 is shown in Figure 4. We can also sum the entries on the diagonal to obtain the sequences in Figure 5.

\underline{A218917}  \underline{A218918}
n S_{n}  A_{n}
1 1  1
2 4  1
3 18  5
4 146  39
5 681  192
6 7518  1717
7 58633  13946
8 952826  243391
9 11168496  2693043
10 232255571  38343715
11 3476965896  545787051
12 108673489373 15787210045
13 1951392769558 268796141406

Table 4: Sum of M(G)

\underline{A218919}  \underline{A218920}
n S_{n}  A_{n}
1 1  1
2 3  1
3 10  4
4 47  19
5 165  73
6 950  412
7 5632  2660
8 43772  21449
9 376586  184541
10 3717663  1827841
11 40555909 20043736
12 484838080 240206213
13 6286289685 3119816216

Table 5: Sum of the Diagonal

We will now collect some elementary properties of tables of marks in Lemma 1. Lemma 1. Let H, K ≤ G. Then the following hold:

(i) The first entry of every row of M(G) is the index of the corresponding subgroup, β_{G/H}(1) = |G : H|.

(ii) The entry on the diagonal is,

β_{G/H}(H) = |N_{G}(H) : H|.

(iii) The length of the conjugacy class [H] of H is given by,

|[H]| = |G : N_{G}(H)| = \frac{β_{G/H}(1)}{β_{G/H}(H)}.

(iv) The number of conjugates of H which contain K is given by,

|\{H^{a} : a ∈ G, K ≤ H^{a}\}| = \frac{β_{G/H}(K)}{β_{G/H}(H)}.

The following formula which follows trivially from Lemma 1 (iv) relates marks to incidences in the subgroup lattice of G.

β_{G/H}(K) = |N_{G}(H) : H| · #{H^{g} : K ≤ H^{g}, g ∈ G}.  (1)

As a first application of Formula 1 we obtain the following lemma which enables us to count the total number of subgroups of G.

Lemma 2. Given a list {H_{1}, …, H_{r}} of representatives of the conjugacy classes of subgroups of G, the total number of subgroups of G is

|Sub(G)| = ∑_{i=1}^{r} \frac{β_{G/H_{i}}(1)}{β_{G/H_{i}}(H_{i})}.

Proof. It follows from Formula 1 that for any subgroup H ≤ G, \frac{β_{G/H}(1)}{β_{G/H}(H)} is the length of the conjugacy class of H in G.

Table 6 lists the total number of subgroups of S_{n} and A_{n} for n ≤ 13.

\underline{A029725}  \underline{A005432}
n A_{n}  S_{n}
1 1  1
2 1  2
3 2  6
4 10  30
5 59  156
6 501  1455
7 3786  11300
8 48337  151221
9 508402  1694723
10 6469142  29594446
11 81711572  404126228
12 2019160542 10594925360
13 31945830446 175238308453

Table 6: Total Number of Subgroups of A_{n} and S_{n}

3.2 Counting Incidences

Another immediate consequence of Formula 1 is that by dividing each row of the table of marks of G by its diagonal entry β_{G/H}(H) we obtain a matrix C(G) describing containments in the subgroup lattice of G, where the (H, K)-entry is

C(H, K) = #{K^{g} : H ≤ K^{g}, g ∈ G}.  (2)

Figure 2 illustrates the containment matrix of the symmetric group S_{4}.

1 1
2 3 1
2 6 . 1
3 4 . . 1
2^{2} 1 1 . . 1
2^{2} 3 1 1 . . 1
4 3 1 …. 1
S_{3} 4 . 2 1 … 1
D_{8} 3 3 1 . 3 1 1 . 1
A_{4} 1 1 . 1 1 …. 1
S_{4} 1 1 1 1 1 1 1 1 1 1 1
1 2 2 3 2^{2} 2^{2} 4 S_{3} D_{8} A_{4} S_{4}

Figure 2: Containment Matrix : C(S_{4})

The conjugacy classes of subgroups of G are partially ordered by [H] ≤ [K] if H ≤ K^{g} for some g ∈ G i.e. if C(H, K) ≠ 0. Therefore we can easily obtain the incidence matrix, I(G), of the poset of conjugacy classes of subgroups of G by replacing each nonzero entry in C(G), (or M(G) ) by an entry 1. Figure 3 shows the incidence matrix I(S_{4}) of the poset of conjugacy classes of subgroups of S_{4}.

1 1
2 1 1
2 1 . 1
3 1 . . 1
2^{2} 1 1 . . 1
2^{2} 1 1 1 . . 1
4 1 1 …. 1
S_{3} 1 . 1 1 … 1
D_{8} 1 1 1 . 1 1 1 . 1
A_{4} 1 1 . 1 1 …. 1
S_{4} 1 1 1 1 1 1 1 1 1 1 1
1 2 2 3 2^{2} 2^{2} 4 S_{3} D_{8} A_{4} S_{4}

Figure 3: Incidence Matrix : I(S_{4})

For comparison with Figure 3 we illustrate the poset of conjugacy classes of subgroups of S_{4} in Figure 4.

12232^{2} 2^{2} 4S_{3} D_{8} A_{4} S_{4}

Figure 4: Poset of Conjugacy Classes of Subgroups of S_{4}

Lemma 3. The number of incidences in the poset of conjugacy classes of subgroups of G is given by

∑ I(G).

Proof. The incidence matrix I(G) is obtained by replacing every nonzero entry in the table of marks by an entry 1. By Formula 1 I(H, K) = 1 if and only if K is subconjugate to H in G, i.e. if and only if H and K are incident in the poset of conjugacy classes of subgroups of G.

Table 7 lists the number of incidences in the poset of conjugacy classes of subgroups of A_{n} and S_{n} for n ≤ 13.

Lemma 4. The total number of incidences in the entire subgroup lattice of G is given by

∑ C(G).

Proof. For H, K ∈ Sub(G)/G the H, K entry in C(G) is the number of incidences between H, K in the subgroup lattice of G. Thus summing over the entries in C(G) yields the total number of incidences in the entire subgroup lattice of G.

Table 8 records the number of incidences in the subgroup lattices of S_{n} and A_{n} for n ≤ 13.

\underline{A218921} \underline{A218922}
n S_{n}  A_{n}
1 1  1
2 3  1
3 9  3
4 44  13
5 101  32
6 523  128
7 1195  330
8 6751  2309
9 16986  4271
10 87884  12468
11 248635 33329
12 1709781 196182
13 4665651 490137

Table 7: Incidences in Poset

\underline{A218924}  \underline{A218923}
n A_{n}  S_{n}
1 1  1
2 1  3
3 3  11
4 18  68
5 85  262
6 657  2261
7 4374  14032
8 55711  176245
9 530502  1821103
10 6603007  30883491
11 82736601  415843982
12 2032940127 10779423937
13 32102236563 177718085432

Table 8: Incidences in Subgroup Lattice

3.3 Counting Edges in Hasse Diagrams

The table of marks also allows us to count the number of edges in both the Hasse diagrams of the poset of conjugacy classes of subgroups and the subgroup lattice of G. Computing such data requires careful analysis of maximal subgroups in the subgroup lattice.

Formula 1 describes containments in the poset of conjugacy classes of subgroups looking upward through the subgroup lattice of G. But we can also view marks as containments looking downward through the subgroup lattice of G.

Lemma 5. Let H, K ∈ Sub(G)/G. Then the number of conjugates of H contained in K is given by

E^{↑}(H, K) = |\{H^{g}, g ∈ G : H^{g} ≤ K\}| = \frac{β_{G/K}(H)β_{G/H}(1)}{β_{G/H}(H)β_{G/K}(1)}

Proof. The total number of edges between the classes [H]_{G} and [K]_{G} can be counted in two different ways, as the length of the class times the number of edges leaving one member of the class. Thus

|[H_{G}| · |{H^{g}, g ∈ G : H^{g} ≤ K}| = |[K]_{G}| · |{K^{g}, g ∈ G : K^{g} ≥ H}|.

By Formula 1 |[H]_{G}| = \frac{β_{G/H}(1)}{β_{G/H}(H)} and |[K]_{G}| = \frac{β_{G/K}(1)}{β_{G/K}(K)}. Thus E^{↑}(H, K) can be expressed in terms of marks.

3.3.1 Identifying Maximal Subgroups

It will be necessary, for the sections that follow, to identify for H_{i} ∈ Sub(G)/G which classes H_{j} ∈ Sub(G)/G are maximal in H_{i}.

Lemma 6. Let H_{i} ∈ Sub(G)/G = {H_{1}, …, H_{r}}. Denote by ρ_{i} = {j : H_{j} <_{G} H_{i}} the set of indices in {1, …, r} of proper subgroups of H_{i} up to conjugacy in G. Then the positions of all maximal subgroups of H_{i} are given by

Max(H_{i}) = ρ_{i} \ ⋃_{j∈ρ_{i}} ρ_{j}  (3)

The set of values ρ_{i} are easily read off the table of marks of G by simply identifying the nonzero entries in the row corresponding to G/H_{i}. Formula 3 is implemented in GAP via the

function MaximalSubgroupsTom.

Lemma 7. Let Sub(G)/G = {H_{1}, …, H_{r}} be a list of representatives of the conjugacy classes of subgroups of G. The number of edges in the Hasse diagram of the poset of conjugacy classes of subgroups of G is given by

|E(Sub(G)/G)| = ∑_{i=1}^{r} |Max(H_{i})|.

Proof. By Lemma 6, Max(H_{i}) is a list of the positions of the maximal subgroups of H_{i} up to conjugacy in G. In the Hasse diagram of the poset Sub(G)/G each edge corresponds to a maximal subgroup.

Table 9 records the number of edges in the Hasse diagram of the poset of conjugacy classes of subgroups of S_{n} and A_{n} for n ≤ 13. In order to count the number of edges in the Hasse diagram of the entire subgroup lattice of G we appeal to Formula 1 and Lemma 5.

Lemma 8. Let Sub(G)/G = {H_{1}, …, H_{r}} be as above. The total number of edges E(L(G)) in the Hasse diagram of the subgroup lattice of G is given by

E(L(G)) = ∑_{i=1}^{r} ∑_{j∈Max(H_{i})} E^{↑}(H_{i}, H_{j}).

Proof. By restricting E^{↑}(H_{i}, H_{j}) to those classes H_{i}, H_{j} which are maximal we obtain the number of edges connecting maximal subgroups of G.

Table 10 records the total number of edges in the Hasse diagram of the subgroup lattice of S_{n} and A_{n} for n ≤ 13.

\underline{A218925} \underline{A218926}
n S_{n}  A_{n}
1 0  0
2 1  0
3 4  1
4 17  5
5 37  13
6 149  44
7 290  98
8 1080  419
9 2267  722
10 8023  1592
11 17249  3304
12 72390  12645
13 153419 24792

Table 9: Edges in Poset

\underline{A218928}  \underline{A218927}
n A_{n}  S_{n}
1 0  0
2 0  1
3 1  8
4 15  66
5 168  501
6 2051  6469
7 19305  60428
8 283258  926743
9 3255913  11902600
10 46464854  240066343
11 670282962  3677270225
12 18723796793 108748156239
13 321480817412 1980478458627

Table 10: Edges in Subgroup Lattice

3.4 Maximal Property-P Subgroups

For any property P which is inherited by subgroups of G we can use the table of marks of G to enumerate the maximal property P subgroups of G.

Lemma 9. Let Sub(G)/G = {H_{1}, …, H_{r}} and let ρ = {i ∈ [1, …, r] : H_{i} is a property P subgroup}. Then the positions of the maximal property P subgroups of G are given by

P (G) = ρ \ ⋃_{j∈ρ} Max(H_{j})  (4)

In Figure 5 the classes of maximal abelian subgroups of S_{4} are boxed.

1223 2^{2} 2^{2} 4 S_{3} D_{8} A_{4} S_{4}

Figure 5: Maximal Abelian Subgroups of S_{4}

Table 11 records, for each of the properties listed across the first row of the table, the numbers of maximal property P classes of subgroups of S_{n}. A similar table for the alternating groups can be found in the Appendix.

\underline{A218929} \underline{A218930} \underline{A218931} \underline{A218932} \underline{A218933}
n Solvable SupSol Abelian  Cyclic Nilpotent
1  1  1  1  1  1
2  1  1  1  1  1
3  1  1  2  2  2
4  1  2  4  3  2
5  3  3  5  3  3
6  4  4  7  5  5
7  5  5  10  6  6
8  6  6  17  11  7
9  9  8  23  15  9
10  12  11  30  20  12
11  14  14  41  24  15
12  17  19  61  34  20
13  24  23  80  43  25

Table 11: Maximal Property-P Subgroups of S_{n}

4 Connected subgroups and the Euler transform

The conjugacy classes of subgroups of the symmetric group play an important role in the theory of combinatorial species as described in [6]. Permutation groups have been used to answer many questions about species. Every species is the sum of its molecular subspecies. These molecular species correspond to conjugacy classes of subgroups of Sym(n). Molecular species decompose as products of atomic species which in turn correspond to connected subgroups of Sym(n) in the following sense. It will be convenient to denote the symmetric group on a finite set X by Sym(X).

Definition 10. For each H ≤ Sym(X) there is a finest partition of X = ⨆ Y_{i} such that H = ∏ H_{i} with H_{i} ≤ Sym(Y_{i}). We allow H_{i} = 1 when |Y_{i}| = 1. We say that H is a connected subgroup of Sym(X) if the finest partition is X.

Example 11. Let X = {1, 2, 3, 4} and consider H = ⟨(1, 2), (3, 4)⟩ and H′ = ⟨(1, 2)(3, 4)⟩. Partitioning X into Y_{1} = {1, 2}, Y_{2} = {3.4} gives H = H_{1} × H_{2} where H_{1} = ⟨(1, 2)⟩ ≤ Sym({1, 2}), H_{2} = ⟨(3, 4)⟩ ≤ Sym({3, 4}), hence H is not connected. On the other hand, H′ is connected since there is no finer partition of X which permits us to write H′ as a product of connected H_{i}.

An algorithm to test a group H acting on a set X for connectedness checks each non-trivial H-stable subset Y of X. If H is the direct product of its action on Y and its action on X \Y then H is not connected.

In general a subgroup H ≤ Sym(X) is a product of connected subgroups H_{i} ≤ Sym(Y_{i}). Sequence \underline{A000638} records the number of molecular species of degree n or equivalently the number of conjugacy classes of subgroups of Sym(n). Sequence \underline{A005226} records the number of atomic species of degree n or equivalently the number of conjugacy classes of connected subgroups of Sym(n). These sequences are related by the Euler Transform.

4.1 The Euler Transform

If two sequences of integers {c_{k}} = (c_{1}, c_{2}, c_{3}, …) and {m_{n}} = (m_{1}, m_{2}, m_{3}, …) are related by

1 + ∑_{n≥1} m_{n}x^{n} = ∏_{k≥1} (\frac{1}{1 − x^{k}} )^{c_{k}} .  (5)

Then we say that {m_{n}} is the Euler transform of {c_{k}} and that {c_{k}} is the inverse Euler transform of {m_{n}} (see [1]). One sequence can be computed from the other by introducing the intermediate sequence {b_{n}} defined by

b_{n} = ∑_{d|n} dc_{d} = nm_{n} − ∑_{k=1}^{n−1} b_{k}m_{n−k}.  (6)

Then

m_{n} = \frac{1}{n}(b_{n} + ∑_{k=1}^{n−1} b_{k}m_{n−k}),  c_{n} = \frac{1}{n} ∑_{d|n} μ(n/d)b_{d},  (7)

where μ is the number-theoretic Möbius function.

There are many applications of this pair of transforms (see [10]). For example, the inverse Euler transform applied to the sequence of numbers of unlabeled graphs on n nodes (\underline{A000088}) yields the sequence of numbers of connected graphs on n nodes (\underline{A001349}). To understand how Formula 5 can be used to count connected graphs we note that the coefficient of x^{n} in the expansion of the product on the right hand side of Formula 5 is

m_{n} = ∑_{1^{a_{1}},2^{a_{2}},...,n^{an}⊢n} ∏_{i} \begin{aligned}( \\ ( & {c_{i} \atop a_{i}} & ) \\ & ) \end{aligned}  (8)

where (\binom{c_{i}}{a_{i}}) denotes the number of a_{i}-element multisets chosen from a set of c_{i} objects. On the other hand, an unlabeled graph on n nodes, as a collection of connected components, can be characterized by a pair (λ, (C_{1}, …, C_{n})) where λ = 1^{a_{1}}, 2^{a_{2}}, …, n^{a_{n}} is a partition of n and C_{i} is a multiset of a_{i} connected unlabeled graphs on i nodes, for 1 ≤ i ≤ n. If c_{i} is the number of connected unlabeled graphs on i nodes then, by Formula 8, m_{n} is the total number of unlabeled graphs on n nodes.

In the same way, the inverse Euler transform of \underline{A000638} (the number of conjugacy classes of subgroups of S_{n}) is \underline{A005226}, (the number of connected conjugacy classes of subgroups of S_{n}) as formalized in the following Lemma.

Lemma 12. There is a bijection between the conjugacy classes of subgroups of S_{n} and the set of pairs of the form (λ, (C_{1}, …, C_{n})) where λ = 1^{a_{1}}, 2^{a_{2}}, …, n^{a_{n}} is a partition of n and C_{i} is a multiset of a_{i} conjugacy classes of connected subgroups of S_{i} for i = 1, …, n.

Proof. Given a representative H of the conjugacy class of subgroups [H] ∈ Sub(S_{n})/S_{n} we associate a pair (λ, (C_{1}, …, C_{n})) to H as follows. Write H = ∏ H_{k} where each H_{k} is a connected subgroup of Sym(Y_{k}). Then X = {1, …, n} = ⨆ Y_{k}. Recording the size of each Y_{k} yields a partition λ = 1^{a_{1}}, 2^{a_{2}}, …, n^{a_{n}}. For 1 ≤ i ≤ n, C_{i} is the multiset of S_{i}-classes of subgroups H_{k} with |Y_{k}| = i. Bijectivity follows from the fact that conjugate subgroups yield the same λ and since H^{g} = ∏ H_{k}^{g}, conjugate subgroups yield conjugate C_{i}.

4.2 Counting Connected Subgroups of the Alternating Group

In Section 4 we noted that molecular species correspond to conjugacy classes of subgroups of Sym(n) and that atomic species correspond to conjugacy classes of connected subgroups of Sym(n) in the sense of Definition 10. In this Section we will count connected conjugacy classes of subgroups of the alternating group, up to S_{n} conjugacy and A_{n} conjugacy.

4.2.1 S_{n}-Orbits of Subgroups of the Alternating Group

In order to count the number of S_{n}-conjugacy classes of subgroups of the alternating group we introduce the following notation. Let

B = {H ≤ S_{n} : H ≤ A_{n} and R = {H ≤ S_{n} : H ≰ A_{n}}.

Then Sub(S_{n})/S_{n} = B/S_{n} ⊔ R/S_{n} and B/S_{n} is the set of S_{n} conjugacy classes of subgroups of the alternating group. The set R/S_{n} is the set of conjugacy classes of subgroups of S_{n} which are not contained in A_{n}. Table 12 illustrates both of these sequences together with the numbers of conjugacy classes of subgroups of S_{n} and A_{n}. In order to count the number of connected S_{n}-conjugacy classes of subgroups of A_{n} we apply the inverse Euler transform to the sequence |B/S_{n}| in Table 12, to obtain

\underline{A218968} : 1, 0, 1, 3, 4, 12, 12, 65, 58, 167, 198, 1207, 1178.

We can also count the number of connected conjugacy classes of subgroups of S_{n} not contained in A_{n} (i.e. corresponding to R/S_{n}) by subtracting the sequence above from \underline{A005226} to obtain

\underline{A218969} : 0, 1, 1, 3, 2, 15, 8, 65, 66, 431, 443, 3643, 3594.
\underline{A000638}  \underline{A029726} \underline{A218966} \underline{A218965}
n |Sub(S_{n})/S_{n}| |Sub(A_{n})/A_{n}| |B/S_{n}| |R/S_{n}|
1  1  1  1  0
2  2  1  1  1
3  4  2  2  2
4  11  5  5  6
5  19  9  9  10
6  56  22  22  34
7  96  40  37  59
8  296  137  112  184
9  554  223  195  359
10  1593  430  423  1170
11  3094  788  780  2314
12  10723  2537  2401  8322
13  20832  4558  4409  16423

Table 12: Red and Blue Subgroups of S_{n}

4.2.2 Connected Subgroups of the Alternating Group

Every subgroup of A_{n} is either connected or not connected with respect to the set {1, …, n} and shares this property with all subgroups in its A_{n}-conjugacy class. So we wish to count the number of A_{n}-conjugacy classes of connected subgroups of A_{n}. Unfortunately, the Euler transform does not apply to A_{n}-orbits. We test for connectedness a list of representatives of Sub(A_{n})/A_{n} in GAP and obtain

\underline{A218967} : 1, 0, 1, 3, 4, 12, 15, 87, 64, 168, 205, 1336, 1198.

Remark 13. There is a sequence in the encyclopedia, \underline{A116653}, which currently claims to count both the number of atomic species based on conjugacy classes of subgroups of the alternating group (i.e. the number of S_{n}-conjugacy classes of connected subgroups of A_{n}) and the number of A_{n}-conjugacy classes of connected subgroups of A_{n}. However this sequence is merely the inverse Euler transform of sequence \underline{A029726}, the number of conjugacy classes of subgroups of the alternating group. The number of S_{n}-conjugacy classes of connected subgroups of A_{n} is sequence \underline{A218968} and the number of A_{n}-conjugacy classes of connected subgroups of A_{n} is \underline{A216967}.

4.3 Connected Subgroups with Additional Properties

Appealing to Definition 10 we can count the connected subgroups of S_{n} which possess additional group theoretic properties. If the property of interest is compatible with taking direct products we can apply the inverse Euler transform to the sequence of numbers of all conjugacy classes of subgroups of S_{n} with this property to obtain the sequence of numbers of conjugacy classes of connected subgroups of S_{n} with this property. Table 13 records the number of connected subgroups of S_{n} which additionally possess the properties listed in the first row of the table. Each of the sequences in Table 13 is the inverse Euler transform of the corresponding sequence in Table 1.

\underline{A000638}  \underline{A218971}  \underline{A218972}  \underline{A218973}  \underline{A218974}
n  |Sub(S_{n})/S_{n}|  Abelian  Nilpotent  Solvable  SupSol
1  1  1  1  1  1
2  2  1  1  1  1
3  4  1  1  2  2
4  11  3  4  6  4
5  19  1  1  4  4
6  56  6  9  23  15
7  96  1  1  16  13
8  296  17  69  122  81
9  554  5  8  109  77
10  1593  40  238  551  352
11  3094  2  2  570  406
12  10723  162  2339  4633  2995
13  20832  5  8  4224  2866

Table 13: Connected Subgroups of S_{n}

4.4 Connected Partitions

The number of conjugacy classes of cyclic subgroups of S_{n} equals the number of partitions of n. The inverse Euler transform of this sequence yields the all ones sequence. This does not count the number of conjugacy classes of connected cyclic subgroups of S_{n} since the direct product of cyclic groups is not necessarily cyclic.

Definition 14. Let λ = [x_{1}, …, x_{l}] be a partition of n. Let G_{λ} be the simple graph with l vertices labeled by x_{1}, …, x_{l} where two vertices are connected by an edge if and only if their labels x_{i}, x_{j} are not coprime. We call the partition λ connected if the graph G_{λ} is connected.

Proposition 15. The number of conjugacy classes of connected cyclic subgroups of S_{n} equals the number of connected partitions of n.

Proof. Let C = ⟨c⟩ ≤ S_{n} be cyclic. Then the cycle lengths of the permutation c form a partition λ of n. For simplicity, we assume λ = [x_{1}, x_{2}]. Then c = ab where a is an x_{1} cycle and b is an x_{2} cycle. Let d = gcd(x_{1}, x_{2}). If d = 1 then G_{λ} is not connected and 1 = yx_{1} + zx_{2}, for some y, z ∈ ℤ. Then c^{yx_{1}} = a, c^{zx_{2}} = b and C = ⟨a⟩ × ⟨b⟩ is not connected. If d > 1 then C does not contain a generator of ⟨a⟩ or of ⟨b⟩. The case for general λ follows by a similar argument.

Example 16. There are 3 connected partitions λ of 13. Their graphs G_{λ} are shown in Figure 6.

13 2 2 3 6 6 4 3

Figure 6: The Graphs of the Connected Partitions of 13

Using Proposition 15 we obtain the sequence of numbers of conjugacy classes of connected cyclic subgroups of S_{n}

\underline{A218970} : 1, 1, 1, 2, 1, 4, 1, 5, 3, 8, 2, 14, 3.

Remark 17. There are two sequences in the encyclopedia which are quite similar to this sequence. Sequence \underline{A018783} counts the number of partitions of n into parts all of which have a common factor greater than 1. Sequence \underline{A200976} counts the number of partitions of n such that each pair of parts (if any) has a common factor greater than 1. For n ≤ 13, sequence \underline{A218970} above differs from both of these sequences when n = 1, 11, 13.

5 Concluding remarks

The sequences presented in this article have been computed using GAP. A GAP file contain-

ing the programs can be found at www.maths.nuigalway.ie/~liam/CountingSubgroups.g.

The GAP table of marks library Tomlib can be found here [11] and is a requirement for computing many of the sequences presented. It is worth pointing out that Holt has determined all conjugacy classes of subgroups of S_{n} for values of n up to and including n = 18, (see [5]). The majority of the sequences presented in this article rely on the availability of the table of marks of S_{n} and so we restrict our attention to n ≤ 13. We are grateful to Des MacHale for suggesting many of the sequences that we compute in this article. We thank the anonymous referees for helpful suggestions.

Appendix A Additional Sequences

Using the methods described in this article the following additional sequences have been computed.

\underline{A029726}  \underline{A218934}  \underline{A218935}  \underline{A218936}  \underline{A218937}  \underline{A218938}
n  |Sub(A_{n})/A_{n}|  Abelian  Cyclic  Nilpotent  Solvable  SupSol
1  1  1  1  1  1  1
2  1  1  1  1  1  1
3  2  2  2  2  2  2
4  5  4  3  4  5  4
5  9  5  4  5  8  7
6  22  9  6  10  19  14
7  40  12  8  13  33  22
8  137  30  12  53  122  70
9  223  41  17  69  192  122
10  430  60  23  122  364  225
11  788  81  29  160  650  395
12  2537  193  40  734  2194  1240
13  4558  243  52  848  3845  2185

Table 14: Conjugacy classes of subgroups of A_{n}

\underline{A005432} \underline{A062297} \underline{A051625}  \underline{A218939}  \underline{A218940}  \underline{A218941}
n  |Sub(S_{n})|  Abelian  Cyclic Nilpotent  Solvable  SupSol
1  1  1  1  1  1  1
2  2  2  2  2  2  2
3  6  5  5  5  6  6
4  30  21  17  24  30  28
5  156  87  67  102  154  144
6  1455  612  362  837  1429  1259
7  11300  3649  2039  5119  11065  9560
8  151221  35515  14170  78670  148817  123102
9  1694723  289927  109694  664658  1667697  1371022
10  29594446 3771118  976412 13514453  29103894  23449585
11 404126228 36947363 8921002 137227213 396571224 317178020
12 10594925360 657510251 101134244 4919721831 10450152905 8296640115
13 175238308453 7736272845 1104940280 60598902665 172658168937 136245390535

Table 15: Total number of subgroups of S_{n}

\underline{A218955} \underline{A218956} \underline{A218957} \underline{A218958} \underline{A218959}
n  Solvable  SupSol  Abelian  Cyclic Nilpotent
1  1  1  1  1  1
2  1  1  1  1  1
3  1  1  4  4  4
4  1  7  11  13  7
5  21  31  51  31  31
6  76  101  241  246  211
7  456  491  1506  1296  1156
8  1956  3011  9649  10774  5419
9  12136  18467  80281  83238  40027
10  80836  114983  640741  788820  348331
11  807676 1283723 6196576 6835170 3204796
12 8779816 13380643 66883411 81364944 38422891
13 104127596 148321603 775421219 848378532 467645179

Table 16: Total number of maximal property-P subgroups of S_{n}

\underline{A029725}  \underline{A218942} \underline{A051636}  \underline{A218943}  \underline{A218944}  \underline{A218945}
n  |Sub(A_{n})|  Abelian  Cyclic Nilpotent  Solvable  SupSol
1  1  1  1  1  1  1
2  1  1  1  1  1  1
3  2  2  2  2  2  2
4  10  9  8  9  10  9
5  59  37  32  37  58  53
6  501  207  167  252  488  418
7  3786  1192  947  1507  3664  2894
8  48337  11449  6974  21739  47210  33675
9  508402  93673  53426  186983  498102  369763
10  6469142  892783  454682  2369258  6293475  4769542
11  81711572  8534308 4303532 22872863  78805290  58853842
12 2019160542 148561283 50366912 746597568 1960342409 1395051100
13 31945830446 1740198891 553031624 9157758326 31130243721 21847262156

Table 17: Total no of subgroups of A_{n}

\underline{A218946} \underline{A218947} \underline{A218948} \underline{A218949} \underline{A218950}
n Solvable SupSol Abelian  Cyclic Nilpotent
1  1  1  1  1  1
2  1  1  1  1  1
3  1  1  1  1  1
4  1  2  2  2  2
5  3  3  3  3  3
6  4  3  5  4  3
7  5  4  6  5  5
8  6  6  13  6  6
9  10  8  19  8  7
10  12  10  22  10  9
11  14  13  27  14  12
12  17  18  40  20  17
13  24  22  54  24  20

Table 18: Maximal property-P subgroups of A_{n}

\underline{A029726}  \underline{A218951}  \underline{A218952}  \underline{A218953}  \underline{A218954}
n  |Sub(A_{n})/A_{n}|  Abelian  Nilpotent  Solvable  SupSol
1  1  1  1  1  1
2  1  0  0  0  0
3  2  1  1  1  1
4  5  2  2  3  2
5  9  1  1  3  3
6  22  3  4  10  6
7  40  1  1  11  6
8  137  14  36  80  42
9  223  5  9  52  39
10  430  12  49  145  85
11  788  2  2  165  104
12  2537  69  489  1208  686
13  4558  3  4  1033  617

Table 19: Connected subgroups of A_{n}

The number of connected even partitions of n

\underline{A218975} : 1, 0, 1, 1, 1, 2, 1, 3, 3, 4, 2, 8, 2.

\underline{A218960} \underline{A218961} \underline{A218962} \underline{A218963} \underline{A218964}
n Solvable SupSol  Abelian  Cyclic Nilpotent
1  1  1  1  1  1
2  1  1  1  1  1
3  3  3  3  3  3
4  1  10  10  9  10
5  36  40  30  30  30
6  225  110  115  100  110
7  686  645  861  665  1001
8  4655  5670  10536  3885  4005
9  28728  47754  78474  33093  45696
10 397005 311850 1008000  371700  379155
11 2210890 3014550 9302964 3790875 4913040
12 26975025 24022845 73024380 37839285 36701280
13 26121667 46950904 563291872 350984414 158538380

Table 20: Total number of maximal property-P subgroups of A_{n}

References

[1] M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Algebra Appl. 226/228 (1995), 57–72.

[2] W. Burnside, Theory of Groups of Finite Order, 2nd ed., Dover, 1955.

[3] Peter J. Cameron, Permutation Groups, London Mathematical Society Student Texts, Vol. 45, Cambridge University Press, 1999.

[4] GAP – Groups, Algorithms, and Programming, Version 4.4.12,

    http://www.gap-system.org, 2008.

[5] Derek F. Holt, Enumerating subgroups of the symmetric group, in Computational Group Theory and the Theory of Groups, II, Contemp. Math., Vol. 511, Amer. Math. Soc., 2010, pp. 33–37.

[6] J. Labelle and Y. N. Yeh, The relation between Burnside rings and combinatorial species, J. Combin. Theory Ser. A 50 (1989), 269–284.

[7] L. Naughton and G. Pfeiffer, Computing the table of marks of a cyclic extension, Math. Comp. 81 (2012), 2419–2438.

[8] Götz Pfeiffer, The subgroups of M_{24}, or how to compute the table of marks of a finite group, Experiment. Math. 6 (1997), 247–270.

[9] N. J. A. Sloane, The on-line encyclopedia of integer sequences, Notices Amer. Math. Soc. 50 (2003), 912–915.

[10] N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995.

[11] Tomlib, Version 1.2.1 , http://http://schmidt.nuigalway.ie/tomlib, 2011.

2010 Mathematics Subject Classification: Primary 20B40; Secondary 20D30, 19A22. Keywords: symmetric group, alternating group, table of marks, subgroup pattern.

(Concerned with sequences \underline{A000041}, \underline{A000088}, \underline{A000638}, \underline{A001349}, \underline{A005226}, \underline{A005432}, \underline{A018783}, \underline{A029725}, \underline{A029726}, \underline{A051625}, \underline{A051636}, \underline{A062297}, \underline{A116653}, \underline{A200976}, \underline{A216967}, \underline{A218909}, \underline{A218910}, \underline{A218911}, \underline{A218912}, \underline{A218913}, \underline{A218914}, \underline{A218915}, \underline{A218916}, \underline{A218917}, \underline{A218918}, \underline{A218919}, \underline{A218920}, \underline{A218921}, \underline{A218922}, \underline{A218923}, \underline{A218924}, \underline{A218925}, \underline{A218926}, \underline{A218927}, \underline{A218928}, \underline{A218929}, \underline{A218930}, \underline{A218931}, \underline{A218932}, \underline{A218933}, \underline{A218934}, \underline{A218935}, \underline{A218936}, \underline{A218937}, \underline{A218938}, \underline{A218939}, \underline{A218940}, \underline{A218941}, \underline{A218942}, \underline{A218943}, \underline{A218944}, \underline{A218945}, \underline{A218946}, \underline{A218947}, \underline{A218948}, \underline{A218949}, \underline{A218950}, \underline{A218951}, \underline{A218952}, \underline{A218953}, \underline{A218954}, \underline{A218955}, \underline{A218956}, \underline{A218957}, \underline{A218958}, \underline{A218959}, \underline{A218960}, \underline{A218961}, \underline{A218962}, \underline{A218963}, \underline{A218964}, \underline{A218965}, \underline{A218966}, \underline{A218967}, \underline{A218968}, \underline{A218969}, \underline{A218970}, \underline{A218971}, \underline{A218972}, \underline{A218973}, \underline{A218974}, and \underline{A218975}.)

Received November 28 2012; revised version received May 20 2013. Published in Journal of Integer Sequences, June 4 2013.

Return to Journal of Integer Sequences home page.