\documentclass{article}
\usepackage[colorlinks=true]{hyperref}
\usepackage{amsthm,amssymb}
\usepackage{psfig,epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
%% \boldmath %--- try3 ! & \mathit or \mathrm [or/and -i in TtH]
\newcommand{\bm}[1]{\mbox{\boldmath{$#1$}}}
\sloppy
\newcommand{\bsq}{\vrule height .9ex width .8ex depth -.1ex}
%\makeatletter
%\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus
% -.2ex}{2.3ex plus .2ex}{\normalsize\bf}}
%\makeatother
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo22.eps}
\vskip 1cm
{\LARGE\bf Some Easily Derivable Integer Sequences}
\vskip 1.5cm
{\large Valery A. Liskovets}\\ \medskip
Institute of Mathematics, National Academy of Sciences,
Surganov str. 11 \\
220072, Minsk, BELARUS\\
\medskip
Email address: \href{mailto:liskov@im.bas-net.by}{liskov@im.bas-net.by}
\vskip2.5cm
\bf {Abstract}
\end{center}
{\em
We propose and discuss several simple ways of obtaining
new enumerative sequences from existing ones. For instance,
the number of graphs considered up to the action of an involutory
transformation is expressible as the semi-sum of
the total number of such graphs and the number of graphs
invariant under the involution.
Another, less familiar idea concerns even- and odd-edged graphs:
the difference between their numbers often proves to be a very
simple quantity (such as $n!$). More than 30 new sequences
will be constructed by these methods.
}
\vspace*{+.1in}
\noindent
{\small\bf Acknowledgement.} {\small This research was
supported by INTAS (Grant INTAS-BELARUS 97-0093).}
\noindent{\small{\bf Mathematics Subject Classification (1991):}
{\rm 05C30, 05A19}}
\tableofcontents
\section{Introduction}\label{B}
New realities set up new tasks. The {\em On-line Encyclopedia
of Integer Sequences}~\cite{Slo99} (in the sequel referred to as
the {\it OEIS}) is a rapidly growing facility, which has been playing
a more and more important role in mathematical research.
To be a
comprehensive reference source, the OEIS
needs to include as many naturally defined sequences as possible.
The efforts of numerous enthusiasts
%% (both professionals and amateurs) and researchers
have been directed towards promoting this aim.
The present work has been motivated by the same
goals.
A fruitful idea is to generate new sequences from known ones.
To implement it, various useful transformations of sequences have
been proposed --- see \cite{BeS95, Cam89, Hel97, Tra98}.
In most cases discussed hitherto, these operations
transform one sequence to another.
Here we consider some other operations
of a similar type but which are less general, producing new enumerative
sequences
for graphs from {\it two}
%% (or more)
other sequences (in most cases, as their semi-sum).
The corresponding relations between the objects being counted
are very simple, and, as a rule, already known.
However, they have
never been analyzed {\it systematically} (this can be partially
explained just by their simplicity: serious researchers rarely
considered them as deserving an independent formulation). As we will
see, our operations do result in new and interesting sequences.
In a sense, they might be considered as already implicitly present in the OEIS.
%% since everybody interested can easily extract them from the corresponding items.
However, they cannot be extracted by a formal rule and thus need to
be presented in the OEIS {\it explicitly}.
At the same time, we should avoid trivial sequences --- not all
new sequences deserve to be added to the OEIS.
We will return
to this question in Section~\ref{F}.
\subsection{Definitions, classes of graphs}\label{G}
In what follows, $n$ denotes the {\it order} of a graph, i.e. the
number of nodes (or vertices). For uniformity, we always start with the case
$n = 1$, and usually $n$ takes all natural values.
In other words, we deal with sequences (or lists) of the form
$[a\,(1), a\,(2), a\,(3), \dots].$\
$N$ denotes the number of edges (in digraphs they are usually called
{\it arcs}) and if there are $n$ nodes and $N$ edges we will sometimes
speak of an $(n,N)$ graph.
$\Phi$ stands for an arbitrary class of graphs, undirected or directed.
Graphs may have loops but not multiple edges (except for planar maps).
The most important specific classes to be considered will be denoted by
the following capital Greek letters, sometimes equipped with a symbolic
subscript:
\begin{itemize}
\item $\Gamma$\quad (simple) undirected graphs
\item $\Gamma_\mathrm{l}$\quad (undirected) graphs with loops, i.e.
symmetric reflexive relations
%% \item $\Gamma_\mathrm{b}$\quad bipartite graphs (with unspecified
%% parts and their sizes),
\item $\Gamma_\mathrm{e}$\quad even (i.e. eulerian) graphs %%3\Xi
\item $\Gamma_\mathrm{m}$\quad median graphs, i.e.
$(n,N)$-graphs with $N = \lceil n(n-1)/4\rceil$ edges
%% with the middle number of edges \lceil \rceil homogeneous
\item $\Gamma_\mathrm{r}$\quad regular graphs with unspecified degrees
\item $\Gamma_\mathrm{t}$\quad (vertex-) transitive graphs
\item $\Gamma_\mathrm{c}$\quad circulant graphs (i.e. Cayley graphs
of cyclic groups)
\item $\Delta$\quad digraphs
\item $\Delta_\mathrm{l}$\quad (binary) relations, i.e. digraphs
with loops
\item $\Delta_\mathrm{e}$\quad balanced digraphs (i.e. eulerian digraphs:
in-degree = out-degree for any vertex)
\item $\Delta_\mathrm{c}$\quad circulant digraphs
\item $\Omega_{}$\quad oriented graphs, i.e. antisymmetric relations
\item $\Theta_{}$\quad tournaments, i.e. complete oriented graphs %4
\item $\Lambda_{}$\quad planar maps (order = \#(edges)). %1
\end{itemize}
\subsection{Enumerative functions\label{N}}
Lower case letters will be used for the cardinalities
(denoted by \#) of subsets of labeled graphs, and the corresponding capital letters
will be used for unlabeled graphs of the same kind.
The most important specific
quantities to be mentioned are the following:
\begin{itemize}
\item $a, A\, =$\, \#(all graphs) in a class $\Phi$
\item $c, C\, =$\, \#(connected graphs)
\item $d, D\, =$\, \#(disconnected graphs)
\item $b, B\, =$\, \#(doubly connected graphs) (both the graph and its complement are connected)
\item $s, S\, =$\, \#(strongly connected digraphs, or strong digraphs)
\item $G\, \, =$\, \#(unlabeled self-complementary undirected graphs)
\item $K\, \, =$\, \#(unlabeled graphs up to complementarity)
\item $f_\mathrm{E}, F_\mathrm{E}\, =$\, \#(graphs with even
number of edges (or arcs)) and
\item $f_\mathrm{O}, F_\mathrm{O}\, =$\, \#(graphs with odd
number of edges (or arcs)), where $f = a, c, \dots, F = A, C, \dots$
\end{itemize}
We denote the corresponding functions for $n$-graphs and $(n,N)$-graphs
by ${f\,(\Phi, n)},\, {F\,(\Phi, n)}$ and
${f\,(\Phi, n, N)},\, {F\,(\Phi, n, N)}$
(or merely $f\,(n),\ f\,(n, N)$, etc. if the class is understood),
where $f$ and $F$ refer to labeled
and unlabeled graphs respectively
The corresponding exponential generating functions (e.g.f.)
for labeled graphs and ordinary generating functions (o.g.f.) for unlabeled graphs
are denoted by
$\mathbf f\,(z)$, $\mathbf f\,(n,x)$, $\mathbf f\,(z,x)$ and
$\mathbf F\,(z)$, $\mathbf F\,(n,x)$, $\mathbf F\,(z,x)$), where
the formal variable $z$ corresponds to $n$ and $x$
corresponds to $N$. In particular, in the labeled case,
$${\mathbf f\,(z,x)\, =\, \sum_{n\geq 1}\mathbf f\,(n,x)\frac{z^n}{n!}}\
=\, \sum_n \sum_N f\,(n,N) x^N \frac{z^n}{n!}$$
%
(so as not to confuse $\mathbf f \, (n,x)$ with
$\mathbf f \,(z,x) |_{z=n}$, the latter expression will not be used here).
We identify any function $f\,(n)$ with the sequence of
its values $[f\,(1), f\,(2), f\,(3), \dots]$.
Sequences in \cite{Slo99} will be referred to by their $A$-numbers.
(Many of these sequences were added as a result of the present paper.)
\section{Subtraction}\label{D}
We begin with the most trivial case: the subtraction method for
calculating objects that do not belong to a given subset of a set.
In principle, this is an inexhaustible source of new sequences,
but we restrict ourselves to several interesting classes,
some of which will be used in what follows. %% immense
\subsection{Disconnection}\label{Dc}
Consider an arbitrary class
of graphs $\Phi$.
Using the above notation,
we have for disconnected labeled graphs,
%
$$ d\,(\Phi,n)\, =\, a\,(\Phi,n)\, -\, c\,(\Phi,n) \eqno(1) $$
%
and for disconnected unlabeled graphs,
%
$$ D\,(\Phi,n)\, =\, A\,(\Phi,n)\, -\, C\,(\Phi,n) \eqno(1*)$$
%
Usually
$c\,(n)$ is expressible in terms of $a\,(n)$ and
$C\,(n)$ in terms of $A\,(n)$, and vice versa, in one of several
ways depending on the labeling type and the repetition restrictions.
See for example the transformations EULERi/EULER/WEIGH for unlabeled graphs
and LOG/EXP for labeled ones~\cite{BeS95,Tra98}.
Therefore $d\,(n)$
(and $D\,(n)$) can usually be expressed solely in terms of $a\,(n)$
{\it or} $c\,(n)$ (resp., in terms of $A\,(n)$ or $C\,(n)$).
In any case, (1) and ($1*$) are much easier for
calculations if both $a\,(n)$ and $c\,(n)$ (resp., $A\,(n)$ and
$C\,(n)$) have already been calculated.
\subsection{Weak and strong digraphs}\label{Wd}
In the directed case (including the case of relations), connected digraphs are
called {\it weakly} connected in order to distinguish them from
{\it strongly} connected ones.
As in Section~\ref{Dc} we may
consider two further quantities: digraphs that are not
strongly connected and (weakly) connected digraphs that are not
strongly connected. Only the latter quantity makes sense for
tournaments, because all tournaments are weakly connected.
Neither notion makes sense for balanced digraphs, in which case
weakly connected digraphs are all strongly connected.
This idea is quite fruitful not only for most of the classes
of digraphs defined above but also for example for {\it semi-regular}
digraphs: ones with the same out-degree at all vertices\footnote{And for abstract {\it automata}~\cite{HaP73} (Sect. 6.5). Fully
defined automata without outputs and initial states are
semi-regular digraphs which may be identified with tuples
of mappings of the set of states to itself~\cite{Lis77}.}.
One further notion, which we will use below (\ref{Sem}), %%(\ref{Std}),
is that of a semi-strong digraph. A digraph is called {\it semi-strong}
if all its weakly connected components are strongly connected
(in particular, strong digraphs are semi-strong). In the unlabeled case,
moreover, one should make a distinction between (at least) two kinds of
semi-strong digraphs: with or without repetitions (i.e. isomorphic
components). Again, using the ordinary enumerative relationship
``connected -- disconnected'', one can easily count semi-strong
digraphs in any class for which the number of strongly connected ones
is known.
In practice, these transformations are less productive since
strongly connected digraphs (especially unlabeled ones) have been
counted only for few types of digraphs (see,
in particular,~\cite{Wri71,Lis73,Lis77});
two of them will be discussed in~\ref{Std}. %%Wri70,
\section{Involutory equivalence}\label{I}
Diverse involutory operations on graphs serve as a source of new
sequences.
\subsection{Complementarity}\label{Co}
Several interesting enumerative sequences are related to the notion of
complementary graph.
Many classes of graphs contain a uniquely defined {\it complete
graph} (for every order). In particular, complete graphs exist
in the families of ordinary undirected graphs $\Gamma$, undirected graphs with
loops $\Gamma_\mathrm{l}$,
directed graphs $\Delta$ and relations $\Delta_\mathrm{l}$.
This notion allows us to introduce the {\it complement} of a graph.
This is the graph on the same vertices
in which the edges are those not in the complete graph.
\subsubsection{Double connection}\label{CC} %% twice
It is clear that the complement of a disconnected graph is connected.
This simple assertion allows us to easily count connected graphs
(of given type $\Phi$) whose complement is also connected {\it and}
belongs to the same class. We call them {\it doubly connected}.
In the labeled case their number
$b\,(\Phi,n)$
is given by
%
$$c\,(\Phi,n)\, =\, {b\,(\Phi,n)\, +\, d\,(\Phi,n)},$$
%
whence by (1),
%
$$ b\,(\Phi,n)\, =\, 2c\,(\Phi,n)\, -\, a\,(\Phi,n). \eqno(2) $$
%
Likewise for unlabeled graphs,
%
$$B\,(\Phi,n)\, =\, 2C\,(\Phi,n)\, -\, A\,(\Phi,n). \eqno(2*)$$
%
Now, for labeled simple undirected graphs,\\
$a\,(\Gamma,n)$\, =\, [1, 2, 8, 64, 1024, 32768, 2097152, \dots]\,
=\, \htmladdnormallink{A006125}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006125}
and \\
$c\,(\Gamma,n)$\, =\, [1, 1, 4, 38, 728, 26704, 1866256, \dots]\,
=\, \htmladdnormallink{A001187}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001187},
resulting in\\
$b\,(\Gamma,n)$\, =\, [1, 0, 0, 12, 432, 20640, 1635360, \dots]
=\, \htmladdnormallink{A054913}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054913}.\\
For labeled digraphs,\\
$a\,(\Delta,n)$\, =\, [1, 4, 64, 4096, 1048576, \dots]
=\, \htmladdnormallink{A053763}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=053763} and \\ %%no A-!
$c\,(\Delta,n)$\, =\, [1, 3, 54, 3834, 1027080, \dots]\, =\,
\htmladdnormallink{A003027}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=003027},
resulting in\\
$b\,(\Delta,n)$\, =\, [1, 2, 44, 3572, 1005584, \dots]
=\, \htmladdnormallink{A054914}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054914}.\\
%% For labeled oriented graphs, \\
%% $a\,(\Omega,n)$\, =\, A047656 \, =\, [1,3,27,729,59049,14348907, \dots]\\
%% $c\,(\Omega,n)$\, =\, A0- \, =\, [1,2,20,624??, \dots] , and\\ %no A-!
%% $b\,(\Omega,n)$ \, =\, ?\dots non-applicable!\\
For unlabeled undirected graphs,\\
%% (ordinary, or simple as they are often called,
%% i.e. without loops and multiple edges),
$A\,(\Gamma,n)$\, =\, [1, 2, 4, 11, 34, 156, 1044, 12346, 274668, \dots]\,
=\, \htmladdnormallink{A000088}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000088}, \\
$C\,(\Gamma,n)$\, =\, [1, 1, 2, 6, 21, 112, 853, 11117, 261080, \dots]\,
=\, \htmladdnormallink{A001349}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001349}, and we obtain\\ %the sequence\\ (=homogeneous)
$B\,(\Gamma,n)$\, =\, [1, 0, 0, 1, 8, 68, 662, 9888, 247492, \dots]
=\, \htmladdnormallink{A054915}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054915}.\\
For unlabeled undirected regular graphs,\\
$A\,(\Gamma_\mathrm{r},n)$\,
=\, [1, 2, 2, 4, 3, 8, 6, 22, 26, 176, \dots]\,
=\, \htmladdnormallink{A005176}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005176},\\
$C\,(\Gamma_\mathrm{r},n)$\,
=\, [1, 1, 1, 2, 2, 5, 4, 17, 22, 167, \dots]\,
=\, \htmladdnormallink{A005177}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005177} and\\
$B\,(\Gamma_\mathrm{r},n)$\,
=\, [1, 0, 0, 0, 1, 2, 2, 12, 18, 158, \dots]
=\, \htmladdnormallink{A054916}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054916}.\\
%% Formerly M0347
For vertex-transitive graphs,\\
$A\,(\Gamma_\mathrm{t},n)$\, =\, [2, 2, 4, 3, 8, 4, 14, 9, 22, \dots]\,
=\, \htmladdnormallink{A006799}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006799},\\
$C\,(\Gamma_\mathrm{t},n)$\, =\, [1, 1, 2, 2, 5, 3, 10, 7, 18, \dots]\,
=\, \htmladdnormallink{A006800}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006800} and\\
$B\,(\Gamma_\mathrm{t},n)$\, =\, [0, 0, 0, 1, 2, 2, 6, 5, 14, \dots]
=\, \htmladdnormallink{A054917}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054917}.\\
For unlabeled digraphs,\\
$A\,(\Delta,n)$\, =\, [1, 3, 16, 218, 9608, 1540944, \dots]\,
=\, \htmladdnormallink{A000273}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000273}, \\
$C\,(\Delta,n)$\, =\, [1, 2, 13, 199, 9364, 1530843, \dots]\,
=\,
\htmladdnormallink{A003085}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=003085} and\\
$B\,(\Delta,n)$\, =\, [1, 1, 10, 180, 9120, 1520742, \dots] =\,
\htmladdnormallink{A054918}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054918}.\\
For unlabeled (reflexive) relations,\\ %(digraphs with loops),\\
$A\,(\Delta_\mathrm{l},n)$\, =\, [2, 10, 104, 3044, 291968, \dots]\,
=\, \htmladdnormallink{A000595}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000595},
therefore, by the EULERi transformation~\cite{Tra98},\\
$C\,(\Delta_\mathrm{l},n)$\, =\, [2, 7, 86, 2818, 285382, \dots]
=\, \htmladdnormallink{A054919}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054919} and\\
$B\,(\Delta_\mathrm{l},n)$\, =\, [2, 4, 68, 2592, 278796, \dots]
=\, \htmladdnormallink{A054920}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054920}.\\
For unlabeled symmetric relations (undirected graphs with loops),\\
$A\,(\Gamma_\mathrm{l},n)$\, =\, [2, 6, 20, 90, 544, 5096, 79264, \dots]\,
=\, \htmladdnormallink{A000666}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000666}, therefore, by the EULERi transformation,\\
$C\,(\Gamma_\mathrm{l},n)$\, =\, [2, 3, 10, 50, 354, 3883, 67994, \dots ]
=\, \htmladdnormallink{A054921}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054921}
and\\ %no A-! ?? 2??
$B\,(\Gamma_\mathrm{l},n)$\, =\, [2, 0, 0, 10, 164, 2670, 56724, \dots]
=\, \htmladdnormallink{A054922}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054922}.
%% For unlabeled oriented graphs (antisymmetric relations),\\
%% $A\,(\Omega,n)$\, =\, A001174 \, = \, [1,2,7,42,582,21480,2142288, \dots]
%% $C\,(\Omega,n)$\, =\, A0- \, = \, [1,1,5,34,?\dots],
Undirected graphs with the median number of edges $\Gamma_\mathrm{m}$
need a slight modification of the present approach. Nothing unusual
arises for orders $n = 4k$ or $4k+1$. However for
$n\equiv 2, 3~ (\mbox {mod } 4)$, the graph and its complement have
{\it different} numbers of edges, namely $\lceil n(n-1)/4\rceil$ and
$\lceil n(n-1)/4\rceil\, - 1$. We will use a prime $'$ in the symbols
for the latter case. Now, in order to count doubly connected median
graphs, one should, instead of doubling $C\,(\Gamma_\mathrm{m},n)$
as in~($2*$), take the sum
${C\,(\Gamma_\mathrm{m},n)} + {C'(\Gamma_\mathrm{m},n)}$.
In other words we have
%% \equiv 0, 1 (\mbox{mod } 4)$
$$ B\,(\Gamma_\mathrm{m},n)\, =\, C\,(\Gamma_\mathrm{m},n)\,
+ C'(\Gamma_\mathrm{m},n)\, -\, A\,(\Gamma_\mathrm{m},n).\eqno(2') $$
%b
Indeed, we have
$C = B + D'$ and $A' = C' + D'$. By definition, $A'$ counts
graphs that are complementary to ones counted by $A$, i.e. $A = A'$.
These equalities give~($2'$).
Numerically, for unlabeled undirected graphs with $n$ nodes and
$N = {\lceil n(n-1)/4\rceil}$ edges,\\
$A\,(\Gamma_\mathrm{m},n)$\,
= \, [1, 1, 1, 3, 6, 24, 148, 1646, 34040, \dots]\, =\, \htmladdnormallink{A000717}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000717},\\
$C\,(\Gamma_\mathrm{m},n)$\,
= \, [1, 1, 1, 2, 5, 22, 138, 1579, 33366, \dots]\, =\, \htmladdnormallink{A001437}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001437}\\
and by the two-parameter table \htmladdnormallink{A054924}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054924},\\
%% (Formerly M1538 and N0601)
%% 1348674,105925685,15968704512,4520384306832,2402814904220039,24256640
%% 21535713098
$C'(\Gamma_\mathrm{m},n)$\,
=\, [1, 0, 0, 2, 5, 19, 132, 1579, 33366, \dots]
=\, \htmladdnormallink{A054926}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054926},
whence\\
$B\,(\Gamma_\mathrm{m},n)$\,
=\, [1, 0, 0, 1, 4, 17, 122, 1512, 32692, \dots] =\,
\htmladdnormallink{A054927}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054927}.
%% Stein. unlab. ]n(n-1)/4[ !? $\lfloor \rfloor =Entier$
Of course, such a generalization can be applied to other similar
classes of graphs (for example, regular of prescribed degree).
\subsubsection{Self-complementarity}\label{Sco}
%% The transformation of a graph to its complement is involutory, and
Next we consider various classes of graphs that are {\it invariant} with respect
to complementarity.
Apart from the classes mentioned in~\ref{CC}, complementarity is
applicable, e.g., to the class of regular graphs of unspecified
degrees $\Gamma_\mathrm{r}$, regular undirected graphs of degree
${(n-1)/2}$ ($n$ odd),
median $n$-graphs for $n(n-1)$ divisible by 4,
undirected eulerian graphs $\Gamma_\mathrm{e}$ of {\it odd} order,
%% vertex-transitive graphs and digraphs, (=homogeneous=eulerian)
balanced digraphs $\Delta_\mathrm{e}$, arbitrary tournaments $\Theta$
and regular tournaments $\Theta_\mathrm{r}$.
On the other hand, e.g., the following classes are not invariant with
respect to complementarity: undirected eulerian graphs of even order,
graphs with one cycle, graphs without 1-valent nodes, regular undirected
graphs of a given degree (not equal to ${(n-1)/2}$), oriented graphs
(except for tournaments), functional digraphs, acyclic digraphs and so on.
For a class of unlabeled graphs $\Phi$ counted
by $A\,(\Phi,n)$,
let $G\,(\Phi,n)$ count {\it self-complementary} graphs
(i.e. graphs isomorphic to their complements). We may ask:
what is the number $K\,(\Phi,n)$ of graphs in $\Phi$ considered
{\it up to complementarity}?
The complement of a graph looks even more natural if one deals with
the pair consisting of a graph and its complement: this
may be interpreted as a complete graph with edges of two
colors. In these terms, $K\,(\Phi,n)$ means the number of
edge-2-colored unlabeled complete graphs whose colors are
{\it interchangeable} and both one-colored edge subgraphs belong
to $\Phi$. The answer to the last question is now very simple:
%% (unordered)
$$K\,(\Phi,n)\, =\, \frac{A\,(\Phi,n)\, +\, G\,(\Phi,n)}{2}.\eqno(3)$$
%
Indeed, every graph appears twice in different pairs
(graph, complement) as the first or second component, except for
the self-complementary graphs, which appear in only one pair.
Each pair presents one graph up to complementarity, so
${2K\,(n)\, =\, A\,(n)\, +\, G\,(n)}$ (cf.~\cite{FrH74}).
This composition can be applied:\\
to undirected graphs, where
$A\,(\Gamma,n)$\, =\, \htmladdnormallink{A000088}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000088} is given above and\\
$G\,(\Gamma,n)$\, =\, [1, 0, 0, 1, 2, 0, 0, 10, 36, \dots]\,
=\, \htmladdnormallink{A000171}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000171}, resulting in the sequence\\
$K\,(\Gamma,n)$\, =\, [1, 1, 2, 6, 18, 78, 522, 6178, 137352, \dots]\,
=\, \htmladdnormallink{A007869}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=007869};\\
to digraphs, where $A\,(\Delta,n)$\, =\, \htmladdnormallink{A000273}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000273} and\\
$G\,(\Delta,n)$\, =\, [1, 1, 4, 10, 136, 720, 44224, \dots]\,
=\, \htmladdnormallink{A003086}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=003086}, resulting in\\
$K\,(\Delta,n)$\, =\, [1, 2, 10, 114, 4872, 770832, \dots] =\, \htmladdnormallink{A054928}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054928};\\
to tournaments, where\\
$A\,(\Theta,n)$\, =\, [1, 1, 2, 4, 12, 56, 456, 6880, 191536, \dots]\,
=\,
\htmladdnormallink{A000568}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000568}
and\\
$G\,(\Theta,n)\, =\, G\,(\Omega,n)$\,
=\,[1, 1, 2, 2, 8, 12, 88, 176, 2752, \dots])\, =\,
\htmladdnormallink{A002785}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=002785},
\, resulting in\\
$K\,(\Theta,n)$\, =\, [1, 1, 2, 3, 10, 34, 272, 3528, 97144, \dots] \,=\,
\htmladdnormallink{A059735}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=059735}; \\
to median $n$-graphs
for $n = 4k$ or $4k+1$ (that is, $n=1, 4, 5, 8, 9\dots$), where\\
$A\,(\Gamma_\mathrm{m},n)$\, =\, [1, 3, 6, 1646, 34040, \dots]\, =\,
the corresponding subsequence of \htmladdnormallink{A000717}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000717} (see~\ref{CC}) and\\
$G\,(\Gamma_\mathrm{m},n)$\, =\, $G\,(\Gamma,n)$\,
=\, [1, 1, 2, 10, 36, \dots] \, =\, \htmladdnormallink{A000171}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000171} without zeros (see above),
resulting in\\
$K\,(\Gamma_\mathrm{m},n)$\, =\, [1, 2, 4, 828, 17038, \dots],\
$n\equiv 0, 1~ (\mbox{mod } 4)$;\\
to circulant graphs, where\\
$A\,(\Gamma_\mathrm{c}, n)$\,
=\, [1, 2, 2, 4, 3, 8, 4, 12, 8, 20, 8, 48, 14, 48, 44, 84, 36, 192, \dots])\,
=\, \htmladdnormallink{A049287}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=049287} and\\
$G\,(\Gamma_\mathrm{c},n)$\,
=\, [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 4, 0, \dots]\,
=\, \htmladdnormallink{A049289}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=049289}, resulting in\\
$K\,(\Gamma_\mathrm{c},n)$\,
=\, [1, 1, 1, 2, 2, 4, 2, 6, 4, 10, 4, 24, 8, 24, 22, 42, 20, 96, \dots] =\, \htmladdnormallink{A054929}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054929};\\
and to circulant digraphs, where\\
$A\,(\Delta_\mathrm{c}, n)$\, =\, [1, 2, 3, 6, 6, 20, 14, 46, 51,
140, 108, \dots]\, =\, \htmladdnormallink{A049297}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=049297} and\\
$G\,(\Delta_\mathrm{c},n)$\, =\, [1, 0, 1, 0, 2, 0, 2, 0, 3, 0, 4, \dots]\,
=\, \htmladdnormallink{A049309}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=049309}, resulting in\\
$K\,(\Delta_\mathrm{c},n)$\,
=\, [1, 1, 2, 3, 4, 10, 8, 23, 27, 70, 56, \dots] =\, \htmladdnormallink{A054930}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054930}.
In the last two cases, $G\,(n)$ differ from the corresponding
sequences in OEIS by additional zeros interspersed
appropriately in order to cover all orders.
One further class of graphs worth mentioning in this respect is that of
bipartite graphs; we refer to~\cite{Qui79} for enumerative results
concerning the function $G$ for such graphs.
In general, this idea can be productively applied to a class
of graphs whenever we know any two
out of the three corresponding sequences.
%% and formula~(3) provides the third sequence.
%% Such is the case, e.g., for unlabeled tournaments
%% (where we have only, as far as I know,\\
%%%to tournaments,\\
%% $A\,(\Theta,n)$\, =\, [1, 1, 2, 4, 12, 56, 456, 6880, 191536, \dots]\,
%% =\, A000568) and for regular undirected graphs with unspecified valency\\
%%% M1262
%%$G\,(\Theta,n)$\, =\, [1, 1, 2, 2, ??, \dots]\, =\, A0?? , %M
%%to homogeneous graphs (with unspecified valency),\\
%% ($A\,(\Gamma_\mathrm{r},n)$\, =\, [1,2,2,4,3,8,6,22,26,176, \dots]\,
%% = \, A005176). %% M0303
%% Nor could I find a class of {\it bipartite} graphs for which both
%% functions $A$ and $G$ (or $A$ and $K$) would be available.
\subsubsection{A combination}\label{Mis} %Misc
Somewhat more artificially we can apply the same approach to
connected graphs, i.e. we consider the number $L\,(n)$ of unlabeled
connected graphs up to complementarity.
Complementarity clearly preserves the subclass of connected graphs
whose complement is also connected. Thus formula~(3) is applicable,
giving rise to ${L\,(n)\, =\, (B\,(n)\, +\, G\,(n))/2}$, where
$B\,(n)$ is determined by formula~($2*$). Thus
%
$$L\,(\Phi,n)\, =\, C\,(\Phi,n)\, -\, \frac{A\,(\Phi,n)\,
-\, G\,(\Phi,n)}{2}. \eqno(4)$$
%
So, for unlabeled undirected connected graphs, we obtain\\
$L\,(\Gamma,n)$\, =\, [1, 0, 0, 1, 5, 34, 331, 4949, 123764, \dots] =\, \htmladdnormallink{A054931}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054931},\\
and for digraphs,\\
$L\,(\Delta,n)$\, =\, [1, 1, 7, 95, 4628, 760731, \dots] =\, \htmladdnormallink{A054932}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054932}.\\
\subsection{Arc reversal}\label{Re}
We can apply the same idea to other involutory transformations.
Consider first the reversal of arcs in digraphs. Now
%
$$K_\mathrm{R}(\Phi,n)\, =\, \frac{A\,(\Phi,n)\,
+\, G_\mathrm{R}(\Phi,n)}{2},\eqno(3\mathrm R)$$
%
where $G_\mathrm{R}$ stands for the number of self-converse digraphs
%% (i.e. ones isomorphic to themselves after reversing the arcs)
and $K_\mathrm{R}$ for the number of (unlabeled) digraphs
considered up to reversing the arcs.
For digraphs, $A\,(\Delta,n)$\, =\, \htmladdnormallink{A000273}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000273} (see~\ref{CC}),\\
$G_\mathrm{R}(\Delta,n)$\, =\, [1, 3, 10, 70, 708, 15224, \dots]\,
=\, \htmladdnormallink{A002499}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=002499} and we obtain\\
$K_\mathrm{R}(\Delta,n)$\, =\, [1, 3, 13, 144, 5158, 778084, \dots]
=\, \htmladdnormallink{A054933}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054933}.\\
For relations, $A\,(\Delta_\mathrm{l},n)$\, =\,
\htmladdnormallink{A000595}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000595},\\
$G_\mathrm{R}(\Delta_\mathrm{l},n)$\,
=\, [2, 8, 44, 436, 7176, 222368, \dots]\, =\,
\htmladdnormallink{A002500}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=002500} and\\
$K_\mathrm{R}(\Delta_\mathrm{l},n)$\,
=\, [2, 9, 74, 1740, 149572, 48575680, \dots]\, =\,
\htmladdnormallink{A029849}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=029849}.\\
For oriented graphs,\\ %$\Omega$,\\
$A\,(\Omega,n)$\, = \, [1, 2, 7, 42, 582, 21480, 2142288, \dots]\,
=\,
\htmladdnormallink{A001174}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001174},\\
$G_\mathrm{R}(\Omega,n)$ =\, [1, 2, 5, 18, 102, 848, 12452, \dots]\,
=\, \htmladdnormallink{A005639}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005639} and we obtain\\
$K_\mathrm{R}(\Omega,n)$\, =\, [1, 2, 6, 30, 342, 11164, 1077370, \dots] =\, \htmladdnormallink{A054934}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054934}.
\subsection{Planar maps}\label{Du} %%Chirality
Equation~(3) has a form which is intrinsic for unlabeled objects
possessing an additional involutory transformation.
Such transformations occur in particular for geometric
and topological objects like planar maps.\footnote
{We notice incidentally that formula~(3) is a particular case
(for the group of order 2) of the result
known as Burnside's Lemma. Formulae~(2)
and~($2*$) are also particular cases of~(3).}
\subsubsection{Duality and reflection}\label{Dua}
The idea can be applied to planar maps (or maps on other
surfaces) with respect to topological duality. %%If denotes
For the number $A\,(\Phi,n)$ of unrooted (= unlabeled) planar maps
with $n$ edges in a class of maps $\Phi$ and the corresponding number
$G_\mathrm{D}(\Phi,n)$ of {\it self-dual} maps, we have, similarly to (3),
%
$$ K_\mathrm{D}(\Phi,n)\, =\, \frac{A\,(\Phi,n)\,
+\, G_\mathrm{D}(\Phi,n)}{2}, \eqno(3\mathrm{D}) $$
%
where $K_\mathrm{D}(\Phi,n)$ denotes the number of unrooted maps
considered {\it up to duality}.
At present,
a formula for $G_\mathrm{D}(\Phi,n)$ seems to be known
in only one case, namely, for the class
$\Phi \, =\, \Lambda$ of all planar maps considered on the sphere with
a distinguished orientation~\cite{Lis85}. In this case,
%
$$ K_\mathrm{D}^+(\Lambda,n)\, =\, \frac{A^+(\Lambda,n)\,
+\, G_\mathrm{D}^+(\Lambda,n)}{2}, \eqno(3\mathrm{D}^+) $$
%
where the superscript $^+$ means enumeration up to
{\it orientation-preserving} transformations. Now,\\
$A^+(\Lambda,n)$\,
=\, [2, 4, 14, 57, 312, 2071, 15030, 117735, 967850, 8268816, \dots]\,
=\, \htmladdnormallink{A006384}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006384} and\\ %%Walsh, M1281
$G_\mathrm{D}^+(\Lambda,n)$\,
=\, [0, 2, 0, 9, 0, 69, 0, 567, 0, 5112, \dots]\,
=\, \htmladdnormallink{A006849}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006849} interspersed with 0s. Hence \\
$K_\mathrm{D}^+(\Lambda,n)$\,
=\, [1, 3, 7, 33, 156, 1070, 7515, 59151, 483925, 4136964, \dots] =\,
\htmladdnormallink{A054935}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054935}.
%% [2, 4, 14, 57, 312, 2071, 15030, 117735, 967850, 8268816
%%+ [0, 2, 0, 9, 0, 69, 0, 567, 0, 5112
%%1/2 1 3 7 33 156 1070 7515 59151 483925 4136964
Instead of duality, let us consider reflections.
We obtain the formula
%
$$ A\,(\Lambda,n)\, =\, \frac{A^+(\Lambda,n)\,
+\, G_\mathrm{ach}(\Lambda,n)}{2}, \eqno(3\mathrm{a}) $$
%
where $G_\mathrm{ach}(\Lambda,n)$ denotes the number of {\it achiral}
maps (i.e. maps isomorphic to their mirror images) considered up to
orientation-preserving isomorphisms. %% (homeomorphisms).
Thus from\\
$A\,(\Lambda,n)$\,
=\, [2, 4, 14, 52, 248, 1416, 9172, 66366, 518868, 4301350, \dots]\,
=\, \htmladdnormallink{A006385}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006385} we have\\
$G_\mathrm{ach}(\Lambda,n)$\,
=\, [2, 4, 14, 47, 184, 761, 3314, 14997, 69886, 333884, \dots] =\,
\htmladdnormallink{A054936}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054936}.
Here it is perhaps more natural to consider maps of the complementary
class, i.e. {\it chiral} maps, i.e.
%
$$G_\mathrm{ch}(\Lambda,n)\, =\, A^+(\Lambda,n)\, - A\,(\Lambda,n)\,
=\, A\,(\Lambda,n)\, -\, G_\mathrm{ach}(\Lambda,n). $$
%
Hence \\
$G_\mathrm{ch}(\Lambda,n)$\,
=\, [0, 0, 0, 5, 64, 655, 5858, 51369, 448982, 3967466, \dots] =\,
\htmladdnormallink{A054937}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054937}.
It would also be interesting to investigate
planar maps with respect to the {\it central symmetry}.
\subsubsection{Circular objects}\label{Nec} %%Necklaces
By circular objects we refer to various classes of geometric figures
defined inside a disk, or, more concretely, inside a convex (regular)
polygon.
Examples are {\it necklaces} (i.e. strings considered up~to rotations),
triangulations of a polygon and other types of dissections
(that is, non-separable outerplanar maps).
Enumerative results for necklaces are well known and widely represented
in the OEIS.
In particular, there are many sequences enumerating
necklaces that can be turned over;
such necklaces are sometimes called {\it bracelets}.
For any type of necklace, the same semi-sum formula
connects three corresponding sequences that enumerate, respectively,
necklaces, bracelets and strings up~to both rotations {\it and}
turning over (i.e. reversal or reflection).
So whenever two
sequences are known, the third can immediately be obtained.
Moreover, just as for maps (see~\ref{Dua}), instead of bracelets
it is sometimes useful to switch to their complementary set,
i.e. to count necklaces that are not isomorphic to their reversals.
Another natural transformation of necklaces is an interchange between
bead colors (or string letters).
Again, if this is an involution (such as the
transposition of two colors), then three appropriate quantities arise
which are connected by the same formula (see~\cite{FrH74}).
Moreover, one may combine this
involution with the reversal and count necklaces up to this combined
transformation as well as those invariant with respect to it.
An unusual instance of the semi-sum formula arises for two-color
necklaces with $2n$ beads in which opposite beads have different colors.
In other words, these are necklaces that are self-dual with respect to
a $180^\circ$ rotation combined with the transposition of the colors.
According to~\cite{PaR84}, the number of such self-dual necklaces is
given by the expression
%
$$ Q\,(n)\, =\, \frac{h\,(n)\, +\, 2^{\lfloor(n-1)/2\rfloor}}{2}, $$
% \eqno(3\mathrm{n})
where
%
$$h\,(n)\, =\, \frac{1}{2n}\sum_{k|n,\ k\ \mathrm{odd}}\phi\,(k)\,2^{n/k}$$
%
involving the Euler totient function $\phi\,(n)$. This is the sequence\\{}
$Q\,(n)\, =\, Q\,(\Psi,n)$\, =\, [1, 1, 2, 2, 4, 5, 9, 12, 23, 34, 63,\dots]\,
=\,
\htmladdnormallink{A007147}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=007147}.
At the same time,\\
$h\,(n)\, =\, h\,(\Theta,n)$\, =\, [1, 1, 2, 2, 4, 6, 10, 16, 30, 52, 94,\dots]\,
=\,
\htmladdnormallink{A000016}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000016}
enumerates so-called vortex-free labeled tournaments (see
in particular~\cite{Knu92}, p.\,14). It is curious to notice that
there is also a sensible shift transformation of $Q\,(n)$: according
to~\cite{BaD98},
%
$$ Q\,(n)\,-\,[n^2/12]\,-\,1 $$
%
enumerates a class of polytopal spheres, where square brackets mean
the nearest integer. Numerically this is\\{} %%-[1, 1, 2, 2, 3, 4, 5, 6, 8, 9, 11,\dots]
[0, 0, 0, 0, 1, 1, 4, 6, 15, 25, 52, \dots] =
\htmladdnormallink{A059736}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=59736}.
Other specific examples of self-dual necklaces can be found, e.g.,
in~\cite{PaR84,Rob81}. Instead of discussing them here, we turn
to an important but less familiar class $\Xi$ of circular object
called chord diagrams. A {\it chord diagram} is a set of chords
between pairwise different nodes lying on an oriented circle.
Chords may intersect and their sets are considered up to an isotopy
transforming the circle to itself.
If no restrictions are imposed, the number of chord diagrams
${A^+(\Xi,n)}$ with $n$ chords and the number of
reversible (achiral) chord diagrams $G_\mathrm{ach}(\Xi,n)$
can easily be evaluated (see details in ~\cite{Sto00,Bar95}).
The corresponding (3a)-type formula has
$A\,(\Xi,n)$ on the left-hand side, where $A\,(\Xi,n)$ denotes
the number of chord diagrams considered up to reflection.
Numerically,\\
$A^+(\Xi,n)$ \,
=\, [1, 2, 5, 18, 105, 902, 9749, 127072, 1915951, \dots]\, =\, \htmladdnormallink{A007769}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=007769}
and\\
$G_\mathrm{ach}(\Xi,n)$\,
=\, [1, 2, 5, 16, 53, 206, 817, 3620, 16361, \dots]\, =\,
\htmladdnormallink{A018191}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=018191},
therefore\\
$A\,(\Xi,n)$\,
=\, [1, 2, 5, 17, 79, 554, 5283, 65346, 966156, \dots] =\, \htmladdnormallink{A054499}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054499}.
So, for the complementary sequence of {\it chiral} chord diagrams
$G_\mathrm{ch}(\Xi,n)\, =\,
{A\,(\Xi,n)\, - \, G_\mathrm{ach}(\Xi,n)}$
we obtain\\
$G_\mathrm{ch}(\Xi,n)$\, =\, [0, 0, 0, 1, 26, 348, 4466, 61726, 949795, \dots] =\,
\htmladdnormallink{A054938}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054938}.
\section{Even- and odd-edged graphs}\label{E}
Consider a specific type of sequence: the numbers $f_\mathrm{E}(n)$
and $f_\mathrm{O}(n)$ of graphs (of a given class with unspecified
numbers of edges) with {\it even} and {\it odd} numbers of
edges. In some non-trivial cases one can easily express both
numbers in terms of the numbers of the corresponding graphs. We use
a formal approach based on generating functions. The formulae
arising in this way are fairly uniform, but require individual
proofs.
The general idea (going back to~\cite{FrH74})
is to evaluate the difference
${f_\mathrm{E}(\Phi,n) - f_\mathrm{O}(\Phi,n)}$
(in other words, this is a weighted enumeration of graphs,
where an $(n,N)$-graph gets the weight $(-1)^N$).
It is clearly equal to $\mathbf{f}\,(\Phi,n,-1)$ and
often turns out to be a very simple function.
%%, therefore $f_\mathrm{E}$ and $f_\mathrm{O}$ are expressed as the semi-sum and
%% half-difference of this sequence with $f$.
%% alternate sum over graph sets.
We also consider analogous sequences $F_\mathrm{E}(n)$ and $F_\mathrm{O}(n)$
for unlabeled graphs, but here fewer results have been obtained.
\subsection{Labeled graphs}\label{Lg}
\subsubsection{Connected graphs}\label{Cog}
For the class $\Gamma$,
%%of labeled connected $n$-graphs with the o.g.f.
as we know, the e.g.f. of the number $c\,(n,N)$ of labeled connected
$(n,N)$-graphs satisfies the equation
%
$$ \mathbf c\,(z,x)\, =\, \log\,(1\, +\, \mathbf a\,(z,x)), $$
%
where the corresponding o.g.f. for $n$-graphs for varying $N$ are
${\mathbf a\,(n,x)\, =\, (1+x)^{n(n-1)/2}}$ and\\
${\mathbf c\,(n,x)\, =\, \sum_N c\,(n,N)x^N}$\
($\Gamma$ is dropped everywhere for simplicity).
Thus ${\mathbf a\,(n, -1)\, =\, 0}$ for $n>1$,
${\mathbf a\,(1, -1)\, =\, 1}$ and ${\mathbf a\,(z, -1)\, =\, z}$.
Hence ${\mathbf c\,(z, -1)\, =\, \log\,(1+z)}$ and
%
$${c_\mathrm{E}(n)\, -\, c_\mathrm{O}(n)}\, =\, \mathbf c\,(n, -1)\,
= \, {-(-1)^{n} (n-1)!}.$$
%
This is {\em Amer. Math. Monthly} problem \#6673, and in~\cite{Sol94} one can find
another proof and a generalization to $k$-component graphs.
We notice also that %%\\
${(-1)^{n-1} (n-1)!}$ is the M\"obius function of the lattice of
set partitions.
Finally, ${c_\mathrm{E}(n)\, +\, c_\mathrm{O}(n)}\, =\, c\,(n)$, hence
%
$$c_\mathrm{E}(\Gamma,n)\,
=\, \frac{c\,(\Gamma,n)\, -\, (-1)^n(n-1)!}{2}$$
%
and
%
$$c_\mathrm{O}(\Gamma,n)\,
=\, \frac{c\,(\Gamma,n)\, +\, (-1)^n(n-1)!}{2}.$$
%
Numerically (with $c\,(\Gamma,n)$\,
=\, [1, 1, 4, 38, 728, 26704, 1866256\dots]\, =\, \htmladdnormallink{A001187}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001187},\\
$c_\mathrm{E}(\Gamma,n)$\, =\, [1, 0, 3, 16, 376, 13292, 933488, \dots]
=\, \htmladdnormallink{A054939}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054939}
and\\
$c_\mathrm{O}(\Gamma,n)$\,
=\, [0, 1, 1, 22, 352, 13412, 932768, \dots]
=\, \htmladdnormallink{A054940}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054940}.
\subsubsection{Connected digraphs}\label{Cod}
The same result is valid for (weakly) connected labeled digraphs
$\Delta$ (see my comment in~\cite{Sol94});
in the proof we need only use the generating function
$(1+x)^{n(n-1)}$ instead of $(1+x)^{n(n-1)/2}$.
\subsubsection{Symmetric relations}\label{Syr}
For the class of graphs with loops $\Gamma_\mathrm{l}$,
the same proof with $(1+x)^{n(n+1)/2}$ instead of $(1+x)^{n(n-1)/2}$
results in ${\mathbf a\,(z, -1)\, =\, 0}$ and
${\mathbf c\,(n, -1)\,=\, 0}$.
Hence
%
$$ c_\mathrm{E}(\Gamma_\mathrm{l},n)\,
=\, c_\mathrm{O}(\Gamma_\mathrm{l},n)\,
=\, c\,(\Gamma_\mathrm{l},n)/2 $$
%
(by complementarity, this is evident for $n\equiv 1, 2~ (\mbox{mod } 4)$).
\subsubsection{Oriented graphs}\label{Org}
For oriented graphs $\Omega$, we work with the polynomials
${\mathbf a\,(n,x)\, =\, (1+2x)^{n(n-1)/2}}$, so that
${\mathbf a\,(n, -1)\, =\, (-1)^{n(n-1)/2}}$.
Now $\mathbf a\,(z, -1)\, =\, {\cos\,(z)\, +\, \sin\,(z) -1}$ and
%
$$\mathbf c\,(\Omega,z, -1)\, =\, \log\,(\cos\,(z)\, +\, \sin\,(z)).$$
%
Therefore\\
${c_\mathrm{E}(\Omega,n)\, -\, c_\mathrm{O}(\Omega,n)}$\, =\,
[1, -2, 4, -16, 80, -512, 3904, -34816, \dots], which is
\htmladdnormallink{A000831}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=000831}
(the expansion of
${(1 + \mbox{tan } x)/(1 - \mbox{tan } x)}$) up to alternating signs.\\
${c_\mathrm{E}(\Omega,n)\, +\, c_\mathrm{O}(\Omega,n)}\,
=\, c\,(\Omega,n)$\, =\, [1, 2, 20, 624, 55248, 13982208, \dots] =\,
\htmladdnormallink{A054941}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054941}.
Thus\\
$c_\mathrm{E}(\Omega,n)$\, =\, [1, 0, 12, 304, 27664, 6990848, \dots] =\,
\htmladdnormallink{A054942}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054942}
and\\
$c_\mathrm{O}(\Omega,n)$\, =\, [0, 2, 8, 320, 27584, 6991360, \dots] =\,
\htmladdnormallink{A054943}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054943}.
%% 3904\, =\, $2^6*61$; 34816\, =\, $2^11*17$;
%% For relations, g_n(x)\, =\, (1+x)^{n^2}.
\subsubsection{Strongly connected digraphs}\label{Std}
\paragraph{Proposition.}
{\it For labeled strong digraphs,}
%
$$s_\mathrm{E}(\Delta,n)\, -\, s_\mathrm{O}(\Delta,n)\,
=\, (n-1)!\,.\eqno(5)$$
%
\medskip
\paragraph{Remark.}
This is the {\em Amer. Math. Monthly} problem~\cite{Pro97}
mentioned earlier without proof in~\cite{Sol94}.
%% to problem \#6673. \#10620 The proof was first obtained by me in 1992.
\paragraph{Proof.}
Let ${s\,(n,N)=s\,(\Delta,n,N)}$.
The left-hand difference in (5) is $\mathbf s\,(n, -1)$.
According to~\cite{Lis73} (cf. also~\cite{Wri71}),
%
$$ \mathbf s\,(z,x)\, =\, -\,\log\,(1\, -\, \mathbf v\,(z,x)), $$
%% \eqno( )
%
where
${\mathbf v\,(z,x)\, =\, \sum_{n\geq 1} \mathbf v\,(n,x)z^n/n!}$,\
${\mathbf v\,(n,x)\, =\, \mathbf a\,(n,x)\,\mathbf u\,(n,x)}$,\
${\mathbf a\,(n,x)\, =\, (1+x)^{n(n-1)/2}}$,\\
${\mathbf a\,(z,x)\,
=\, {\sum_{n\geq 1} \mathbf a\,(n,x)z^n/n!}}$
(hence ${a\,(n,N)\, =\, a\,(\Gamma,n,N)}$ is the number of all
labeled undirected graphs) and
%
$$\mathbf u\,(z,x)\, =\, \sum_{n\geq 1} \mathbf u\,(n,x) \frac{z^n}{n!}\,
=\, 1\, -\, \frac{1}{1 + \mathbf a\,(z,x)}. \eqno(6)$$
%
As we saw in~\ref{Cog}, ${\mathbf a\,(n, -1)\, =\, 0}$ for $n>1$.
Moreover, ${\mathbf a\,(1, -1)}\, =\, {\mathbf u\,(1, -1)\, =\, 1}$.
Therefore\\
${\mathbf v\,(z, -1)\, =\, z}$, whence
${\mathbf s\,(z,-1)\, =\, -\log\,(1-z)}$
and ${\mathbf s\,(n, -1)\, =\, (n-1)!}$.~~~$\bsq$
\medskip
Different proofs can be found in~\cite{Sol00}.
\paragraph{Corollary.}
%
$$ s_\mathrm{E}(\Delta,n)\, =\, \frac{s\,(\Delta,n)\, +\, (n-1)!}{2} $$
%
{\it and}
%
$$ s_\mathrm{O}(\Delta,n)\, =\, \frac{s\,(\Delta,n)\, -\, (n-1)!}{2}.$$
%
\medskip
Thus, from $s\,(\Delta,n)$\, =\,
[1, 1, 18, 1606, 565080, \dots]\, =\,
\htmladdnormallink{A003030}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=003030}, we obtain\\
$s_\mathrm{E}(\Delta,n)$\, =\, [1, 1, 10, 806, 282552, \dots] =\,
\htmladdnormallink{A054944}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054944} and \\
$s_\mathrm{O}(\Delta,n)$\, =\, [0, 0, 8, 800, 282528, \dots] =\,
\htmladdnormallink{A054945}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054945}.
Let
%
$$v\,(n)\, =\, v\,(\Delta,n)\, =\, 2^{n(n-1)/2}u\,(n),$$
%
where the e.g.f. $\mathbf u\,(z)\, =\, {1\, -\, 1/(1 + \mathbf a\,(z))}$
and $\mathbf a\,(z)\, =\, {\sum_{n\geq 1} 2^{n(n-1)/2}z^{n}/n!}$.
It is known that $u\,(n)$ enumerates strong labeled tournaments
(see, e.g.,~\cite{HaP73}, (5.2.4)).
So this is the sequence\\
%% see also~\cite{Lis73} or~\cite{Wri70}).
$u\,(n)\, =\, s\,(\Theta,n)$\,
=\, [1, 0, 2, 24, 544, 22320, 1677488, \dots] =\,
\htmladdnormallink{A054946}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054946}.
The factors $2^{n(n-1)/2}$ form the sequence\\
$a\,(\Gamma,n) = a\,(\Theta,n)$\,
=\, [1, 2, 8, 64, 1024, 32768, 2097152, \dots]\, =\, \htmladdnormallink{A006125}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006125}. Thus\\
%% 1 2 8 64 1024 32768 2097152 A006125 2^{n(n-1)/2}.
%% x 1 0 2 24 544 22320 1677488
%% v 1 0 16 1536 557056 731381760
$v\,(n)$\, =\, [1, 0, 16, 1536, 557056, 731381760, \dots] =\,
\htmladdnormallink{A054947}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054947}.
\subsubsection{A digression: semi-strong digraphs}\label{Sem}
As we pointed out in~\cite{Lis73},
$v\,(n)\, =\, {s^\mathrm{O}(\Delta,n)\, -\, s^\mathrm{E}(\Delta,n)}$,
where $s^\mathrm{E}(\Delta,n)$ and $s^\mathrm{O}(\Delta,n)$
are the numbers of semi-strong digraphs (see~\ref{Wd}) with an even
and odd {\it number of components}. Moreover, \\
${s^\mathrm{O}(\Delta,n)\, +\, s^\mathrm{E}(\Delta,n)\,
=\, s^\mathrm{W}(\Delta,n)}$, where $s^\mathrm{W}(\Delta,n)$
denotes the number of labeled semi-strong digraphs, which is
easily expressed via $s\,(\Delta,n)$ by the EXP
transformation~\cite{BeS95,Tra98}. This provides a way to evaluate
$s^\mathrm{E}(\Delta,n)$ and $s^\mathrm{O}(\Delta,n)$. Specifically, \\
$s^\mathrm{W}(\Delta,n)$\, =\, [1, 2, 22, 1688, 573496, 738218192, \dots] =\,
\htmladdnormallink{A054948}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054948},\\
$s^\mathrm{O}(\Delta,n)$\, =\, [1, 1, 19, 1612, 565276, 734799976, \dots] =\,
\htmladdnormallink{A054949}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054949}
and \\
$s^\mathrm{E}(\Delta,n)$\, =\, [0, 1, 3, 76, 8220, 3418216, \dots] =\,
\htmladdnormallink{A054950}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054950}.
There is a similar
formula for the corresponding odd-even difference for unlabeled
semi-strong digraphs with {\it mutually non-isomorphic components}:
$V\,(n)\, =\, {S^\mathrm{O}(\Delta,n)\, -\, S^\mathrm{E}(\Delta,n)}$.
This alternating sum plays a key role in the enumeration of unlabeled
strongly connected digraphs~\cite{Lis73}: \\
$1 - \sum_n V\,(n)z^n = \prod_n (1-z^n)^{S\,(\Delta,n)}$.
From these formulae one can extract
$S^\mathrm{E}(\Delta,n)$ and $S^\mathrm{O}(\Delta,n)$.
First we need to evaluate $V\,(n)$. In~\cite{Lis73} we gave
a direct (though difficult) formula and numerical data for the corresponding
two-parametric function $V\,(n,N)$.
But now we may proceed in
the opposite direction, using the above expression and known values of
$S\,(\Delta,n)$. Numerically, \\
$S\,(\Delta,n)$\, =\, [1, 1, 5, 83, 5048, 1047008, \dots]\, =\,
\htmladdnormallink{A035512}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=035512},
whence we evaluate\\
$V\,(n)$\, =\, [1, 1, 4, 78, 4960, 1041872, \dots] =\, \htmladdnormallink{A054951}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054951}.
%%! 78=83-5-0+0; 4960=5048-83-5-0+0; 1041872=1047008-5048-83-10!+5!-0+0
Now ${S^\mathrm{O}(\Delta,n)\, +\, S^\mathrm{E}(\Delta,n)\,
=\, S^\mathrm{W}(\Delta,n)}$, the number of semi-strong digraphs with
pairwise different components. We have
${1 + \sum_n S^\mathrm{W}(\Delta,n)z^n} = {\prod_n (1+z^n)^{S\,(\Delta,n)}}$
(this series corresponds to the WEIGH
transformation~\cite{BeS95,Cam89,Tra98}). Therefore \\
$S^\mathrm{W}(\Delta,n)$\, =\, [1, 1, 6, 88, 5136, 1052154, \dots] =\,
\htmladdnormallink{A054952}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054952}.
Thus\\
%% (again as a semi-sum and half-difference),
$S^\mathrm{O}(\Delta,n)$\, =\, [1, 1, 5, 83, 5048, 1047013, \dots] =\, \htmladdnormallink{A054953}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054953} and \\
$S^\mathrm{E}(\Delta,n)$\, =\, [0, 0, 1, 5, 88, 5141, \dots] =\,
\htmladdnormallink{A054954}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054954}.
Evidently, other types of disconnected (di)graphs, labeled or unlabeled,
specified by the parity of the number of components are also
worth considering.
\subsubsection{Eulerian digraphs}\label{Eud}
The next assertion is new.
\paragraph{Proposition.}
{\it For labeled balanced digraphs,
%
$$ a_\mathrm{E}(\Delta_\mathrm{e},n)\,
=\, \frac{a\,(\Delta_\mathrm{e},n)\,+\,n!}{2} \eqno(7_\mathrm{E}) $$
%
and
%
$$ a_\mathrm{O}(\Delta_\mathrm{e},n)\,
=\, \frac{a\,(\Delta_\mathrm{e},n)\,-\,n!}{2}. \eqno(7_\mathrm{O}) $$
%
For labeled Eulerian
(i.e. connected balanced)
digraphs,
%
$$c_\mathrm{E}(\Delta_\mathrm{e},n)\,
=\, \frac{c\,(\Delta_\mathrm{e},n)\,+\,(n-1)!}{2} \eqno(8_\mathrm{E})$$
%
and
$$c_\mathrm{O}(\Delta_\mathrm{e},n)\,
=\, \frac{c\,(\Delta_\mathrm{e},n)\,-\,(n-1)!}{2}. \eqno(8_\mathrm{O})$$
%
}
\medskip
\paragraph{Proof.}
According to Theorem 2 of~\cite{Lis71}, the o.g.f.
$\mathbf a\,(\Delta_\mathrm{e},n,x)$ of balanced digraphs can be
expressed by a formula in terms of $m$-roots of unity, $m\geq n$.
Choosing $m\, =\, n$, and putting $\, x:=\, -1$, we have from that formula,
%
$$ \mathbf a\,(\Delta_\mathrm{e},n, -1)\,
=\, n^{-n}n!\prod\limits_{1\leq k\neq l\leq n}(1\, -\, w^{k-l}), $$
%
where $w$ is a primitive $n$-root of unity.
Thus
%
$$\mathbf a\,(\Delta_\mathrm{e},n, -1)\, =\,
n^{-n}n!\prod\limits_{r=1}^n(1\, -\, w^r)^n.$$
%
But ${\prod_{r}(1-w^r)\, =\, n}$, since this is merely
the polynomial ${(z^n-1)/(z-1)}$ evaluated at $z\, =\, 1$. Thus,
%
$${\mathbf a\,(\Delta_\mathrm{e},n, -1)\, =\, n!}$$
%
This implies formulae~($7_\mathrm{E}$) and~($7_\mathrm{O}$).
Now, for connected balanced digraphs,
${c_\mathrm{E}(\Delta_\mathrm{e},n)\,
-\, c_\mathrm{O}(\Delta_\mathrm{e},n)\, }
=\, {\mathbf c\,(\Delta_\mathrm{e},n, -1)}$.
As usual, ${\mathbf c\,(\Delta_\mathrm{e},z,x)\,
=\, \log\,(1\, +\, \mathbf a\,(\Delta_\mathrm{e},z,x))}$.
By the above formulae,
${\mathbf a\,(\Delta_\mathrm{e},z, -1)\, =\, z/(1-z)}$, thus we have\\
${\log\,(1 + z/(1-z))}\, =\, {\sum_{n\geq 1}z^n/n}$ and
${\mathbf c\,(\Delta_\mathrm{e},n, -1)\, =\, (n-1)!}$.~~~$\bsq$
Numerically we obtain the following sequences: \\
%% (that slightly differ from the known ones):\\
%% according to~\cite{McK83},\\
$a\,(\Delta_\mathrm{e},n)$\, =\, [1, 2, 10, 152, 7736, 1375952, \dots]\,
=\,
\htmladdnormallink{A007080}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=007080} whence by~($7_\mathrm{E}$), \\
$a_\mathrm{E}(\Delta_\mathrm{e},n)$\,
=\, [1, 2, 8, 88, 3928, 688336, \dots] =\,
\htmladdnormallink{A054955}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054955},
and by~($7_\mathrm{O}$),\\
$a_\mathrm{O}(\Delta_\mathrm{e},n)$\,
=\, [0, 0, 2, 64, 3808, 687616, \dots] =\,
\htmladdnormallink{A054956}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054956}.
Now (by the LOG transformation),\\
$c\,(\Delta_\mathrm{e},n)$\, =\, [1, 1, 6, 118, 7000, 1329496, \dots] =\,
\htmladdnormallink{A054957}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054957}
so that\\
$c_\mathrm{E}(\Delta_\mathrm{e},n)$\,
=\, [1, 1, 4, 62, 3512, 664808, \dots] =\,
\htmladdnormallink{A054958}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054958}
and\\
$c_\mathrm{O}(\Delta_\mathrm{e},n)$\,
=\, [0, 0, 2, 56, 3488, 664688, \dots] =\,
\htmladdnormallink{A054959}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054959}.
\subsection{Unlabeled graphs}\label{Ug}
Here we restrict ourselves to one class of graphs, $\Gamma$
(but compare also~\ref{Sem}). Consider the difference
${A_\mathrm{E}(\Gamma,n)\, -\, A_\mathrm{O}(\Gamma,n)}$.
This is clearly the value at $x\, =\, -1$ of the corresponding o.g.f.
%% by the number of edges $N$:
${\mathbf A\,(\Gamma,n,x)\, =\, {\sum_N A\,(\Gamma,n,N)x^N}}$.
According to the P\'olya enumeration theorem
(see for example ~\cite{HaP73}, (4.1.8)),
%
$$\mathbf A\,(\Gamma,n,x)\,
=\, \mathbf Z\,(\mathrm S_n^{(2)}, 1+x, 1+x^2, \dots),$$
%
where $\mathbf Z\,(\mathrm S_n^{(2)},z_1,z_2, \dots)$ denotes the cycle
index of the symmetric group $\mathrm S_n$ in its induced action on
the 2-subsets of vertices. Thus
%
$$ A_\mathrm{E}(\Gamma,n)\, -\, A_\mathrm{O}(\Gamma,n)\,
=\, \mathbf Z\,(\mathrm S_n^{(2)}, 0, 2, 0, 2, \dots). \eqno(9) $$
%
We see that the right-hand side coincides with the formula
(6.2.3) in~\cite{HaP73} for the number $G\,(\Gamma,n)$
of self-complementary graphs. Thus~\cite{Sol96},
${A_\mathrm{E}(\Gamma,n)\, -\, A_\mathrm{O}(\Gamma,n)\,
=\, G\,(\Gamma,n)}$. But\\
${A_\mathrm{E}(\Gamma,n)\, +\, A_\mathrm{O}(\Gamma,n)\,
=\, A\,(\Gamma,n).}$ Therefore
%
$$ A_\mathrm{E}(\Gamma,n)\, =\, \frac{A\,(\Gamma,n)\, +\,
G\,(\Gamma,n)}{2} \eqno(10_\mathrm{E}) $$
%
and
%
$$A_\mathrm{O}(\Gamma,n)\, =\, \frac{A\,(\Gamma,n)\,
-\, G\,(\Gamma,n)}{2}.\eqno(10_\mathrm{O})$$
%
So, comparing formulae~($10_\mathrm{E}$) and~(3), we obtain the
following identity:
%
$$ A_\mathrm{E}(\Gamma,n)\, =\, K\,(\Gamma,n). $$
%
We note also that ${A_\mathrm{E}(\Gamma,n)\, =\, A_\mathrm{O}(\Gamma,n)}\
=\, A\,(\Gamma,n)/2$ if $n = 4k+2$ or $4k+3$.
From the numerical data for $A\,(\Gamma,n)$ and $G\,(\Gamma,n)$
(or, instead, $K\,(\Gamma,n)$) presented in~\ref{CC}, one gets\\
%% $A\,(\Gamma,n)$ = [1, 2, 4, 11, 34, 156, 1044, 12346, 274668] = A000088
%% $G\,(\Gamma,n)$ = [1, 0, 0, 1, 2, 0, 0, 10, 36] = A000171
%% $K\,(\Gamma,n)$ = [1, 1, 2, 6, 18, 78, 522, 6178, 137352] = A007869
%% O 0, 1, 2, 5, 16, 78, 522, 6168, 137316
%% E 1, 1, 2, 6, 16, 78, 522, 6168, 137316
$A_\mathrm{O}(\Gamma,n)$\,
=\, [0, 1, 2, 5, 16, 78, 522, 6168, 137316, \dots] =\,
\htmladdnormallink{A054960}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=054960}.
Similar assertions are valid for arbitrary digraphs and some other
classes of graphs.
%% $S\,(\Delta,n)$\, =\, [1, 1, 5, 83, 5048, 1047008, \dots]\, =\, A035512
\section{Concluding remark}\label{F}
%% In conclusion, several mainly speculative or negative notes.
In principle, there is an easy
way to obtain numerous new sequences from known ones.
Namely, if $a\,(n)$ and $b\,(n)$ count objects of two types,
then of course their product $a\,(n)b\,(n)$ counts ordered pairs
of objects, and their sum $a\,(n)\, +\, b\,(n)$ counts objects of
their disjoint union.
As a rule this can hardly be considered
as a really fruitful idea: in general, such pairs and the union are
unnatural. But sometimes, the term-by-term product (and,
still more often, the sum) of two sequences turns out to have
a natural interpretation, though possibly unexpected.
In this work we encountered various sequences that can be presented as
the semi-sum or sum of two other sequences. Only one sequence
(namely, $v\,(n)$ in~\ref{Std}) was presented as the product of
two sequences (one of which is, moreover, primitive).
Several more such examples can be found in~\cite{KLW99}.
As far as I know, no systematic investigations of such meaningful
operations has been undertaken so far.
%% Switch classes?!
%% are merely powers of 3.
%% See also~\ref{Std}
\bibstyle{plain}
\begin{thebibliography}{xx}
%
%
\bibitem{BaD98} B.\,Bagchi and B.\,Datta, A structure theorem for
pseudomanifolds, {\it Discr. Math.}, {\bf 188} (1998), 41--60.
\bibitem{Bar95} D.\,Bar-Natan, On the Vassiliev knot invariants,
{\it Topology}, {\bf 34} (1995), 423--472.
\bibitem{BeC83} E.\,A.\,Bender and E.\,R.\,Canfield, Enumeration of
connected invariant graphs, {\it J. Combin. Th.}, {\bf B34} (1983),
268--278.
\bibitem{BeS95} M.\,Bernstein and N.\,J.\,A.\,Sloane,
\href{http://www.research.att.com/~njas/doc/eigen.pdf}{Some canonical sequences of integers}, {\it Linear Alg. \& Its Appl.},
{\bf 226--228} (1995), 57--72.
%
%%\bibitem{Cam87} P.\,J.\,Cameron, Some treelike objects,
%% {\it Quart. J. Math. Oxford}, {\bf 38} (1987), 155--183.
%
\bibitem{Cam89} P.\,J.\,Cameron, Some sequences of integers,
{\it Discr. Math.}, {\bf 75} (1989), 89--102.
%
%%\bibitem{Cam96} P.\,J.\,Cameron, Stories about groups and sequences,
%% {\it Designs, Codes \& Crypt.}, {\bf 8} (1996), 109--134.
%
\bibitem{FrH74} R.\,Frucht and F.\,Harary, Self-complementary
generalized orbits of a permutation group, {\it Canad. Math. Bull.},
{\bf 17} (1974), 203--208.
\bibitem{HaP73} F.\,Harary, E.\,M.\,Palmer, {\it Graphical
Enumeration}, Acad.Press, N.Y. (1973).
%
\bibitem{Knu92} D.\,E.\,Knuth. {\it Axioms and Hulls.}
Lect. Notes Comput. Sci., {\bf 606}, Sprin\-ger-Verlag, Berlin (1992).
\bibitem{KLW99} L.\,M.\,Koganov, V.\,A.\,Liskovets and
T.\,R.\,S.\,Walsh, Total vertex enumeration in rooted planar
maps, {\it Ars Combin.} {\bf 54} (2000), 149--160.
%
\bibitem{Lis71} V.\,A.\,Liskovets, On the number of Eulerian digraphs
and homogeneous tournaments, {\it Vesci AN BSSR}
(ser. fiz.-mat. n.), No 1 (1971), 22--27 (in Russian).
%
\bibitem{Lis73} V.\,A.\,Liskovets, A contribution to the enumeration
of strongly connected digraphs, {\it Dokl. AN BSSR}, {\bf 17},
No 12 (1973), 1077--1080 (in Russian).
%
\bibitem{Lis77} V.\,A.\,Liskovets, On a general enumerative scheme for
labeled graphs, {\it Dokl. AN BSSR}, {\bf 21},
No 6 (1977), 496--499 (in Russian).
%
\bibitem{Lis85} V.\,A.\,Liskovets, Enumeration of nonisomorphic planar
maps, {\it Selecta Math. Soviet.}, {\bf 4} (1985), 304--323.
%
%%\bibitem{McK83} B.\,D.\,McKay, Applications of a technique for
%% labelled enumeration, {\it Congr. Numer.}, {\bf 40} (1983), 207--221.
%
\bibitem{PaR84} E.\,M.\,Palmer and R.\,W.\,Robinson,
Enumeration of self-dual configurations, {\it Pacif. J. Math.},
{\bf 110} (1984), 203--221.
\bibitem{Pro97} J.\,Propp, Problem \#10620, {\it Amer. Math. Monthly},
{\bf 104} (1997), 870.
%
\bibitem{Qui79} S.\,J.\,Quinn, Factorisation of complete bipartite
graphs into two isomorphic subgraphs, {\it Combinatorial Mathematics
VI} (A.\,Horadam and W.\,D.\,Wallis eds.), {\it Lect. Notes in Math.},
{\it 748}, Springer, Berlin (1979), 98--111.
\bibitem{Rob81} R.\,W.\,Robinson, Counting graphs with a duality property,
{\it Combinatorics} (Proc. 8th Brit. Comb. Conf., Swansea, 1981),
{\it Lond. Math. Soc. Lect. Notes Ser.}, {\bf 52} (1981), 156--186.
\bibitem{Slo99} N.\,J.\,A.\,Sloane, {\it The On-Line Encyclopedia of
Integer Sequences}, published electronically at
\href{http://www.research.att.com/~njas/sequences/}{http://www.research.att.com/$\sim$njas/sequences/}
\bibitem{Hel97} N. J. A. Sloane,
\href{http://www.research.att.com/~njas/sequences/superhelp.html}
{Help File for Superseeker},
{\it a sub-page of}~\cite{Slo99} (1999).
\bibitem{Tra98} N. J. A. Sloane,
\href{http://www.research.att.com/~njas/sequences/transforms.txt}
{Transformations of Integer Sequences},
{\it a sub-page of}~\cite{Slo99} (2001).
\bibitem{SlP95} N.\,J.\,A.\,Sloane and S.\,Plouffe, {\it The
Encyclopedia of Integer Sequences}, Academic Press, San Diego (1995).
%
\bibitem{Sol94} Solution of problem \#6673, {\it Amer. Math. Monthly},
{\bf 101} (1994), 686--687.
%
\bibitem{Sol96} Solution of problem \#10285, {\it Amer. Math.
Monthly}, {\bf 103} (1996), 268--269.
%
\bibitem{Sol00} Solution of problem \#10620, {\it Amer. Math.
Monthly} {\bf 106} (1999), 865--867.
%
\bibitem{Sto00} A.\,Stoimenow, On the number of chord diagrams,
{\it Discr. Math.} {\bf 218} (2000), 209--233.
%% \bibitem{Wri70} E.\,M.\,Wright, The number of irreducible
%% tournaments, {\it Glasgow Math. J.}, {\bf 10} (1970), 97--101.
%
\bibitem{Wri71} E.\,M.\,Wright, The number of strong digraphs,
{\it Bull. London Math. Soc.}, {\bf 3} (1971), 348--350.
%
\end{thebibliography}
\vspace*{+.5in}
\centerline{\rule{6.5in}{.01in}}
\vspace*{+.1in}
\noindent
{\small
(Concerned with sequences
\htmladdnormallink{A000016}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000016}
\htmladdnormallink{A000088}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000088}
\htmladdnormallink{A000171}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000171}
\htmladdnormallink{A000273}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000273}
\htmladdnormallink{A000568}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000568}
\htmladdnormallink{A000595}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000595}
\htmladdnormallink{A000666}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000666}
\htmladdnormallink{A000717}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000717}
\htmladdnormallink{A000831}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A000831}
\htmladdnormallink{A001174}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001174}
\htmladdnormallink{A001187}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001187}
\htmladdnormallink{A001349}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001349}
\htmladdnormallink{A001437}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001437}
\htmladdnormallink{A002499}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002499}
\htmladdnormallink{A002500}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002500}
\htmladdnormallink{A002785}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002785}
\htmladdnormallink{A003027}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A003027}
\htmladdnormallink{A003030}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A003030}
\htmladdnormallink{A003085}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A003085}
\htmladdnormallink{A003086}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A003086}
\htmladdnormallink{A005176}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005176}
\htmladdnormallink{A005177}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005177}
\htmladdnormallink{A005639}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A005639}
\htmladdnormallink{A006125}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006125}
\htmladdnormallink{A006384}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006384}
\htmladdnormallink{A006385}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006385}
\htmladdnormallink{A006799}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006799}
\htmladdnormallink{A006800}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006800}
\htmladdnormallink{A006849}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A006849}
\htmladdnormallink{A007080}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A007080}
\htmladdnormallink{A007147}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A007147}
\htmladdnormallink{A007769}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A007769}
\htmladdnormallink{A007869}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A007869}
\htmladdnormallink{A018191}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A018191}
\htmladdnormallink{A029849}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A029849}
\htmladdnormallink{A035512}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A035512}
\htmladdnormallink{A049287}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A049287}
\htmladdnormallink{A049289}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A049289}
\htmladdnormallink{A049297}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A049297}
\htmladdnormallink{A049309}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A049309}
\htmladdnormallink{A053763}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A053763}
\htmladdnormallink{A054499}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054499}
\htmladdnormallink{A054913}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054913}
\htmladdnormallink{A054914}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054914}
\htmladdnormallink{A054915}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054915}
\htmladdnormallink{A054916}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054916}
\htmladdnormallink{A054917}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054917}
\htmladdnormallink{A054918}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054918}
\htmladdnormallink{A054919}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054919}
\htmladdnormallink{A054920}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054920}
\htmladdnormallink{A054921}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054921}
\htmladdnormallink{A054922}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054922}
\htmladdnormallink{A054924}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054924}
\htmladdnormallink{A054926}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054926}
\htmladdnormallink{A054927}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054927}
\htmladdnormallink{A054928}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054928}
\htmladdnormallink{A054929}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054929}
\htmladdnormallink{A054930}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054930}
\htmladdnormallink{A054931}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054931}
\htmladdnormallink{A054932}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054932}
\htmladdnormallink{A054933}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054933}
\htmladdnormallink{A054934}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054934}
\htmladdnormallink{A054935}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054935}
\htmladdnormallink{A054936}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054936}
\htmladdnormallink{A054937}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054937}
\htmladdnormallink{A054938}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054938}
\htmladdnormallink{A054939}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054939}
\htmladdnormallink{A054940}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054940}
\htmladdnormallink{A054941}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054941}
\htmladdnormallink{A054942}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054942}
\htmladdnormallink{A054943}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054943}
\htmladdnormallink{A054944}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054944}
\htmladdnormallink{A054945}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054945}
\htmladdnormallink{A054946}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054946}
\htmladdnormallink{A054947}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054947}
\htmladdnormallink{A054948}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054948}
\htmladdnormallink{A054949}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054949}
\htmladdnormallink{A054950}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054950}
\htmladdnormallink{A054951}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054951}
\htmladdnormallink{A054952}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054952}
\htmladdnormallink{A054953}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054953}
\htmladdnormallink{A054954}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054954}
\htmladdnormallink{A054955}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054955}
\htmladdnormallink{A054956}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054956}
\htmladdnormallink{A054957}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054957}
\htmladdnormallink{A054958}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054958}
\htmladdnormallink{A054959}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054959}
\htmladdnormallink{A054960}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A054960}
\htmladdnormallink{A059735}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A059735}
\htmladdnormallink{A059736}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A059736}
)
\centerline{\rule{6.5in}{.01in}}
\vspace*{+.1in}
\noindent
Received Dec. 30, 1999, revised version received May 24, 2000,
published in Journal of Integer Sequences Feb. 9, 2001.
\centerline{\rule{6.5in}{.01in}}
\vspace*{+.1in}
\noindent
Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.research.att.com/~njas/sequences/JIS/}.
\centerline{\rule{6.5in}{.01in}}
\end{document}