<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}



\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{tikz}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\newcommand{\Sym}{\mathsf{Sym}}

\begin{center}
\vskip 1cm{\LARGE\bf 
Integer Sequences Realized by the Subgroup \\
\vskip .11in
Pattern of the Symmetric Group
}
\vskip 1cm
\large
L. Naughton and G. Pfeiffer\\  
School of Mathematics \\
Applied Mathematics and Statistics\\  
National University of Ireland \\
Galway\\  
Ireland\\   
\href{mailto:liam.naughton@nuigalway.ie}{\tt liam.naughton@nuigalway.ie} \\
\end{center}

\vskip .2 in

\begin{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.
\end{abstract}

\section{Introduction}\label{sec:introduction}
The table of marks of a finite group $G$ was introduced by Burnside \cite{burn}. 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 \leq 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$, ($\beta_{G/H}(K)$).  If $H_{1}, \dots, H_{r}$ is a list of representatives of the conjugacy classes of subgroups of $G$, the 
table of marks is then the $(r \times r)$-matrix 
\[ M(G) = ( \beta_{G/H_{i}}(H_{j}) )_{i,j = 1.,\dots,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 \texttt{GAP} \cite{GAP4} library of tables of marks \texttt{Tomlib} \cite{tomlib} 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 \cite{pfe} and \cite{mcompaper}. 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 
\ref{sec:counting subgroups} we study the conjugacy classes of subgroups of  $S_{n}$ for $n \leq 13$. In Section \ref{sec:Sequences from the Table of Marks} 
we examine the tables of marks of $S_{n}$ for $n \leq 13$ and describe how much more information regarding the subgroup structure of $S_{n}$ can be obtained. In 
Section \ref{sec:conn} we discuss the Euler Transform and its applications in counting subgroups of $S_{n}$. 


\section{Counting subgroups}\label{sec:counting subgroups}
Given a list of representatives $\{ H_{1}, \dots, H_{r} \}$ of $\mathrm{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 \seqnum{A000638} and \seqnum{A029726} respectively in Sloane's encyclopedia \cite{intseq}. The \texttt{GAP} table of marks library \texttt{Tomlib}
 provides access to the conjugacy classes of subgroups of the symmetric and alternating groups for $n \leq 13$. Table~\ref{tab:sequences in Sn} 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 \ref{appendix}.



  \begin{center}
\begin{table}[H]
  \arraycolsep12pt
  $\begin{array}{|r|r|r|r|r|r|r|} \hline 
&amp; \text{\seqnum{A000638}} 
&amp; \text{\seqnum{A218909}}
&amp; \text{\seqnum{A000041}}
&amp; \text{\seqnum{A218910}}
&amp; \text{\seqnum{A218911}}
&amp; \text{\seqnum{A218912}}
\\
\hline 
n&amp; \text{$|\mathrm{Sub}(S_{n})/S_{n}|$} 
&amp; \text{Abelian}
&amp; \text{Cyclic}
&amp; \text{Nilpotent}
&amp; \text{Solvable}
&amp; \llap{\text{SupSol}}
\\
\hline
 1  &amp; 1          &amp;     1 &amp;       1  &amp;   1       &amp;       1       &amp;       1\\           
 2  &amp; 2          &amp;     2 &amp;       2  &amp;   2       &amp;       2       &amp;       2\\           
 3  &amp; 4          &amp;     3 &amp;       3  &amp;   3       &amp;       4       &amp;       4\\          
 4  &amp; 11         &amp;     7 &amp;       5  &amp;   8       &amp;       11      &amp;       9\\         
 5  &amp; 19         &amp;     9 &amp;       7  &amp;   10      &amp;       17      &amp;       15\\        
 6  &amp; 56         &amp;    20 &amp;      11  &amp;   25      &amp;       50      &amp;       38\\       
 7  &amp; 96         &amp;    26 &amp;      15  &amp;   32      &amp;       84      &amp;       65\\      
 8  &amp; 296        &amp;    61 &amp;      22  &amp;   127     &amp;       268     &amp;       187\\     
 9  &amp; 554        &amp;    82 &amp;      30  &amp;   156     &amp;       485     &amp;       341\\    
 10 &amp; 1593       &amp;   180 &amp;      42  &amp;   531     &amp;       1418    &amp;       923\\  
 11 &amp; 3094       &amp;   236 &amp;      56  &amp;   648     &amp;       2691    &amp;       1789\\
 12 &amp; 10723      &amp;   594 &amp;      77  &amp;   3727    &amp;       9725    &amp;       6118\\
 13 &amp; 20832      &amp;   762 &amp;     101  &amp;   4221    &amp;       18286   &amp;       11616\\
\hline
  \end{array}$
  
\caption{Sequences in $S_{n}$}\label{tab:sequences in Sn}
\end{table}
\end{center}


\subsection{Subgroup Orders}

\noindent A question of historical interest concerns the orders of subgroups of $S_{n}$. In \cite{cameronsbook} Cameron writes:
\textit{
 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 \leq 13$, Table \ref{sizes} records the numbers of different orders $\mathcal{O}(S_{n}),\mathcal{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 \mid |S_{n}|$ but $S_{n}$ has no subgroup of order $d$. Table \ref{missingsizes} records the number of missing subgroup orders of $S_{n}$ and $A_{n}$ for $n \leq 13$.


%\begin{table}[H]
\begin{minipage}[b]{0.4\linewidth}\centering
\begin{table}[H]
\begin{center}
\begin{tabular}{|l|r|r|}
\hline
 &amp; \seqnum{A218913} &amp; \seqnum{A218914} \\
\hline
$n$ &amp; $\mathcal{O}(S_{n})$ &amp; $\mathcal{O}(A_{n})$\\
\hline
1 &amp; 1 &amp; 1\\
2 &amp; 2 &amp; 1\\
3 &amp; 4 &amp; 2\\
4 &amp; 8 &amp; 5\\
5 &amp; 13 &amp; 9\\
6 &amp; 21 &amp; 15\\
7 &amp; 31 &amp; 22\\
8 &amp; 49 &amp; 38\\
9 &amp; 74 &amp; 59\\
10 &amp; 113 &amp; 89\\
11 &amp; 139 &amp; 115\\
12 &amp; 216 &amp; 180\\
13 &amp; 268 &amp; 226 \\
\hline
\end{tabular}
\caption{Subgroup Orders}
\label{sizes}
\end{center}
\end{table}
\end{minipage}
\hspace{0.2cm}
\begin{minipage}[b]{0.5\linewidth}
\centering
\begin{table}[H]
 \begin{center}
\begin{tabular}{|l|r|r|}
\hline
 &amp; \seqnum{A218915} &amp; \seqnum{A218916}\\
\hline
$n$ &amp; $d(S_{n})$ &amp; $d(A_{n})$\\
\hline
1 &amp; 0 &amp; 0\\
2 &amp; 0 &amp; 0\\
3 &amp; 0 &amp; 0\\
4 &amp; 0 &amp; 1\\
5 &amp; 3 &amp; 3\\
6 &amp; 9 &amp; 9\\
7 &amp; 29 &amp; 26\\
8 &amp; 47 &amp; 46\\
9 &amp; 86 &amp; 81\\
10 &amp; 157 &amp; 151\\
11 &amp; 401 &amp; 365\\
12 &amp; 576 &amp; 540\\
13 &amp; 1316 &amp; 1214\\
\hline
 \end{tabular}
\caption{Missing Subgroup Orders}
\label{missingsizes}
 \end{center}
\end{table}
\end{minipage}
%\end{table}
\section{Counting using the table of marks}\label{sec:Sequences from 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.
\subsection{About Tables of Marks}
Let $G$ be a finite group and let $\mathrm{Sub}(G)$ denote the set of subgroups of $G$. By $\mathrm{Sub}(G)/G$ we denote the set of conjugacy classes of subgroups 
of $G$. For $H,K \in \mathrm{Sub}(G)$ let 
\[ \beta_{G/H}(K) = \# \{ Hg \in G/H : (Hg)k = Hg \mbox{ for all } k \in K \} = \# \{ g \in G : K \leq 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 $\beta_{G/H}(K) \neq 0 \Rightarrow |K| \leq |H|$. 
If $H_{1}, \dots, 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 \times r)$-matrix 
\[ M(G) = ( \beta_{G/H_{i}}(H_{j}) )_{i,j = 1,\dots,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 \ref{toms4}.
\begin{figure}[H]
\begin{center}
\begin{tabular}{l|ccccccccccc}
$S_{4}/1 $&amp;$ 24 $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $\\ 
$S_{4}/2 $&amp;$ 12 $&amp;$ 4 $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $\\ 
$S_{4}/2 $&amp;$ 12 $&amp;$ . $&amp;$ 2 $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $\\ 
$S_{4}/3 $&amp;$ 8 $&amp;$ . $&amp;$ . $&amp;$ 2 $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $\\ 
$S_{4}/2^2 $&amp;$ 6 $&amp;$ 6 $&amp;$ . $&amp;$ . $&amp;$ 6 $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $\\ 
$S_{4}/2^2 $&amp;$ 6 $&amp;$ 2 $&amp;$ 2 $&amp;$ . $&amp;$ . $&amp;$ 2 $&amp;$  $&amp;$  $&amp;$  $&amp;$  $&amp;$  $\\ 
$S_{4}/4 $&amp;$ 6 $&amp;$ 2 $&amp;$ . $&amp;$ . $&amp;$ . $&amp;$ . $&amp;$ 2 $&amp;$   $&amp;$  $&amp;$  $&amp;$  $\\ 
$S_{4}/S_3 $&amp;$ 4 $&amp;$ . $&amp;$ 2 $&amp;$ 1 $&amp;$ . $&amp;$ . $&amp;$ . $&amp;$ 1 $&amp;$   $&amp;$  $&amp;$  $\\ 
$S_{4}/D_8 $&amp;$ 3 $&amp;$ 3 $&amp;$ 1 $&amp;$ . $&amp;$ 3 $&amp;$ 1 $&amp;$ 1 $&amp;$ . $&amp;$ 1 $&amp;$   $&amp;$  $\\ 
$S_{4}/A_4 $&amp;$ 2 $&amp;$ 2 $&amp;$ . $&amp;$ 2 $&amp;$ 2 $&amp;$ . $&amp;$ . $&amp;$ . $&amp;$ . $&amp;$ 2 $&amp;$ $\\ 
$S_{4}/S_4 $&amp;$ 1 $&amp;$ 1 $&amp;$ 1 $&amp;$ 1 $&amp;$ 1 $&amp;$ 1 $&amp;$ 1 $&amp;$ 1 $&amp;$ 1 $&amp;$ 1 $&amp;$ 1 $\\ 
\hline
 &amp;$ 1 $&amp;$ 2 $&amp;$ 2 $&amp;$ 3 $&amp;$ 2^2 $&amp;$ 2^2 $&amp;$ 4 $&amp;$ S_3 $&amp;$ D_8 $&amp;$ A_4 $&amp;$ S_4$
\end{tabular} 
\end{center}
\caption{Table of Marks $M(S_{4})$}
\label{toms4}
\end{figure}
\noindent 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 \leq 13$ is shown in Figure \ref{fig:sum M(G)}. We can also sum the entries on the diagonal to obtain the sequences in Figure \ref{fig:sum diag}.
\bigskip
%\begin{table}[H]
\begin{minipage}[b]{0.4\linewidth}\centering
\begin{table}[H]
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
 &amp; \seqnum{A218917} &amp; \seqnum{A218918} \\
\hline
$n$ &amp; $S_{n}$ &amp; $A_{n}$\\
\hline
1 &amp; 1 &amp; 1\\
2 &amp; 4 &amp; 1\\
3 &amp; 18 &amp; 5\\
4 &amp; 146 &amp; 39\\
5 &amp; 681 &amp; 192\\
6 &amp; 7518 &amp; 1717\\
7 &amp; 58633 &amp; 13946\\
8 &amp; 952826 &amp; 243391\\
9 &amp; 11168496 &amp; 2693043\\
10 &amp; 232255571 &amp; 38343715\\
11 &amp; 3476965896 &amp; 545787051\\
12 &amp; 108673489373 &amp; 15787210045 \\
13 &amp; 1951392769558 &amp; 268796141406 \\
\hline
\end{tabular}
\end{center}
\caption{Sum of $M(G)$}
\label{fig:sum M(G)}
\end{table}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[b]{0.5\linewidth}
\centering
\begin{table}[H]
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
 &amp; \seqnum{A218919} &amp; \seqnum{A218920} \\
\hline
$n$ &amp; $S_{n}$ &amp; $A_{n}$\\
\hline
1 &amp; 1 &amp; 1\\
2 &amp; 3 &amp; 1\\
3 &amp; 10 &amp; 4\\
4 &amp; 47 &amp; 19\\
5 &amp; 165 &amp; 73\\
6 &amp; 950 &amp; 412\\
7 &amp; 5632 &amp; 2660\\
8 &amp; 43772 &amp; 21449\\
9 &amp; 376586 &amp; 184541\\
10 &amp; 3717663 &amp; 1827841\\
11 &amp; 40555909 &amp; 20043736\\
12 &amp; 484838080 &amp; 240206213\\
13 &amp; 6286289685 &amp; 3119816216 \\
\hline
\end{tabular}
\end{center}
\caption{Sum of the Diagonal}
\label{fig:sum diag}
\end{table}
\end{minipage}
%\end{table}





\noindent We will now collect some elementary properties of tables of marks in Lemma \ref{lem:propertiesoftoms}. 
\begin{lemma}\label{lem:propertiesoftoms}
\noindent Let $H, K \leq G$. Then the following hold:
\begin{enumerate}
\item[(i)] The first entry of every row of $M(G)$ is the index of the corresponding subgroup,
\[\beta_{G/H} (1) = |G:H|.\]
\item[(ii)] The entry on the diagonal is,
\[ \beta_{G/H}(H) = |N_G (H):H|. \]
\item[(iii)] The length of the conjugacy class $[H]$ of $H$ is given by,
\[ |[H]| = |G:N_G (H)| = \frac{\beta_{G/H} (1) }{\beta_{G/H} (H) }. \]
\item[(iv)] The number of conjugates of $H$ which contain $K$ is given by,
\[ |\lbrace H^a : a \in G, K \leq H^a \rbrace | = \frac{\beta_{G/H} (K)}{\beta_{G/H} (H) }.\]
\end{enumerate}
\end{lemma}
\noindent The following formula which follows trivially from Lemma \ref{lem:propertiesoftoms} (iv) relates marks to incidences in the subgroup lattice of $G$.
\begin{align}\label{marksasincidence}
 \beta_{G/H}(K) = |N_{G}(H):H| \cdot \# \{H^g : K \leq H^g, g \in G \}.
\end{align}

\noindent As a first application of Formula \ref{marksasincidence} we obtain the following lemma which enables us to count the total number of subgroups of $G$.
\begin{lemma}\label{lem:totalsub}
Given a list $\{ H_{1}, \dots, H_{r} \}$ of representatives of the conjugacy classes of subgroups of $G$, the total number of subgroups of $G$ is 
\[ |\mathrm{Sub}(G)| = \sum \limits_{i = 1}^{r} \frac{\beta_{G/H_{i}}(1)}{\beta_{G/H_{i}}(H_{i}) }. \]
\end{lemma}
\begin{proof}
It follows from Formula \ref{marksasincidence} that for any subgroup $H \leq G$, $\frac{\beta_{G/H}(1)}{\beta_{G/H}(H)}$ is the length of the conjugacy class of 
$H$ in $G$.
\end{proof}
\noindent Table \ref{totalnumberofsubssymalt} lists the total number of subgroups of $S_{n}$ and $A_{n}$ for $n \leq 13$.

\begin{table}[H]

\begin{center}
\begin{tabular}{|l|l|l|}
\hline
&amp;\seqnum{A029725} &amp; \seqnum{A005432} \\
\hline
$n$ &amp; $A_{n}$ &amp; $S_{n}$\\
\hline
1 &amp; 1 &amp; 1\\
2 &amp; 1 &amp; 2\\
3 &amp; 2 &amp; 6\\
4 &amp; 10 &amp; 30\\
5 &amp; 59 &amp; 156\\
6 &amp; 501 &amp; 1455\\
7 &amp; 3786 &amp; 11300\\
8 &amp; 48337 &amp; 151221\\
9 &amp; 508402 &amp; 1694723\\
10 &amp; 6469142 &amp; 29594446\\
11 &amp; 81711572 &amp; 404126228\\
12 &amp; 2019160542 &amp; 10594925360\\
13 &amp; 31945830446 &amp; 175238308453\\
\hline
\end{tabular}
\end{center}
\caption{Total Number of Subgroups of $A_{n}$ and $S_{n}$}
\label{totalnumberofsubssymalt}
\end{table}


\subsection{Counting Incidences}
Another immediate consequence of Formula \ref{marksasincidence} is that by dividing each row of the table of marks of $G$ by its diagonal entry $\beta_{G/H}(H)$  we obtain a matrix 
 $\mathcal{C}(G)$ describing 
containments in the subgroup lattice of $G$, where the $(H,K)$-entry is 
\begin{align}
\mathcal{C}(H,K) = \# \{ K^{g} : H \leq K^{g}, g \in G \}.
\end{align}
Figure \ref{fig:subgroup containments} illustrates the containment matrix of the symmetric group $S_{4}$. 
\begin{center}
\begin{figure}[H]
\[ 
\begin{array}{c|ccccccccccc}
1 &amp; 1 &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
2 &amp; 3 &amp; 1 &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
2 &amp; 6 &amp; . &amp; 1 &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
3 &amp; 4 &amp; . &amp; . &amp; 1 &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
2^2 &amp; 1 &amp; 1 &amp; . &amp; . &amp; 1 &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
2^2 &amp; 3 &amp; 1 &amp; 1 &amp; . &amp; . &amp; 1 &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
4 &amp; 3 &amp; 1 &amp; . &amp; . &amp; . &amp; . &amp; 1 &amp;   &amp;  &amp;  &amp;  \\ 
S_3 &amp; 4 &amp; . &amp; 2 &amp; 1 &amp; . &amp; . &amp; . &amp; 1 &amp;   &amp;  &amp;  \\ 
D_8 &amp; 3 &amp; 3 &amp; 1 &amp; . &amp; 3 &amp; 1 &amp; 1 &amp; . &amp; 1 &amp;   &amp;  \\ 
A_4 &amp; 1 &amp; 1 &amp; . &amp; 1 &amp; 1 &amp; . &amp; . &amp; . &amp; . &amp; 1 &amp; \\ 
S_4 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 \\ 
\hline
 &amp; 1 &amp; 2 &amp; 2 &amp; 3 &amp; 2^2 &amp; 2^2 &amp; 4 &amp; S_3 &amp; D_8 &amp; A_4 &amp; S_4
\end{array}  \]
\caption{Containment Matrix : $\mathcal{C}(S_{4})$}
\label{fig:subgroup containments}
\end{figure}
\end{center}
The conjugacy classes of subgroups of $G$ are partially ordered by $[H] \leq [K]$ if $H \leq K^g$ for some $g \in G$ i.e. if $\mathcal{C}(H, K) \neq 0$.
Therefore we can easily obtain the incidence matrix, $\mathcal{I}(G)$, of the poset of conjugacy classes of subgroups 
of $G$ by replacing each nonzero entry in $\mathcal{C}(G)$, (or $M(G)$ ) by an entry $1$.  
Figure \ref{fig:incidence matrix S_(4)} shows the incidence matrix $\mathcal{I}(S_{4})$ of the poset of conjugacy classes of subgroups of $S_{4}$.
\begin{center}
\begin{figure}[H]
\[ 
\begin{array}{c|ccccccccccc}
1 &amp; 1 &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
2 &amp; 1 &amp; 1 &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
2 &amp; 1 &amp; . &amp; 1 &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
3 &amp; 1 &amp; . &amp; . &amp; 1 &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
2^2 &amp; 1 &amp; 1 &amp; . &amp; . &amp; 1 &amp;  &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
2^2 &amp; 1 &amp; 1 &amp; 1 &amp; . &amp; . &amp; 1 &amp;  &amp;  &amp;  &amp;  &amp;  \\ 
4 &amp; 1 &amp; 1 &amp; . &amp; . &amp; . &amp; . &amp; 1 &amp;   &amp;  &amp;  &amp;  \\ 
S_3 &amp; 1 &amp; . &amp; 1 &amp; 1 &amp; . &amp; . &amp; . &amp; 1 &amp;   &amp;  &amp;  \\ 
D_8 &amp; 1 &amp; 1 &amp; 1 &amp; . &amp; 1 &amp; 1 &amp; 1 &amp; . &amp; 1 &amp;   &amp;  \\ 
A_4 &amp; 1 &amp; 1 &amp; . &amp; 1 &amp; 1 &amp; . &amp; . &amp; . &amp; . &amp; 1 &amp; \\ 
S_4 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 \\ 
\hline
 &amp; 1 &amp; 2 &amp; 2 &amp; 3 &amp; 2^2 &amp; 2^2 &amp; 4 &amp; S_3 &amp; D_8 &amp; A_4 &amp; S_4
\end{array}  \]
\caption{Incidence Matrix : $\mathcal{I}(S_{4})$}
\label{fig:incidence matrix S_(4)}
\end{figure}
\end{center}
For comparison with Figure \ref{fig:incidence matrix S_(4)} we illustrate the 
poset of conjugacy classes of subgroups of $S_{4}$ in Figure \ref{lattices4}.
 
 \begin{figure}[H]
\begin{center}
\scalebox{0.8}{
\begin{tikzpicture}

 \node (1) at (10,0)[black]   {$1$};
\node (b2) at (8,2)[black]   {$2$};

\node (r2) at (6,2)[black]  {$2$};
\node (b3) at (12, 3)[black]   {$3$};
\node (b22) at (8, 4)[black]   {$2^2$};
\node (r22) at (4, 4)[black]  {$2^2$};
\node (r4) at (6, 4)[black]  {$4$};
\node (s3) at (13, 5)[black]  {$S_{3}$};
\node (d8) at (6, 6) [black] {$D_{8}$};
\node (a4) at (10, 8) [black] {$A_{4}$};
\node (s4) at (10, 10)[black]  {$S_{4}$};

\path
(1) edge[thick] (b2)
(1) edge[thick]  (b3)
(b2) edge[thick]  (b22)
(b3) edge[thick]  (a4)
(b22) edge[thick]  (a4)
(1) edge[thick] (r2)
(b2) edge[thick] (r22)
(b2) edge[thick] (r4)
(b22) edge[thick] (d8)
(a4) edge[thick] (s4)
(b3) edge[thick] (s3)
(r2) edge[thick] (s3)
(r2) edge[thick]  (r22)
(r4) edge[thick]  (d8)
(r22) edge[thick]  (d8)
(d8) edge[thick]  (s4)
(s3) edge[thick]  (s4);


\end{tikzpicture}}
\end{center}
\caption{Poset of Conjugacy Classes of Subgroups of $S_{4}$}
\label{lattices4}
 \end{figure}
%\sum_{\substack{j=0\\j \neq i}} ^n 
\begin{lemma}
 The number of incidences in the poset of conjugacy classes of subgroups of $G$ is given by 
\[  \sum\mathcal{I}(G). \]
\end{lemma} 
\begin{proof}
 The incidence matrix $\mathcal{I}(G)$ is obtained by replacing every nonzero entry in the table of marks by an entry $1$. By Formula \ref{marksasincidence} 
$\mathcal{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$.
\end{proof}
Table \ref{fig:incidences in poset} lists the number of incidences in the poset of conjugacy classes of subgroups of $A_{n}$ and $S_{n}$ for $n \leq 13$.
\begin{lemma}
 The total number of incidences in the entire subgroup lattice of $G$ is given by 
\[ \sum \mathcal{C}(G). \]
\end{lemma}
\begin{proof}
 For $H,K \in \mathrm{Sub}(G)/G$ the $H,K$ entry in $\mathcal{C}(G)$ is the number of incidences between $H,K$ in the subgroup lattice of $G$. Thus summing 
over the entries in $\mathcal{C}(G)$ yields the total number of incidences in the entire subgroup lattice of $G$.
\end{proof}
\noindent Table \ref{fig : incidences in subgroup lattice} records the number of incidences in the subgroup lattices of $S_{n}$ and $A_{n}$ for $n \leq 13$.

\begin{table}[H]
\begin{minipage}[t]{0.4\linewidth}\centering
\begin{table}[H]
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
 &amp; \seqnum{A218921} &amp; \seqnum{A218922} \\
\hline
$n$ &amp; $S_{n}$  &amp;$A_{n}$\\ \hline
1 &amp; 1 &amp; 1\\
2 &amp; 3 &amp; 1\\
3 &amp; 9 &amp; 3\\
4 &amp; 44 &amp; 13\\
5 &amp; 101 &amp; 32\\
6 &amp;  523 &amp; 128 \\
7 &amp; 1195  &amp; 330\\
8 &amp; 6751  &amp; 2309 \\
9 &amp; 16986  &amp; 4271 \\
10 &amp; 87884  &amp; 12468 \\
11 &amp; 248635  &amp; 33329 \\
12 &amp; 1709781  &amp; 196182 \\
13 &amp; 4665651  &amp; 490137  \\
\hline
\end{tabular}
\end{center}
\caption{Incidences in Poset}
\label{fig:incidences in poset}
\end{table}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[t]{0.5\linewidth}
\centering
\begin{table}[H]
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
 &amp; \seqnum{A218924} &amp; \seqnum{A218923} \\
\hline
$n$ &amp; $A_{n}$ &amp; $S_{n}$\\ 
\hline
1 &amp; 1 &amp; 1\\
2 &amp; 1 &amp; 3\\
3 &amp; 3 &amp; 11\\
4 &amp; 18 &amp; 68\\
5 &amp; 85 &amp; 262\\
6 &amp; 657 &amp; 2261\\
7 &amp; 4374 &amp; 14032\\
8 &amp; 55711 &amp; 176245\\
9 &amp; 530502 &amp; 1821103\\
10 &amp; 6603007 &amp; 30883491\\
11 &amp; 82736601 &amp; 415843982\\
12 &amp; 2032940127 &amp; 10779423937\\
13 &amp; 32102236563 &amp; 177718085432\\
\hline
\end{tabular}
\end{center}
\caption{Incidences in Subgroup Lattice}
\label{fig : incidences in subgroup lattice}
\end{table}
\end{minipage}
\end{table}

\subsection{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 \ref{marksasincidence} 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$.
\begin{lemma}\label{lemma:edgesupward}
 Let $H, K \in \mathrm{Sub}(G)/G$. Then the number of conjugates of $H$ contained in $K$ is given by 
\[  E^{\uparrow} (H,K) = |\{ H^{g}, g \in G : H^{g} \leq K \}| = \frac{\beta_{G/K}(H) \beta_{G/H}(1)}{\beta_{G/H}(H) \beta_{G/K}(1)} \]
\end{lemma}
\begin{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}| \cdot |\{ H^{g} , g \in G : H^{g} \leq K \}| = |[K]_{G}| \cdot |\{ K^{g} , g \in G : K^{g} \geq H \}|. \]
By Formula \ref{marksasincidence} $|[H]_{G}| = \frac{\beta_{G/H}(1)}{\beta_{G/H}(H)}$ and $|[K]_{G}| = \frac{\beta_{G/K}(1)}{\beta_{G/K}(K)}$. 
Thus $E^{\uparrow}(H,K)$ can be expressed in terms of marks.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Identifying Maximal Subgroups}
It will be necessary, for the sections that follow, to identify for $H_{i} \in \mathrm{Sub}(G)/G$ which classes $H_{j} \in \mathrm{Sub}(G)/G$ are maximal in $H_{i}$. 
\begin{lemma}\label{lem:max}
Let $H_{i} \in \mathrm{Sub}(G)/G = \{ H_{1}, \ldots, H_{r} \}$. Denote by $\rho_{i} = \{ j : H_{j} &lt;_{G} H_{i} \}$ the set of indices in $\{1, \ldots , 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
\begin{align}\label{form:max}
 \mathrm{Max}(H_{i}) = \rho_{i} \setminus \bigcup_{j \in \rho_{i}} \rho_{j} 
\end{align}
\end{lemma}
The set of values $\rho_{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 \ref{form:max} is implemented in \texttt{GAP} via the function \texttt{MaximalSubgroupsTom}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%





\begin{lemma}
 Let $\mathrm{Sub}(G)/G = \{ H_{1}, \ldots, 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(\mathrm{Sub}(G)/G)| = \sum \limits_{i = 1}^{r} | \mathrm{Max}(H_{i}) |. \]
\end{lemma}
\begin{proof}
 By Lemma \ref{lem:max}, $\mathrm{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 
$\mathrm{Sub}(G)/G$ each edge corresponds to a maximal subgroup.
\end{proof}
 Table \ref{fig:edges in poset} 
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 \leq 13$.
In order to count the number of edges in the Hasse diagram of the entire subgroup lattice of $G$ we appeal to Formula \ref{marksasincidence} and Lemma \ref{lemma:edgesupward}.
\begin{lemma}
 Let $\mathrm{Sub}(G)/G = \{ H_{1}, \ldots, 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)) = \sum \limits_{i=1}^{r} \sum \limits_{j \in \mathrm{Max}(H_{i})} E^{\uparrow}(H_{i},H_{j}). \]
\end{lemma}
\begin{proof}
 By restricting $E^{\uparrow}(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$. 
\end{proof}

Table \ref{fig:edges subgroup lattice} records the total number of edges in the Hasse diagram of the subgroup lattice of $S_{n}$ and $A_{n}$ for $n \leq 13$.

\begin{table}[H]
\begin{minipage}[]{0.4\linewidth}\centering
\begin{table}[H]
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
 &amp; \seqnum{A218925} &amp; \seqnum{A218926} \\
\hline
$n$ &amp; $S_{n}$&amp; $A_{n}$ \\ \hline
1 &amp; 0 &amp; 0\\
2 &amp; 1  &amp;0 \\
3 &amp;4 &amp;1 \\
4 &amp;17  &amp;5 \\
5 &amp;37  &amp;13 \\
6 &amp;149  &amp;44 \\
7 &amp;290  &amp;98 \\
8 &amp;1080  &amp;419 \\
9 &amp;2267  &amp;722 \\
10 &amp;8023 &amp;1592 \\
11 &amp;17249  &amp;3304 \\
12 &amp;72390  &amp;12645\\
13 &amp;153419  &amp;24792 \\
\hline
\end{tabular}
\caption{Edges in Poset}
\label{fig:edges in poset}
\end{center}
\end{table}
\end{minipage}
\hspace{0.5cm}
\begin{minipage}[]{0.5\linewidth}
\centering
\begin{table}[H]
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
 &amp; \seqnum{A218928} &amp; \seqnum{A218927} \\
\hline
$n$ &amp; $A_{n}$ &amp; $S_{n}$\\ \hline
1 &amp; 0 &amp; 0\\
2 &amp; 0 &amp; 1\\
3 &amp; 1 &amp; 8\\
4 &amp; 15 &amp; 66\\
5 &amp; 168 &amp; 501\\
6 &amp; 2051 &amp; 6469\\
7 &amp; 19305 &amp; 60428\\
8 &amp; 283258 &amp; 926743\\
9 &amp; 3255913 &amp; 11902600\\
10 &amp; 46464854 &amp; 240066343\\
11 &amp; 670282962 &amp; 3677270225\\
12 &amp; 18723796793 &amp; 108748156239\\
13 &amp; 321480817412 &amp; 1980478458627\\
\hline
\end{tabular}
\caption{Edges in Subgroup Lattice}
\label{fig:edges subgroup lattice}
\end{center}
\end{table}
\end{minipage}
\end{table}



\subsection{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$.  
\begin{lemma}\label{lem:maxP}
Let $\mathrm{Sub}(G)/G = \{ H_{1}, \ldots, H_{r} \}$ and let $\rho = \{ i \in [1, \ldots, r ] : H_{i} \mbox{ is a property $P$ subgroup} \}$.
 Then the positions of the maximal property $P$ 
subgroups of $G$ are given by 

 \begin{align}\label{form:maxP}
 P(G) = \rho \setminus \bigcup_{j \in \rho}  \mathrm{Max}(H_{j})
\end{align}
\end{lemma}

\noindent In Figure \ref{fig:max abelian subs s4} the classes of maximal abelian subgroups of $S_{4}$ are boxed.



 \begin{figure}[H]
\begin{center}
\scalebox{0.8}{
\begin{tikzpicture}

 \node (1) at (10,0)[black]   {$1$};
\node (b2) at (8,2)[black]   {$2$};

\node (r2) at (6,2)[black]  {$2$};
\node (b3) at (12, 3)[draw,blue]   {$\mathbf{3}$};
\node (b22) at (8, 4)[draw,blue]   {$\mathbf{2^2}$};
\node (r22) at (4, 4)[draw,blue]  {$\mathbf{2^2}$};
\node (r4) at (6, 4)[draw,blue]  {$\mathbf{4}$};
\node (s3) at (13, 5)[black]  {$S_{3}$};
\node (d8) at (6, 6) [black] {$D_{8}$};
\node (a4) at (10, 8) [black] {$A_{4}$};
\node (s4) at (10, 10)[black]  {$S_{4}$};

\path
(1) edge[thick,dashed,red] (b2)
(1) edge[thick,dashed,red]  (b3)
(b2) edge[thick,dashed,red]  (b22)
(b3) edge[thick]  (a4)
(b22) edge[thick]  (a4)
(1) edge[thick,dashed,red] (r2)
(b2) edge[thick,dashed,red] (r22)
(b2) edge[thick,dashed,red] (r4)
(b22) edge[thick] (d8)
(a4) edge[thick] (s4)
(b3) edge[thick] (s3)
(r2) edge[thick] (s3)
(r2) edge[thick,dashed,red]  (r22)
(r4) edge[thick]  (d8)
(r22) edge[thick]  (d8)
(d8) edge[thick]  (s4)
(s3) edge[thick]  (s4);


\end{tikzpicture}}
\end{center}
\caption{Maximal Abelian Subgroups of $S_{4}$}
\label{fig:max abelian subs s4}
 \end{figure}


Table \ref{fig:max sn} 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. 


\begin{table}[H]
 \begin{center}
\begin{tabular}{|l|r|r|r|r|r|}
\hline
 &amp; \seqnum{A218929} &amp; \seqnum{A218930}&amp; \seqnum{A218931} &amp; \seqnum{A218932}&amp; \seqnum{A218933} \\
\hline 
n &amp; Solvable &amp; SupSol &amp; Abelian &amp; Cyclic &amp; Nilpotent\\
\hline
1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1\\
2 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1\\
3 &amp; 1 &amp; 1 &amp; 2 &amp; 2 &amp; 2\\
4 &amp; 1 &amp; 2 &amp; 4 &amp; 3 &amp; 2\\
5 &amp; 3 &amp; 3 &amp; 5 &amp; 3 &amp; 3\\
6 &amp; 4 &amp; 4 &amp; 7 &amp; 5 &amp; 5\\
7 &amp; 5 &amp; 5 &amp; 10 &amp; 6 &amp; 6\\
8 &amp; 6 &amp; 6 &amp; 17 &amp; 11 &amp; 7\\
9 &amp; 9 &amp; 8 &amp; 23 &amp; 15 &amp; 9\\
10 &amp; 12 &amp; 11 &amp; 30 &amp; 20 &amp; 12\\
11 &amp; 14 &amp; 14 &amp; 41 &amp; 24 &amp; 15\\
12 &amp; 17 &amp; 19 &amp; 61 &amp; 34 &amp; 20\\
13 &amp; 24 &amp; 23 &amp; 80 &amp; 43 &amp; 25\\
\hline
 \end{tabular}
 \end{center}
\caption{Maximal Property-P Subgroups of $S_{n}$}
\label{fig:max sn}
\end{table}

\section{Connected subgroups and the Euler transform}\label{sec:conn}
The conjugacy classes of subgroups of the symmetric group play an important role in the theory of combinatorial species as described in \cite{speciespaper}. 
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)}$.

\begin{definition}\label{connected}
 For each $H \leq \mathsf{Sym}(X)$ there is a finest partition of $X = \bigsqcup Y_{i}$ such that $H = \prod H_{i}$ with $H_{i} \leq \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$.
\end{definition}
\begin{example}
Let $X = \{ 1,2,3,4 \}$ and consider $H = \langle (1,2), (3,4) \rangle$ and $H' = \langle (1,2)(3,4) \rangle$. Partitioning $X$ into $Y_{1} = \{ 1,2 \}, Y_{2} = \{ 3.4 \}$ 
gives $H = H_{1} \times H_{2}$ where $H_{1} =  \langle (1,2) \rangle \leq \mathsf{Sym}(\{ 1,2 \}) , H_{2} = \langle (3,4) \rangle \leq \mathsf{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}$.
\end{example}


\noindent 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 \setminus Y$ then $H$ is not connected.
 
 In general a subgroup $H \leq \Sym{(X)}$ is a product of connected subgroups $H_{i} \leq \Sym{(Y_{i})}$. Sequence \seqnum{A000638} records the number of molecular species of 
degree $n$ or equivalently the number of  
conjugacy classes of subgroups of $\Sym{(n)}$. Sequence  \seqnum{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.

\subsection{The Euler Transform}
If two sequences of integers $\{ c_{k} \} = ( c_{1}, c_{2}, c_{3}, \ldots )$ and  $\{ m_{n} \}  = ( m_{1}, m_{2}, m_{3}, \ldots )$
are related by
\begin{align}\label{eulertransform}
 1 + \sum \limits_{n \geq 1} m_{n}x^{n} = \prod \limits_{k \geq 1} \left(\frac{1}{1 - x^{k}} \right)^{c_{k}} .
\end{align}
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 \cite{BernSloane}). One sequence can 
be computed from the other by introducing the intermediate sequence $\{ b_{n} \}$ defined by
\begin{align}
 b_{n} = \sum \limits_{d | n}^{} d c_{d} = n m_{n} - \sum \limits_{k=1}^{n-1} b_{k} m_{n-k}.
\end{align}
Then 
\begin{align}
 m_{n} &amp;= \frac{1}{n} \Bigl(    b_{n} + \sum \limits_{k =1}^{n-1} b_{k} m_{n-k}    \Bigr),&amp; c_{n} =  \frac{1}{n} \sum \limits_{d | n}^{} \mu (n/d) b_{d},
\end{align}
where $\mu$ is the number-theoretic M\"obius function.




There 
are many applications of this pair of transforms (see \cite{sloane}). For example, the inverse Euler transform 
applied to the sequence of numbers of unlabeled graphs on $n$ nodes (\seqnum{A000088}) yields the sequence of numbers of connected graphs on $n$ nodes (\seqnum{A001349}). 
To understand how Formula \ref{eulertransform} 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 \ref{eulertransform} is
\begin{align}\label{multiset}
 m_{n} = \sum \limits_{1^{a_{1}}, 2^{a_{2}}, \ldots, n^{a_{n}} \vdash n}^{} \prod \limits_{i}^{}  \left(\! \!{c_{i} \choose a_{i}}\!\! \right) % \binom{c_{i}}{a_{i}}
\end{align}
where $\bigl(\! \!{c_{i} \choose a_{i}}\!\! \bigr)$ 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 $(\lambda, (C_{1}, \ldots, C_{n}))$ where 
$\lambda =   1^{a_{1}}, 2^{a_{2}}, \ldots, 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 \leq i \leq n$. If $c_{i}$ is the number of connected unlabeled graphs on $i$ nodes then, by Formula \ref{multiset}, $m_{n}$ is the total number of unlabeled 
graphs on $n$ nodes.

In the same way, the inverse Euler 
transform of \seqnum{A000638} (the number of conjugacy classes of subgroups of $S_{n}$) is \seqnum{A005226}, (the number of connected conjugacy classes of 
subgroups of $S_{n}$) as formalized in the following Lemma. 
\begin{lemma}\label{subgroups and pairs}
There is a bijection between the conjugacy classes of subgroups of $S_{n}$ and the set of pairs of the form $( \lambda, (C_{1}, \ldots, C_{n}) )$ where 
$\lambda = 1^{a_{1}}, 2^{a_{2}}, \ldots, 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, \ldots, n$.
\end{lemma}
\begin{proof}
Given a representative $H$ of the conjugacy class of subgroups $[H] \in \mathsf{Sub}(S_{n})/S_{n}$ we associate a pair $( \lambda, (C_{1}, \ldots, C_{n}) )$ 
to $H$ as follows. Write $H = \prod H_{k}$ where each $H_{k}$ is a connected subgroup of $\Sym{(Y_{k})}$. Then $X = \{ 1, \ldots, n \} = \bigsqcup Y_{k}$. Recording the size of each $Y_{k}$ yields a 
partition $\lambda =  1^{a_{1}}, 2^{a_{2}}, \ldots, n^{a_{n}}$. For $1 \leq i \leq 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 $\lambda$ and since $H^{g} = \prod H_{k}^{g}$, conjugate subgroups yield conjugate $C_{i}$.
\end{proof}

\subsection{Counting Connected Subgroups of the Alternating Group}
In Section \ref{sec:conn} 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 \ref{connected}. In this Section we will count connected conjugacy classes of subgroups 
of the alternating group, up to $S_{n}$ conjugacy and $A_{n}$ conjugacy.

\subsubsection{$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 \[ \mathcal{B} = \{ H \leq S_{n} : H \leq A_{n} \mbox{ and } \mathcal{R} = \{ H \leq S_{n} : H \nleq A_{n} \}. \]
Then $\mathsf{Sub}(S_{n})/S_{n} = \mathcal{B}/S_{n} \sqcup \mathcal{R}/S_{n}$ and $\mathcal{B}/S_{n}$ is the set of $S_{n}$ conjugacy classes of subgroups of the alternating group. 
The set $\mathcal{R}/S_{n}$ is the set of conjugacy classes of subgroups of $S_{n}$ which are not contained in $A_{n}$. Table 
\ref{bluered} 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 $|\mathcal{B}/S_{n}|$ in Table \ref{bluered}, to obtain

\[ \seqnum{A218968}: \mbox{    } 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  $\mathcal{R}/S_{n}$) by subtracting the sequence above from \seqnum{A005226} to obtain
\[ \seqnum{A218969}: \mbox{    }  0, 1, 1, 3, 2, 15, 8, 65, 66, 431, 443, 3643, 3594. \]
\begin{table}[H]
\begin{center}
\begin{tabular}{|l|r|r|r|r|}
\hline
 &amp;\seqnum{A000638} &amp;\seqnum{A029726} &amp;\seqnum{A218966} &amp;\seqnum{A218965} \\
\hline
$n$ &amp; $|\mathsf{Sub}(S_{n})/S_{n}|$ &amp; $|\mathsf{Sub}(A_{n})/A_{n}|$ &amp; $|\mathcal{B}/S_{n}|$&amp; $|\mathcal{R}/S_{n}|$ \\
\hline
$1$ &amp;$1$ &amp; $1$ &amp; $1$&amp;$0$  \\
$2$ &amp;$2$ &amp; $1$ &amp; $1$&amp;$1$  \\
$3$ &amp;$4$ &amp; $2$ &amp; $2$&amp;$2$  \\
$4$ &amp;$11$ &amp; $5$ &amp; $5$&amp;$6$  \\
$5$ &amp;$19$ &amp; $9$ &amp; $9$&amp; $10$ \\
$6$ &amp;$56$ &amp; $22$ &amp; $22$&amp;$34$  \\
$7$ &amp;$96$ &amp; $40$ &amp; $37$&amp;$59$  \\
$8$ &amp;$296$ &amp; $137$ &amp; $112$&amp;$184$  \\
$9$ &amp;$554$ &amp; $223$ &amp; $195$&amp;$359$  \\
$10$ &amp;$1593$ &amp; $430$ &amp; $423$&amp;$1170$  \\
$11$ &amp;$3094$ &amp; $788$ &amp; $780$&amp;$2314$  \\
$12$ &amp;$10723$ &amp; $2537$ &amp; $2401$&amp;$8322$  \\
$13$ &amp;$20832$ &amp; $4558$ &amp; $4409$&amp;$16423$  \\
\hline
\end{tabular}
\caption{Red and Blue Subgroups of $S_{n}$}\label{tab:redblue subgroups Sn}
\label{bluered}
\end{center}
\end{table}


\subsubsection{Connected Subgroups of the Alternating Group}
Every subgroup of $A_{n}$ is either connected or not connected with respect to the set $\{ 1, \ldots, 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 $\mathsf{Sub}(A_{n})/A_{n}$ in \textsf{GAP} and obtain
 \[\seqnum{A218967}: \mbox{     } 1, 0, 1, 3, 4, 12, 15, 87, 64, 168, 205, 1336, 1198. \]
\begin{remark}
There is a sequence in the encyclopedia, \seqnum{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 \seqnum{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 \seqnum{A218968} and the number of $A_{n}$-conjugacy classes of connected 
subgroups of $A_{n}$ is \seqnum{A216967}.
\end{remark}
\subsection{Connected Subgroups with Additional Properties}
Appealing to Definition \ref{connected} 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  \ref{tab:connected subgroups Sn} 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 \ref{tab:connected subgroups Sn} is the inverse Euler transform of the corresponding sequence in Table \ref{tab:sequences in Sn}.

\begin{table}[H]
\begin{center}
  \arraycolsep12pt
  $\begin{array}{|r|r|r|r|r|r|} 
\hline
&amp; \seqnum{A000638}
&amp; \seqnum{A218971}
&amp; \seqnum{A218972}
&amp; \seqnum{A218973}
&amp; \seqnum{A218974}
\\
\hline
n&amp; \text{$|\mathrm{Sub}(S_{n})/S_{n}|$} 
&amp; \text{Abelian}
&amp; \text{Nilpotent}
&amp; \text{Solvable}
&amp; \llap{\text{SupSol}}
\\
\hline
 1  &amp; 1          &amp;     1 &amp;      1       &amp;       1       &amp;       1\\           
 2  &amp; 2          &amp;     1 &amp;      1       &amp;       1       &amp;       1\\           
 3  &amp; 4          &amp;     1 &amp;      1       &amp;       2       &amp;       2\\          
 4  &amp; 11         &amp;     3 &amp;      4       &amp;       6       &amp;       4\\         
 5  &amp; 19         &amp;     1 &amp;      1       &amp;       4       &amp;       4\\        
 6  &amp; 56         &amp;     6 &amp;      9       &amp;       23      &amp;       15\\       
 7  &amp; 96         &amp;     1 &amp;      1       &amp;       16      &amp;       13\\      
 8  &amp; 296        &amp;    17 &amp;      69      &amp;       122     &amp;       81\\     
 9  &amp; 554        &amp;     5 &amp;      8       &amp;       109     &amp;       77\\    
 10 &amp; 1593       &amp;    40 &amp;      238     &amp;       551     &amp;       352\\  
 11 &amp; 3094       &amp;     2 &amp;      2       &amp;       570     &amp;       406\\
 12 &amp; 10723      &amp;   162 &amp;      2339    &amp;       4633    &amp;       2995\\
 13 &amp; 20832      &amp;     5 &amp;      8       &amp;       4224    &amp;       2866\\
\hline
  \end{array}$
  
\caption{Connected Subgroups of $S_{n}$}\label{tab:connected subgroups Sn}
\end{center}
\end{table}


\subsection{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.
\bigskip
\begin{definition}
 Let $\lambda = [x_{1}, \ldots, x_l ] $ be a partition of $n$. Let $G_{\lambda}$ be the simple graph with $l$ vertices labeled by $x_1, \ldots, 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 $\lambda$ connected if the graph $G_{\lambda}$ is connected.
\end{definition}

\begin{proposition}\label{conpart}
 The number of conjugacy classes of connected cyclic subgroups of $S_{n}$ equals the number of connected partitions of $n$.
\end{proposition}
\begin{proof}
Let $C = \langle c \rangle \leq S_{n}$ be cyclic. Then the cycle lengths of the permutation $c$ form a partition $\lambda$ of $n$.  
For simplicity, we assume $\lambda = [ 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_{\lambda}$ 
is not connected and   $ 1 = y x_1 + z x_2$, for some $y, z \in \mathbb{Z}$. Then $c^{yx_1} = a, c^{zx_2} = b$ and $C = \langle a \rangle \times \langle b \rangle$ is not connected. 
If $d &gt; 1$ then $C$ does not contain a generator of $\langle a \rangle$ or of $\langle b \rangle$. The case for general $\lambda$ follows by a similar argument.
\end{proof}

\begin{example}
There are $3$ connected partitions $\lambda$ of $13$. Their graphs $G_{\lambda}$ are shown in Figure \ref{fig:partitions of 13}.
\bigskip

 \begin{figure}[H]
\begin{center}
\scalebox{0.8}{
\begin{tikzpicture}

\node (13) at (2,3)[black,draw,circle]  {$13$};

\node (a21) at (5,4)[black,draw,circle]  {$2$};
\node (a22) at (7,4)[black,draw,circle]  {$2$};
\node (a3) at (5,2)[black,draw,circle]  {$3$};
\node (a6) at (7,2)[black,draw,circle]  {$6$};

\node (b6) at (9,4)[black,draw,circle]  {$6$};
\node (b4) at (11,4)[black,draw,circle]  {$4$};
\node (b3) at (11,2)[black,draw,circle]  {$3$};

\path
(a21) edge[thick] (a22)
(a21) edge[thick] (a6)
(a22) edge[thick] (a6)
(a3) edge[thick] (a6)

(b6) edge[thick] (b3)
(b6) edge[thick] (b4)

;
\end{tikzpicture}}
\end{center}
\caption{The Graphs of the Connected Partitions of $13$}
\label{fig:partitions of 13}
 \end{figure}

\end{example}
Using Proposition \ref{conpart} we obtain the sequence of numbers of conjugacy classes of connected cyclic subgroups of $S_{n}$
\[ \seqnum{A218970}: \mbox{    }  1, 1, 1, 2, 1, 4, 1, 5, 3, 8, 2, 14, 3. \]

\begin{remark}
 There are two sequences in the encyclopedia which are quite similar to this sequence.  Sequence \seqnum{A018783} counts 
the number of partitions of $n$ into parts all of which have a common factor greater than $1$.  Sequence \seqnum{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 \leq 13$, sequence \seqnum{A218970} above differs from both of these sequences 
when $n = 1, 11, 13$. 
\end{remark}




% begin appendix

\section{Concluding remarks} The sequences presented in this article have been computed using \textsf{GAP}. A \textsf{GAP} file containing the programs can be 
found at \url{www.maths.nuigalway.ie/~liam/CountingSubgroups.g}. The \textsf{GAP} table of marks library \textsf{Tomlib} can be found here \cite{tomlib} 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 \cite{holt}). 
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 \leq 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

\newcommand{\appsection}[1]{\let\oldthesection\thesection
  \renewcommand{\thesection}{Appendix \oldthesection}
  \section{#1}\let\thesection\oldthesection}


\appsection{Additional Sequences}\label{appendix}
Using the methods described in this article the following additional sequences have been computed.
  \begin{center}
\begin{table} [H]
  \arraycolsep12pt
  $\begin{array}{|r|r|r|r|r|r|r|} 
\hline
&amp;\seqnum{A029726}&amp;\seqnum{A218934} &amp;\seqnum{A218935} &amp;\seqnum{A218936} &amp;\seqnum{A218937} &amp; \seqnum{A218938} \\
\hline
n&amp; \text{$|\mathrm{Sub}(A_{n})/A_{n}|$} 
&amp; \text{Abelian}
&amp; \text{Cyclic}
&amp; \text{Nilpotent}
&amp; \text{Solvable}
&amp; \llap{\text{SupSol}}
\\
\hline
 1  &amp; 1          &amp;     1 &amp;       1  &amp;   1       &amp;       1       &amp;       1\\           
 2  &amp; 1          &amp;     1 &amp;       1  &amp;   1       &amp;       1       &amp;       1\\           
 3  &amp; 2          &amp;     2 &amp;       2  &amp;   2       &amp;       2       &amp;       2\\          
 4  &amp; 5          &amp;     4 &amp;       3  &amp;   4       &amp;       5       &amp;       4\\         
 5  &amp; 9          &amp;     5 &amp;       4  &amp;   5       &amp;       8       &amp;       7\\        
 6  &amp; 22         &amp;     9 &amp;       6  &amp;   10      &amp;       19      &amp;       14\\       
 7  &amp; 40         &amp;    12 &amp;       8  &amp;   13      &amp;       33      &amp;       22\\      
 8  &amp; 137        &amp;    30 &amp;      12  &amp;   53      &amp;       122     &amp;       70\\     
 9  &amp; 223        &amp;    41 &amp;      17  &amp;   69      &amp;       192     &amp;       122\\    
 10 &amp; 430        &amp;    60 &amp;      23  &amp;   122     &amp;       364     &amp;       225\\  
 11 &amp; 788        &amp;    81 &amp;      29  &amp;   160     &amp;       650     &amp;       395\\
 12 &amp; 2537       &amp;   193 &amp;      40  &amp;   734     &amp;       2194    &amp;       1240\\
 13 &amp; 4558       &amp;   243 &amp;      52  &amp;   848     &amp;       3845    &amp;       2185\\
\hline
\end{array}$
\caption{Conjugacy classes of subgroups of $A_{n}$}\label{tab:sequences in An}
\end{table}
\end{center}

  \begin{center}
\begin{table} [H]
  \arraycolsep3pt
  $\begin{array}{|r|r|r|r|r|r|r|} \hline
 &amp;\seqnum{A005432} &amp;\seqnum{A062297} &amp;\seqnum{A051625} &amp;\seqnum{A218939} &amp;\seqnum{A218940} &amp;\seqnum{A218941}  \\ \hline
 n &amp;\text{$|\mathrm{Sub}(S_{n})|$} 
&amp; \text{Abelian}
&amp; \text{Cyclic}
&amp; \text{Nilpotent}
&amp; \text{Solvable}
&amp; \llap{\text{SupSol}}
\\
\hline
1	   &amp;    1  	&amp;    1   &amp;    1   &amp;    1   &amp;    1   &amp;    1 \\ 
2	   &amp;    2   	&amp;    2   &amp;    2   &amp;    2   &amp;    2   &amp;    2 \\   
3	   &amp;    6   	&amp;    5   &amp;    5   &amp;    5   &amp;    6   &amp;    6 \\
4	   &amp;    30   	&amp;    21   &amp;    17   &amp;    24   &amp;    30   &amp;    28 \\
5	   &amp;    156   	&amp;    87   &amp;    67   &amp;    102   &amp;    154   &amp;    144 \\
6	   &amp;    1455   	&amp;    612   &amp;    362   &amp;    837   &amp;    1429   &amp;    1259 \\ 
7	   &amp;    11300   &amp;    3649   &amp;    2039   &amp;    5119   &amp;    11065   &amp;    9560 \\
8	   &amp;    151221   &amp;    35515   &amp;    14170   &amp;    78670   &amp;    148817   &amp;    123102 \\
9	   &amp;    1694723   &amp;    289927   &amp;    109694   &amp;    664658   &amp;    1667697   &amp;    1371022 \\ 
10 	   &amp;    29594446   &amp;    3771118   &amp;    976412   &amp;    13514453   &amp;    29103894   &amp;    23449585 \\
11 	   &amp;    404126228   &amp;    36947363   &amp;    8921002   &amp;    137227213   &amp;    396571224   &amp;    317178020 \\
12 	   &amp;    10594925360   &amp;    657510251   &amp;    101134244   &amp;    4919721831   &amp;    10450152905   &amp;    8296640115 \\
13 	   &amp;    175238308453   &amp;    7736272845   &amp;    1104940280   &amp;    60598902665   &amp;    172658168937   &amp;    136245390535 \\
\hline
\end{array}$
\caption{Total number of subgroups of $S_{n}$}\label{tab:totsequences in Sn}
\end{table}
\end{center}







\begin{table}[H]
 \begin{center}
\begin{tabular}{|l|r|r|r|r|r|}
\hline 
 &amp; \seqnum{A218955} &amp; \seqnum{A218956} &amp; \seqnum{A218957} &amp; \seqnum{A218958} &amp; \seqnum{A218959}\\
\hline
n &amp; Solvable &amp; SupSol &amp; Abelian &amp; Cyclic &amp; Nilpotent\\
\hline
    1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1 \\    2&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1 \\    3&amp; 1&amp; 1&amp; 4&amp; 4&amp; 4 \\    4&amp; 1&amp; 7&amp; 11&amp; 13&amp; 7 \\    5&amp; 21&amp; 31&amp; 51&amp; 31&amp; 31 \\    6&amp; 76&amp; 101&amp; 241&amp; 246&amp; 211 \\  
    7&amp; 456&amp; 491&amp; 1506&amp; 1296&amp; 1156 \\    8&amp; 1956&amp; 3011&amp; 9649&amp; 10774&amp; 5419 \\    9&amp; 12136&amp; 18467&amp; 80281&amp; 83238&amp; 40027 \\    10&amp; 80836&amp; 114983&amp; 640741&amp; 788820&amp; 348331 \\  
    11&amp; 807676&amp; 1283723&amp; 6196576&amp; 6835170&amp; 3204796 \\    12&amp; 8779816&amp; 13380643&amp; 66883411&amp; 81364944&amp; 38422891 \\    13&amp; 104127596&amp; 148321603&amp; 775421219&amp; 848378532&amp; 467645179\\
\hline
 \end{tabular}
 \end{center}
\caption{Total number of maximal property-P subgroups of $S_{n}$}
\label{fig:tot max Sn}
\end{table}






  \begin{center}
\begin{table} [H]
  \arraycolsep5pt
  $\begin{array}{|r|r|r|r|r|r|r|r|} \hline
 &amp; \seqnum{A029725} &amp;\seqnum{A218942} &amp; \seqnum{A051636} &amp;\seqnum{A218943} &amp;\seqnum{A218944} &amp;\seqnum{A218945} \\
\hline
n&amp; \text{$|\mathrm{Sub}(A_{n})|$} 
&amp; \text{Abelian}
&amp; \text{Cyclic}
&amp; \text{Nilpotent}
&amp; \text{Solvable}
&amp; \llap{\text{SupSol}}
\\
\hline
 1  &amp; 1          &amp;     1 &amp;       1  &amp;   1       &amp;       1       &amp;       1\\           
 2  &amp; 1          &amp;     1 &amp;       1  &amp;   1       &amp;       1       &amp;       1\\           
 3  &amp; 2          &amp;     2 &amp;       2  &amp;   2       &amp;       2       &amp;       2\\          
 4  &amp; 10          &amp;     9 &amp;       8  &amp;   9       &amp;       10       &amp;       9\\         
 5  &amp; 59          &amp;     37 &amp;       32  &amp;   37       &amp;       58       &amp;       53\\        
 6  &amp; 501         &amp;     207 &amp;       167  &amp;   252      &amp;       488      &amp;       418\\       
 7  &amp; 3786         &amp;    1192 &amp;       947  &amp;   1507      &amp;       3664      &amp;       2894\\      
 8  &amp; 48337        &amp;    11449 &amp;      6974  &amp;   21739      &amp;       47210     &amp;      33675 \\     
 9  &amp; 508402        &amp;    93673 &amp;      53426  &amp;   186983      &amp;        498102    &amp;      369763 \\    
 10 &amp; 6469142       &amp;    892783 &amp;      454682  &amp;    2369258    &amp;       6293475     &amp;       4769542\\  
 11 &amp; 81711572        &amp;    8534308 &amp;      4303532  &amp;   22872863    &amp;       78805290     &amp;       58853842\\
 12 &amp; 2019160542       &amp;   148561283 &amp;      50366912  &amp;   746597568     &amp;       1960342409    &amp;      1395051100 \\
 13 &amp; 31945830446      &amp;   1740198891 &amp;      553031624  &amp;   9157758326     &amp;       31130243721    &amp;      21847262156 \\
\hline
  \end{array}$
\caption{Total no of subgroups of $A_{n}$}\label{tab:totsequences in An}
\end{table}
\end{center}

\begin{table}[H]
 \begin{center}
\begin{tabular}{|l|r|r|r|r|r|}
\hline 
 &amp; \seqnum{A218946}  &amp; \seqnum{A218947}  &amp; \seqnum{A218948}  &amp; \seqnum{A218949}  &amp; \seqnum{A218950} \\
\hline 
n &amp; Solvable &amp; SupSol &amp; Abelian &amp; Cyclic &amp; Nilpotent\\
\hline
1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1\\
2 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1\\
3 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1\\
4 &amp; 1 &amp; 2 &amp; 2 &amp; 2 &amp; 2\\
5 &amp; 3 &amp; 3 &amp; 3 &amp; 3 &amp; 3\\
6 &amp; 4 &amp; 3 &amp; 5 &amp; 4 &amp; 3\\
7 &amp; 5 &amp; 4 &amp; 6 &amp; 5 &amp; 5\\
8 &amp; 6 &amp; 6 &amp; 13 &amp; 6 &amp; 6\\
9 &amp; 10 &amp; 8 &amp; 19 &amp; 8 &amp; 7\\
10 &amp; 12 &amp; 10 &amp; 22 &amp; 10 &amp; 9\\
11 &amp; 14 &amp; 13 &amp; 27 &amp; 14 &amp; 12\\
12 &amp; 17 &amp; 18 &amp; 40 &amp; 20 &amp; 17\\
13 &amp; 24 &amp; 22 &amp; 54 &amp; 24 &amp; 20\\
\hline
 \end{tabular}
 \end{center}
\caption{Maximal property-P subgroups of $A_{n}$}
\label{fig:max an}
\end{table}

\begin{table}[H]
\begin{center}
  \arraycolsep12pt
  $\begin{array}{|r|r|r|r|r|r|} 
\hline 
 &amp; \seqnum{A029726}  &amp; \seqnum{A218951}  &amp; \seqnum{A218952}  &amp; \seqnum{A218953}  &amp; \seqnum{A218954} \\
\hline
n&amp; \text{$|\mathrm{Sub}(A_{n})/A_{n}|$} 
&amp; \text{Abelian}
&amp; \text{Nilpotent}
&amp; \text{Solvable}
&amp; \llap{\text{SupSol}}
\\
\hline
 1  &amp; 1          &amp;     1 &amp;      1       &amp;       1       &amp;       1\\           
 2  &amp; 1          &amp;     0 &amp;      0       &amp;       0       &amp;       0\\           
 3  &amp; 2          &amp;     1 &amp;      1       &amp;       1       &amp;       1\\          
 4  &amp; 5          &amp;     2 &amp;      2       &amp;       3       &amp;       2\\         
 5  &amp; 9          &amp;     1 &amp;      1       &amp;       3       &amp;       3\\        
 6  &amp; 22         &amp;     3 &amp;      4       &amp;       10      &amp;       6\\       
 7  &amp; 40         &amp;     1 &amp;      1       &amp;       11      &amp;       6\\      
 8  &amp; 137        &amp;    14 &amp;      36      &amp;       80     &amp;       42\\     
 9  &amp; 223        &amp;     5 &amp;      9       &amp;       52     &amp;       39\\    
 10 &amp; 430        &amp;    12 &amp;      49      &amp;       145     &amp;       85\\  
 11 &amp; 788        &amp;     2 &amp;      2       &amp;       165     &amp;       104\\
 12 &amp; 2537       &amp;   69 &amp;      489      &amp;       1208    &amp;       686\\
 13 &amp; 4558       &amp;     3 &amp;      4       &amp;       1033    &amp;       617\\
\hline
  \end{array}$
  
\caption{Connected subgroups of $A_{n}$}\label{tab:connected subgroups An}
\end{center}
\end{table}
%maxsol :=[ 1, 1, 1, 1, 3, 4, 5, 6, 10, 12, 14, 17, 24 ]
%maxsupsol:= [ 1, 1, 1, 2, 3, 3, 4, 6, 8, 10, 13, 18, 22 ]
%maxadel:=[ 1, 1, 1, 2, 3, 5, 6, 13, 19, 22, 27, 40, 54 ]
%maxcycy:=[ 1, 1, 1, 2, 3, 4, 5, 6, 8, 10, 14, 20, 24 ]
%maxnil:-=[ 1, 1, 1, 2, 3, 3, 5, 6, 7, 9, 12, 17, 20 ]
\noindent The number of connected even partitions of $n$
\[\seqnum{A218975}: \mbox{    }   1, 0, 1, 1, 1, 2, 1, 3, 3, 4, 2, 8, 2. \]






\begin{table}[H]
 \begin{center}
\begin{tabular}{|l|r|r|r|r|r|}
\hline 
 &amp; \seqnum{A218960} &amp; \seqnum{A218961} &amp; \seqnum{A218962} &amp; \seqnum{A218963} &amp; \seqnum{A218964} \\
\hline 
n &amp; Solvable &amp; SupSol &amp; Abelian &amp; Cyclic &amp; Nilpotent\\
\hline
  1&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1 \\   2&amp; 1&amp; 1&amp; 1&amp; 1&amp; 1 \\   3&amp; 3&amp; 3&amp; 3&amp; 3&amp; 3 \\   4&amp; 1&amp; 10&amp; 10&amp; 9&amp; 10 \\   5&amp; 36&amp; 40&amp; 30&amp; 30&amp; 30 \\   6&amp; 225&amp; 110&amp; 115&amp; 100&amp; 110 \\  
   7&amp; 686&amp; 645&amp; 861&amp; 665&amp; 1001 \\   8&amp; 4655&amp; 5670&amp; 10536&amp; 3885&amp; 4005 \\   9&amp; 28728&amp; 47754&amp; 78474&amp; 33093&amp; 45696 \\   10&amp; 397005&amp; 311850&amp; 1008000&amp; 371700&amp; 379155 \\  
   11&amp; 2210890&amp; 3014550&amp; 9302964&amp; 3790875&amp; 4913040 \\   12&amp; 26975025&amp; 24022845&amp; 73024380&amp; 37839285&amp; 36701280 \\   13&amp; 26121667&amp; 46950904&amp; 563291872&amp; 350984414&amp; 158538380 \\
\hline
 \end{tabular}
 \end{center}
\caption{Total number of maximal property-P subgroups of $A_{n}$}
\label{fig:tot max P An}
\end{table}




\begin{thebibliography}{10}

\bibitem{BernSloane}
M.~Bernstein and N.~J.~A. Sloane, Some canonical sequences of integers,
  {\it Linear Algebra Appl.} \textbf{226/228} (1995), 57--72. 

\bibitem{burn}
W.~Burnside, \emph{Theory of Groups of Finite Order}, 2nd ed., 
Dover, 1955.

\bibitem{cameronsbook}
Peter~J. Cameron, \emph{Permutation Groups}, London Mathematical Society
  Student Texts, Vol.~45, Cambridge University Press, 1999.

\bibitem{GAP4}
\emph{{GAP -- Groups, Algorithms, and Programming, Version 4.4.12}}, \newline
  \url{http://www.gap-system.org}, 2008.

\bibitem{holt}
Derek~F. Holt, Enumerating subgroups of the symmetric group, in
  \textit{Computational Group Theory and the Theory of Groups, {II}},
  Contemp. Math.,
  Vol.\ 511, Amer. Math. Soc., 2010, pp.~33--37. 

\bibitem{speciespaper}
J.~Labelle and Y.~N. Yeh, The relation between {B}urnside rings and
  combinatorial species, \textit{J. Combin. Theory Ser. A}
  \textbf{50} (1989), 
  269--284. 

\bibitem{mcompaper}
L.~Naughton and G.~Pfeiffer, Computing the table of marks of a cyclic
  extension, \textit{Math. Comp.} \textbf{81} (2012), 2419--2438.

\bibitem{pfe}
G{\"o}tz Pfeiffer, The subgroups of {$M_{24}$}, or how to compute the
  table of marks of a finite group, \textit{Experiment. Math.}
  \textbf{6} (1997), 247--270. 

\bibitem{intseq}
N.~J.~A. Sloane, The on-line encyclopedia of integer sequences, 
\textit{Notices Amer. Math. Soc.} \textbf{50} (2003), 912--915. 

\bibitem{sloane}
N.~J.~A. Sloane and Simon Plouffe, \emph{The Encyclopedia of Integer
  Sequences}, Academic Press, 1995.

\bibitem{tomlib}
\emph{{Tomlib, Version 1.2.1 }},
  \url{http://http://schmidt.nuigalway.ie/tomlib}, 2011.

\end{thebibliography}



\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 20B40; Secondary 20D30, 19A22.

\noindent \emph{Keywords:}   
symmetric group,
alternating group,
table of marks,
subgroup pattern.


\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received November 28 2012;
revised version received  May 20 2013.
Published in {\it Journal of Integer Sequences}, June 4 2013.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                



</pre></body></html>