\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}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf
Automatic Enumeration of Regular Objects}
\vskip 1cm
\large
Marni Mishna\footnote{
The author thanks the Canadian Natural Science and
Engineering Research Council for funding this work through the PDF program.
This work was completed while at LaBRI, Universit\'e
Bordeaux I, and at the Fields Institute, Toronto, Canada.}\\
Department of Mathematics\\
Simon Fraser University\\
8888 University Drive\\
Burnaby, BC V5A 1S6\\
Canada \\
\href{mmishna@sfu.ca}{\tt mmishna@sfu.ca}\\
\end{center}
\vskip .2 in
\begin{abstract}
We describe a framework for systematic enumeration of families
combinatorial structures that possess a certain regularity. More
precisely, we describe how to obtain the differential equations
satisfied by their generating series. These differential equations
are then used to determine the initial terms in the counting sequence and for
asymptotic analysis. The key tool is the scalar product for
symmetric functions.
\end{abstract}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
%% example environment
\newenvironment{example}{
\begin{quotation}\noindent{\bfseries Example.\/} }{\end{quotation}}
%% symmetric functions
\def\gadj{{\#}}
\def\uadj{\star} % usual adjunction
\def\sadj{\perp} % symmetric adjunction
\newcommand{\pleth}[2]{#1\left[#2\right]} % symmetric plethysm
\newcommand{\Hk}{{\mathcal{H}_k}} % Hammond series
\def\iprod{*} % tensor/ inner/ .. product
\def\HH{\ensuremath{H}}
\def\EE{\ensuremath{ E}}
\def\SS{\ensuremath{\mathcal S}}
\def\Hk{{\mathcal{H}_k}} % Hammond series
\newcommand{\rsc}[2]{\left\langle#1, #2\right\rangle} % symm. scalar product
\newcommand{\rsp}[2]{\left\langle#1| #2\right\rangle} % usual scalar product
\def\sgn{\operatorname{sgn}} % sign of a permutation
\def\field{K}
\def\Lambdap{\field[\boldp]} % SFs viewed as a ring in p
\def\Lambdapt{\field[t][\boldp]}
\def\lser{\field[\![\boldp]\!]} % power series
\def\bm{{\mathbf{m}}}
%% q stuff
\newcommand\exq[1]{\ifthenelse{\equal{#1}{}}{\operatorname{ex}_q}{\operatorname{
ex}_q\left(#1\right)}}
%% font definitions
\newcommand\cA{\mathcal A}
\newcommand\bP{\mathbb P}
\newcommand\bA{\mathbb A}
\newcommand\bN{\mathbb N}
\newcommand\bR{\mathbb R}
\newcommand\bZ{\mathbb Z}
\newcommand\bS{\mathbb S}
\newcommand\bC{\mathbb C}
\newcommand{\cF}{{\mathcal F}}
\newcommand{\cB}{{\mathcal B}}
\newcommand{\cS}{{\mathcal S}}
\newcommand{\cG}{{\mathcal G}}
\newcommand{\cH}{{\mathcal H}}
\newcommand{\cI}{{\mathcal I}}
\newcommand{\cJ}{{\mathcal J}}
\newcommand{\cL}{{\mathcal L}}
\newcommand{\cX}{{\mathcal X}}
\newcommand{\cR}{{\mathcal R}}
\newcommand{\cU}{{\mathcal U}}
\newcommand{\cV}{{\mathcal V}}
\def\sF{\ensuremath{\mathsf{F}} } % species font
\def\sP{\ensuremath{\mathsf{P}} }
\def\sE{\ensuremath{\mathsf{E}} }
\def\sG{\ensuremath{\mathsf{G}} }
\def\sS{\ensuremath{\mathsf{S}} }
\def\sR{\ensuremath{\mathsf{R}} }
\def\sX{\ensuremath{\mathsf{X}} }
\def\sL{\ensuremath{\mathsf{L}} }
\def\sC{\ensuremath{\mathsf{C}} }
\def\C{\ensuremath{\mathbb C}}
\def\R{\ensuremath{\mathbb R}}
\def\Z{\ensuremath{\mathbb Z}}
\def\Q{\ensuremath{\mathbb Q}}
\def\N{\ensuremath{\mathbb N}}
\def\A{\ensuremath{\mathbb A}}
%%%%%%%%%%% algorithm names
\def\spa{{\sf scalar\_de}}
\def\ham{{\sf hammond}}
%----------------
%\usepackage{amssymb,amsmath, amsthm}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}{Conjecture}
\newtheorem{defn}{Definition }
\newenvironment{pf}{\begin{proof}}{\end{proof}}
%----------------
\section{Introduction}
Some classes of combinatorial objects naturally possess a substantial
amount of symmetry and when formal sums of monomials encoding
some parameter of interest are taken over the entire class, symmetric
functions, or symmetric series appear. There has been
some recent activity to determine how to extract enumerative series of
sparse sub-families of these classes directly from the symmetric
functions. The principle can be illustrated with one well studied
example, the subset of labelled graphs in which the degree of each
vertex is a fixed value, say $k$, known as the {\em $k$-regular
graphs}. Here, we encode a graph by its degree sequence. When
we consider the sum of this encoding over all graphs, they are encoded
by the infinite product
\begin{equation}\label{eq:allgraphs}
G(x_1, x_2, \ldots)=\prod_{i0$, which we also
denote~$\lambda\vdash n$. Partitions serve as indices for the five
principal symmetric function families that we use: homogeneous
($h_\lambda$), power ($p_\lambda$), monomial ($m_\lambda$), elementary
($e_\lambda$), and Schur ($s_\lambda$). These are series in the
infinite set of variables, $x_1,x_2,\dotsc$ over a field~$\field$ of
characteristic~0. When the indices are restricted to all partitions
of the same positive integer~$n$, any of the five families forms a
basis for the vector space of symmetric polynomials of degree~$n$
in~$x_1,x_2,\dotsc$\@{} On the other hand, the family of $p_i$'s indexed
by the integers~$i\in\bN$ generates the algebra~$\Lambda$ of symmetric
functions over~$\field$: $\Lambda=\field[p_1, p_2,\dotsc]$.
Furthermore, the~$p_i$'s are algebraically independent over~$\bZ$.
Generating series of symmetric functions live in the larger ring of
symmetric series, $\field[t][[p_1,p_2,\dotsc]]$. There, we have the
generating series of homogeneous and elementary functions:
\[
H(t)=\sum_n h_n t^n =\exp\left(\sum_i p_i\frac{t^i}i\right),\qquad
E(t)=\sum_n e_n t^n =\exp\left(\sum_i (-1)^ip_i\frac{t^i}i\right).
\]
We often refer to $H=H(1)$ and $E=E(1)$.
Alternatively, the power notation $\lambda=1^{n_1}\dotsm k^{n_k}$ for
partitions indicates that $i$~occurs $n_i$~times in~$\lambda$,
for~$i=1,2,\dots,k$. The normalization constant
\[
z_\lambda:= 1^{n_1}n_1!\dotsm k^{n_k}n_k!
\]
plays the role of the square of a norm of~$p_\lambda$ in the following important
formula:
\begin{equation}\label{eq:scalp}
\rsc{p_\lambda}{p_\mu}=\delta_{\lambda,\mu}z_\lambda,
\end{equation}
where $\delta_{\lambda,\mu}$~is~1 if $\lambda=\mu$ and 0 otherwise.
The scalar product is a basic tool for coefficient extraction. Indeed,
if we write $F(x_1,x_2,\dotsc)$ in the form~$\sum_\lambda f_\lambda
m_\lambda$, then the coefficient of $x_1^{\lambda_1}\dotsm
x_k^{\lambda_k}$ in~$F$ is $f_\lambda=\rsc F{h_\lambda}$. Moreover,
when $\lambda=1^n$, the identity $h_{1^n}=p_{1^n}$ yields a simple way
to compute this coefficient when $F$ is written in the basis of
the~$p$'s. When viewed at the level of generating series, this fact
gives the following theorem:
\begin{thm}[Gessel\cite{Gessel90}; Goulden \& Jackson\cite{GoJaRe83}]\label{thm:theta}
Let $\theta$ be the $\field$-algebra homomorphism from the algebra
of symmetric functions over~$\field$ to the algebra~$\field[[t]]$ of
formal power series in~$t$ defined by $\theta(p_1)=t$,
$\theta(p_n)=0$ for $n>1$. Then if $F$ is a symmetric function,
\[\theta(F)=\sum_{n=0}^\infty a_n\frac{t^n}{n!},\]
where $a_n$ is the coefficient of $x_1\dotsm x_n$ in~$F$.
\end{thm}
To end our brief recollections of symmetric functions recall that
plethysm is a way to compose symmetric functions. An inner law
of~$\Lambda$, denoted $u[v]$ for $u,v$ in~$\Lambda$, it satisfies the
following rules~\cite{Stanley99}, with $u, v, w\in\Lambda$ and~
$\alpha,\beta$ in~$\field$
\begin{equation*}
(\alpha u+\beta v)[w]=\alpha u[w]+\beta v[w],
\quad
(uv)[w]=u[w]v[w],
\end{equation*}
and if $w=\sum_\lambda c_\lambda p_\lambda$ then
$p_n[w]=\sum_\lambda c_\lambda p_{(n\lambda_1)}p_{(n\lambda_2)}\ldots$.
For example, consider
that $w[p_n]=p_n[w]$, and in particular that $p_n[p_m]=p_{nm}$. In a
mnemonic way:
\[
w[p_n]=w(p_{1n},p_{2n},\dots,p_{kn},\ldots)
\qquad\text{whenever}\qquad
w=w(p_1,p_2,\dots,p_k,\ldots).
\]
\subsection{D-finite multivariate series}
Recall that a series $F\in\field[[x_1,\dots,x_n]]$ is {\em
D-finite\/} in $x_1,\dots,x_n$ when the set of all partial derivatives
and their iterates, $\partial^{i_1+\dots+i_n}F/\partial x_1^{i_1}\dotsm
\partial x_n^{i_n}$, spans a finite-dimensional vector space over the
field $\field(x_1,\dots, x_n)$. A {\em D-finite description\/} of a
series~$F$ is a set of differential equations that
establishes this property. A typical example of such a set is a
system of $n$~differential equations of the form
\[
q_1(x)f(x)+q_2(x)\frac{\partial f}{\partial x_i}(x)+\dots+
q_k(x)\frac{\partial^kf}{\partial x_i^k}(x)=0,
\]
where $i$~ranges over $1,\dots,n$, each~$q_j$ is in $\field(x_1,\dots,x_n)$
for $1\leq j\leq k$, and $k$ and~$q_j$ depend on~$i$.
Such a system is a typical example of a D-finite description of a
functions, and often this will be the preferred form for
manipulating~$f$. In truth we can accept any basis that generates the
vector space of partial derivatives, but in the applications below,
this form is particularly easy to obtain.
\subsection{D-finite symmetric series}
The following definition of D-finiteness of series in an infinite
number of variables is given by Gessel~\cite{Gessel90}, who had
symmetric functions in mind. A series $F\in\field[[x_1,x_2,\dotsc]]$
is {\em D-finite\/} in the $x_i$ if the specialization to 0 of all but
a finite (arbritrary) choice, $S$, of the variable set results in a D-finite
function (in the finite sense). In this case,
many of the properties of the finite multivariate case hold true. One
exception is closure under algebraic substitution, which requires
additional hypotheses.
The definition is then tailored to symmetric series by considering the
algebra of symmetric series as generated over~$\field$ by the set
$\{p_1,p_2,\dotsc\}$: a symmetric series is called {\em D-finite\/}
when it is D-finite in the $p_i$'s\footnote{This is interestingly
enough {\em not\/} equivalent to D-finiteness with respect to either the $h$ or
$e$ basis.}.
\begin{example}
Both $H(t)$ and $E(t)$ are D-finite symmetric functions, as for any
specialization of all but a finite number of the $p_i$'s to 0 results
in an exponential of a polynomial. Similarly, $\exp(h_kt)$ is D-finite
because $h_k=\sum_{\lambda\vdash k} p_\lambda$ is a polynomial in the $p_i$s.
\end{example}
The closure under Hadamard product of D-finite
series~\cite{Lipshitz88} yields the consequence:
\begin{thm}[Gessel]\label{thm:rsc_pres_df}
Let $f$ and $g$ be elements of
$\field[t_1,\dots,t_k][[p_1,p_2,\dotsc]]$, D-finite in the $p_i$'s
and $t_j$'s, and suppose that $g$ involves only finitely many of the
$p_i$'s. Then $\rsc fg$ is D-finite in the $t_j$'s provided it is
well-defined as a power series.
\end{thm}
\subsection{Effective calculation and algorithms}
In our initial study~\cite{ChMiSa05} we gave an algorithm
which, given a D-finite descriptions of two functions satisfying the
hypothesis of Theorem~\ref{thm:rsc_pres_df}, determines a D-finite
description of the series of the scalar product. Henceforth, we shall
refer to this algorithm as~\spa. As we noted in~\cite{ChMiSa05}, a
second algorithm,~\ham, based on the work of Goulden, Jackson and
Reilly~\cite{GoJaRe83} applies in the case when $g=
\exp(h_nt)$, which we shall see is precisely how one can
extract the exponential generating series of sub-classes with
``regularity''. They are implemented in Maple, are are
available for public distribution at the website {\tt
http://www.math.sfu.ca/\verb+~+mmishna}. Maple worksheets illustrating the
calculations presented are also available at that same site.
\section{D-finite symmetric series appear naturally in combinatorics}
Species theory (in the sense of~\cite{BeLaLe98,Joyal81}) is a formalism
for defining and manipulating combinatorial structures that relates
classes to encoding series. An important connection to our work here
is that the series for structures we consider are D-finite symmetric
series, and many of the natural combinatorial actions preserve
D-finiteness on the level of these series.
The reader unfamiliar with species is heartily encouraged to
consult~\cite{BeLaLe98}. A {\em species\/} associates to every set a
family of structures in a way such that two sets of the same
cardinality yield the same family, upto isomorphism. For example, the
species of sets $\sE$ on the underlying set $U$ is simply
$\sE[U]=U$. The species of lists $\sL[U]=\{(x_1, x_2, \dots, x_n):
x_i\in U, n=0,1,2\dots\}$, is the set of finite ordered collections
of elements. The atomic species, $X[U]$ is $U$ if $U$ contains a
single element, and is empty otherwise.
The theory of species develops a rigorous
formalism that allows a sort of calculus of combinatorial
families. For example we construct lists of length 4 from our atomic
species via multiplication: $\sL_4[U]=X^4[U]$.
The key feature that we use are that for every combinatorial family
(species) $\sF$ that one can define, there is an associated cycle
index series $Z_\sF$ and an asymmetric cycle index series~$\Gamma_\sF$,
both of which are symmetric series. Recall for any species \sF its
cycle index series $Z_\sF$ is the series in $\C[\![p_1, p_2,
\ldots]\!]$ given by
\begin{equation}\label{eq:cycle_index}
Z_\sF(p_1, p_2, \ldots)
:=\sum_n\sum\limits_{\lambda\vdash n}\operatorname{Fix} \sF[\lambda]
\frac{p_1^{m_1}p_2^{m_2}\cdots p_k^{m_k}}{z_\lambda},
\end{equation}
%
where the value of $\operatorname{Fix}\sF[\lambda]$ is the
number of structures of $\sF$ that remain fixed under some labelling
permutation of type\footnote{A
permutation of type $(1^{m_1}, 2^{m_2}, \ldots)$ has $m_1$ fixed
points, $m_2$ cycles of length 2, etc.} $\lambda$, and $m_k$ gives
the number of parts of $\lambda$ equal to~$k$.
The definition of the {\em asymmetry index series} of a
species~$\sF$, denoted~$\Gamma_\sF$, as introduced by
Labelle~\cite{BeLaLe98} is related, but more subtle. The
series~$\Gamma$ behaves analytically in much the same way as the
cycle index series, notably, substitution (in almost all cases) is
reflected by plethysm, etc. Essentially, this series counts the objects with no
internal symmetry. Table~\ref{tab:smallspec} contains some small
examples of both series.
\begin{table}[t]
\center
\begin{tabular}{lll|lll}\small
Object&Series&Symmetric function&Object&Series&Symmetric function\\\hline\hline
2-sets&$\Gamma_{\sE_2}$&$e_2=\frac{p_1^2}{2}-\frac{p_2}{2}$&2-multisets&$Z_{\sE_2}$&$h_2=\frac{p_1^2}{2}
+\frac{p_2}{2}$\\
3-sets&$\Gamma_{\sE_3}$&$e_3$ &3-multisets&$Z_{\sE_3}$&$h_3$\\
4-sets&$\Gamma_{\sE_4}$&$e_4$ &4-multisets&$Z_{\sE_4}$&$h_4$\\
$k$-sets &$\Gamma_{\sE_k}$&$e_k$ &$k$-multisets&$Z_{\sE_k}$& $h_k $\\
3-cycles &$Z_{\sC_3}$&$\frac{p_1^3}{3}+\frac{p_3}{3}$ & triples &$Z_{X^3}$&$p_1^3 $\\
4-cycles &$Z_{\sC_4}$&$\frac{p_1^4}{4}+\frac{p_2^2}{12}+\frac{p_4}{12}$& 4-arrays&$Z_{X^4}$&$p_1^4 $\\
5-cycles &$Z_{\sC_5}$&$\frac{p_1^5}{5}+\frac{p_5}{30}$ & 5-arrays& $Z_{X^5}$&$p_1^5 $\\
$k$-cycles &$Z_{\sC_k}$& $\sum_{cd=k} \phi(d)\frac{p_d^c}{k!}$ &
$k$-arrays&$Z_{X^k}$& $p_i^k$\\\hline\hline\\
\end{tabular}\\
\caption{Index series of small species and their corresponding
symmetric functions}
\label{tab:smallspec}
\hrule
\end{table}
In a fashion similar to the cycle index series,~$\Gamma_\sF$ arises
through the enumeration of colorings of asymmetric $\sF$-structures.
A notable example is the species of sets, $\sE$. Recall for any finite
set $U$ we have that $\sE[U]=U$. The two series above turn out to be
$Z_\sE=\exp(\sum_n p_n/n)=\sum_n h_n$
and~$\Gamma_\sE=\exp(\sum_n(-1)^n p_n/n)=\sum_n e_n$.
The primary advantage of this approach, as is true with any generating
series approach, is that natural combinatorial operations (set,
cartesian product, substitution) coincide with straighforward analytic
operations (sum, product, plethystic substitution)\footnote{This is
slightly less true with the asymmetry index series, but true enough for our purposes.}.
The {\em exponential generating series\/} of a species $\sF$ is the
sum $\sF(t)=\sum_n |\sF[n]| \frac{t^n}{n!}$, where $|\sF[n]|$ is the number of
structures of type $\sF$ on a set of size
$n$. The {\em ordinary generating
function}, $\widetilde{\sF}(t)$, is the sum $\sF(t)=\sum_n
\operatorname{Orb}(\sF[n]) t^n$, where $\operatorname{Orb}(\sF[n])$ is
the number structures of $\sF$ on a set of size $n$ distinct up to
relabelling. Also recall the notation $[x^n]f(x)$ refers to the
coefficient of $[x^n]$ in the expansion of $f(x)$. This definition
extends likewise to monomials.
The next result is essentially a collection of known results and basic facts of
D-finite series.
\begin{thm}\label{thm:Dfin_species}
Suppose $\sF$ is a species such that $Z_\sF$ is a
D-finite symmetric series and write $p_n=x_1^n+x_2^n+\ldots$. Then
all of the following series are D-finite with respect to $t$:
\begin{enumerate}
\item The exponential generating function $\sF(t)$;
\item The ordinary generating
function $\widetilde{\sF}(t)$, if the additional condition that $Z_\sF(p_1, p_2, \ldots)$ is D-finite with
respect to the $x_i$ variables is also true;
\item The series $\sum_n \left([x_1^k\cdots
x_n^k]Z_\sF\right) \frac{t^n}{n!}$, for fixed $k$;
\item The series
$\sum_n\sum_{\bar k\in S^n}\left(\left[ x_1^{k_1}x_2^{k_2}\dots
x_n^{k_n}\right] Z_\sF\right) t^n/n!$, for any finite set $S\subset \bN$.
\end{enumerate}
\end{thm}
\begin{pf}
The first two parts are proved using two basic results about cycle
index series:
\begin{equation*}
\sF(t)=Z_\sF(t, 0, 0, \ldots) \quad \text{ and } \quad
\widetilde{\sF}(t)=Z_\sF(t, t^2, t^3, \ldots)
\end{equation*}
The first specialization is well-known to preserve
D-finiteness~\cite{Stanley80} for any $n$.
The additional condition on the second item is sufficient to prove
the D-finiteness since the stated substitution is the same as
$x_1\mapsto t$, and $x_i\mapsto 0$ otherwise.
The third item of the proposition is proved by the expression
\begin{equation*}
\sum_n \left([x_1^k\cdots x_n^k]Z_\sF\right) \frac{t^n}{n!}=\rsc{Z_\sF}{\exp(th_k)},
\end{equation*}
which is D-finite by Theorem~\ref{thm:rsc_pres_df}.
The final item of the proposition is true because the series is equal to
\begin{equation*}
\rsc{Z_\sF}{\exp(t\sum_{i\in S}h_i)},
\end{equation*}
which is also D-finite by Theorem~\ref{thm:rsc_pres_df}.
\end{pf}
We have one large class of species for which the cycle index series is
D-finite. All of our examples come from this class.
\begin{thm}
Let $\sE$ be the species of sets and let~$\sP$ be a polynomial
species with finite support\footnote{Species that
can be written as polynomials of {\em molecular
species}. For example, every species in Table~\ref{tab:smallspec} is
polynomial.}. Then~$\sF=\sE\circ \sP$ describes a species for
which~$Z_\sF$ is a D-finite symmetric series and provided that $\sP(0)=0$,~$\Gamma_\sF$ is also a D-finite symmetric series.
\end{thm}
\begin{proof}
If~$\sP$ is a polynomial species, then its cycle index series is
a polynomial in the $p_i$'s, say $P(p_1, \ldots, p_n)$. Composition of
species is reflected in the cycle index series by plethysm, thus
\[
Z_\sF=\exp(\sum_k p_k/k)[P(p_1, \ldots, p_n)]=\exp\left(\sum P(p_k,
p_{2k},\dots, p_{nk})/k\right).
\]
For any specialization of all but a finite number of $p_i$ to zero,
this gives an exponential of a polynomial, which is clearly
D-finite. Thus, $Z_\sF$ is D-finite. We can similarly show that
$\Gamma_\sF$ is also D-finite under the stated conditions, since the
composition also results in a plethystic composition.
\end{proof}
Our concluding remarks in Section~\ref{sec:conclusion} address the
more general question of combinatorial criteria on a species $\sF$
that ensure that $Z_\sF$ or $\Gamma_\sF$ are D-finite.
\section{Using species to describe regular graph-like structures}
Ultimately our goal is to generalize the well-studied case of $k$-regular
graphs to other structures whose cycle index series are D-finite. To
do so, we express the graph encoding by degree sequence as symmetric
series, and describe how to find such a representation in general
using species theory.
In Eq.~\eqref{eq:allgraphs} we define $G(x_1, x_2, \ldots)$ as
the encoding over all graphs of their degree sequence and we express
this as an infinite product. It turns out that this series is
equivalent to $E[e_2]$, which is equivalent to $\Gamma_{\sE\circ
\sE_2}$. The equivalent series for multigraphs (with loops) is equal
to $H[h_2]=Z_{\sE\circ\sE_2}$, and thus suspecting an explanation via
species, we investigate this connection. Specifically, how do we
construct symmetric function equations to describe the generating
functions of different families of objects, such as hypergraphs.
We begin with the remark that $\sF=\sE\circ\sE_2$ is {\em not\/} the
species of graphs. It is the species of partitions into 2-sets. For
example, $\{\{1,4\},\{2,6\}, \{3,7\},\{5,8\}\}$ is an element
of~$\sF$, and we should not think that this is the graph on 8
vertices, with four edges, rather it just gives the basic structure,
i.e. four edges.
We express the Polya cycle index in the power series
symmetric function. As a series in the symmetric $x_i$
indeterminates, it is an inventory of distinct (non-isomorphic)
colorings of the elements of the species.
For example, the non-isomorphic colorings (by positive
integers, say) of the set $\{a,b\}$ is the set of maps
$\{(a,b)\mapsto(i,j)\in\bN^2: i\leq j\}$, and the inventory of all
such colorings is $\sum_{i\leq j} x_ix_j=h_2$.
A coloring of an element in $\sE\circ\sE_2$ gives rise to a graph
(See Figure~\ref{fig:graph}) and two colorings are isomorphic if one
is a graph relabelling of the other. The monomial encoding a coloring indicates
how many time each color was used, that is, in how many edges the
color appears, that is, the degree of the vertex represented by the
color.
\begin{figure}
\center
\includegraphics[width=5cm]{graph1.eps}
\caption{The graph associated with the colored set partition $\{ \{1_3,4_2\}, \{2_2,6_4\},\{3_4,7_3\},\{5_2,8_1\}\}$}
\label{fig:graph}
\hrule
\end{figure}
We restate this correspondence. The species $\sE\circ\sE_2$ indicates
the structure-- sets of pairs. The cycle index series
$Z_{\sE\circ\sE_2}$ encodes non-isomorphic colorings of elements,
which are in turn equivalent to labelled multi-graphs. The sets of pairs
indicate edges, and the colors indicate vertices.
For many applications, like regular graphs, we would like to count
colorings without repetition. In this case, we do not allow
repetition of a color in a given object, hence to encode a $k$-set,
each color appears exactly once, and this is precisely the notion of
asymmetry in the asymmetry cycle index, and thus we use $\Gamma$
instead of $Z$. Remark,
and thus
\begin{equation*}
\Gamma_{\sE_k} = e_k \quad\text{and thus, } \quad\Gamma_\sE=E.
\end{equation*}
Taking the same species $\sE\circ\sE_2$ as above, and using the
asymmetry index series with a similar argument, we get that
$\Gamma_{\sE\circ\sE_2}=\EE[e_2]$ encodes simple graphs without loops
on the set of colors precisely as is determined by
Eq.~\eqref{eq:allgraphs}: $E[e_2]=\prod_{i