\documentclass[12pt,reqno]{article}



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


\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.2in}
\setlength{\textheight}{8.0in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}



\begin{document}
\makeatletter

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

\begin{center}
\vskip 1cm {\LARGE\bf Sequences realized as Parker vectors of oligomorphic permutation
groups}
\vskip 1cm
\large Daniele A. Gewurz and Francesca Merola\\
\vskip .5cm
Dipartimento di Matematica\\
Universit\`a di Roma ``La Sapienza''\\
Piazzale Aldo Moro, 2 -- 00185 Roma \\
Italy\\
\href{mailto:gewurz@mat.uniroma1.it}{\tt gewurz@mat.uniroma1.it}\\
\href{mailto:merola@mat.uniroma1.it}{\tt merola@mat.uniroma1.it}\\
\end{center}

\date{}

\pagestyle{myheadings}

\newcommand{\no}{\noindent}
\newcommand{\pf}[1]{\no{\bf Proof.} #1\diam\medbreak}
\newcommand{\ndiv}{/\hskip-2.52mm\mid}
\newcommand{\bin}[2]{\left(\hskip-2mm \begin{array}{c} #1\\#2
         \end{array} \hskip-2mm\right)}
\newcommand{\qbin}[2]{\left[\hskip-2mm \begin{array}{c} #1\\#2
         \end{array} \hskip-2mm\right]_q}
\newcommand{\etalchar}[1]{$^{#1}$}
\newcommand{\comment}[1]{}

\newcommand{\diam}{\hfill$\diamondsuit$}
\newcommand{\G}{$GL(n,q)$}
\newcommand{\lcm}{{\rm lcm}}

\newtheorem{tm}{Theorem}[section]
\newtheorem{pr}[tm]{Proposition}
\newtheorem{lm}[tm]{Lemma}
\newtheorem{cl}[tm]{Corollary}
\newtheorem{cj}[tm]{Conjecture}

%\usepackage{eufrak}
%\usepackage{times}
%\usepackage{mathptm}

\hoffset-1truecm
\textwidth 14cm

\thispagestyle{empty}
\null
\addtolength{\textheight}{2cm}

\begin{abstract}
The purpose of this paper is to study the Parker vectors (in fact,
sequences) of several known classes of oligomorphic groups. The Parker
sequence of a group $G$ is the sequence that counts the number of
$G$-orbits on cycles appearing in elements of $G$. This work was inspired
by Cameron's paper on the sequences realized by counting orbits on
$k$-sets and $k$-tuples.
\end{abstract}
\bigskip

\section{Introduction}
In a recent paper \cite{Cam2000}, P. J. Cameron describes several
``classical" sequences (in the sense of appearing in the
\emph{Encyclopedia of Integer Sequences} \cite{njas}) obtainable as
U- or L-sequences of oligomorphic groups, that is as sequences of
numbers counting the orbits of such groups on $k$-subsets and on
ordered $k$-tuples, respectively.

Oligomorphic permutation groups \cite{Cam90} constitute a class of
infinite groups to which it is meaningful to extend the concept of Parker
vector, originally defined for finite groups (see 
\vfill\eject
\noindent\cite{GeMe01}).
So it is natural to study which integer sequences are obtained as Parker
sequence, that is, by counting orbits on $k$-cycles.

Recall that the \emph{Parker sequence}, or \emph{Parker vector}, of an
oligomorphic permutation group $G$ is the sequence ${\mathbf p}(G) =
(p_1,p_2,p_3,\dots)$, where $p_k$ is the number of orbits of $G$ on the
set of $k$-cycles appearing in elements of $G$, with $G$ acting by
conjugation. For instance, for the symmetric group $S$ acting on
a countable set, the Parker sequence is just $(1,1,1,\dots)$. A less
trivial example is the group $C$ preserving a circular order on a
countable set; for the Parker sequence one has $p_k=\varphi(k)$

Let us fix the notation for some sequences needed in this paper:
$\varphi(k)$ is the Euler (totient) function (A000010 in Sloane's
\emph{Encyclopedia} \cite{njas}), $d(k)$ is the number of divisors of $k$
(A000005),  and $\sigma(k)$ is the sum of the divisors of $k$ (A000203).


\section{Operators on sequences}\label{newold}
Cameron \cite{Cam2000} describes how obtaining ``new
groups from old" (mainly by taking direct and wreath product, and by
taking the stabilizer) corresponds to operators on and transforms of their
U- and L-sequences (in the sense of Sloane \cite{transf}).

Analogously, it is possible to study how the Parker sequences of ``new"
groups are related to those of ``old" ones. The general effect on Parker
sequences of taking direct and wreath products of groups is studied in the
authors' papers \cite{Gew02} and \cite{GeMe01}.

Let $G$ and $H$ be permutation groups acting on the sets $X$ and $Y$,
respectively. Recall that, if we consider the direct product $G\times H$
acting on the disjoint union of $X$ and $Y$, the U-sequence for $G\times
H$ is obtained as CONV of the U-sequences of the factors (we are
multiplying the ordinary generating functions of the sequences); on the
other hand, the L-sequence of the direct product is obtained as EXPCONV
(here one considers the exponential generating functions).

For the Parker sequences the corresponding operation is simply the sum
(element by element):
$$p_k(G\times H) = p_k(G) + p_k(H).$$

Forming the direct product of $G$ with the countable symmetric group $S$
gives, as U-sequence, PSUM of the L-sequence of $G$; as L-sequence,
BINOMIAL of its L-sequence. For the Parker sequence, it simply yields
$$p_k(G\times S) = p_k(G) + 1.$$

One may also consider the product action of $G\times H$ on the cartesian
product $X\times Y$. For this action one has:
$$p_k(G\times H) = \sum_{\stackrel{\scriptstyle i,j}{\lcm(i,j)=k}}
p_i(G) p_j(H).$$

What happens for wreath products is more interesting. Recall \cite{Gew02,GeMe01}
that for the Parker sequences of the wreath product of
$G$ and $H$ the following holds:
$$p_k(G\wr H) = \sum_{d|k} p_d(G) p_{k/d}(G).$$
This is the Dirichlet convolution, which in the terminology of Sloane
\cite{transf} is the DIRICHLET transform of the two sequences.

We may now study, for a given oligomorphic group $H$, the operator mapping
the Parker sequence of any group $G$ to that of $G\wr H$. For U-sequences,
this procedure gives rise to the operators EULER, INVERT, and CIK,
respectively for $H=S$, $H=A$, and $H=C$. For Parker sequences we get, for
$H=S$, the MOBIUSi operator
$$p_k(G\wr S) = \sum_{d|k} p_d(G);$$
and, for $H=A$, the identity operator
$$p_k(G\wr A) = p_k(G).$$
For $H=C$ we get
$$p_k(G\wr C) = \sum_{d|k} p_d(G) \varphi(k/d);$$
in particular note that for square-free $k$'s (that is, the values of $k$
such that $\mu(k)\neq 0$) one has $p_k(G\wr\nolinebreak C) = \varphi(k)
\sum_{d|k} p_d(G)/\varphi(d)$.

Notice that, while in general $G\wr H$ and $H\wr G$ may be different
groups, they have the same Parker sequence; so these operators are also
those mapping ${\bf p}(G)$ to ${\bf p}(H\wr G)$.


\section{Parker sequences and circulant relational
structures}\label{circulant}

Recall \cite{GeMe01} that, if we are dealing with a group $G$ defined as
the automorphism group of the limit of a Fra\"{\i}ss\'e class $\cal F$ of
relational structures, the Parker sequence of $G$ has an alternative
interpretation as the sequence enumerating the finite circulant structures
in that class. More precisely, the $k$th component of the Parker sequence
counts the relational structures in (the age of) $\cal F$ on the set
$\{1,2,\dots,k\}$ admitting as an automorphism the permutation $(1\ 2\
\dots\ k)$ (note that this is different than just requesting that the
structure admits a circular symmetry). In what follows we shall use
``circulant [structure]'' to mean ``circulant [structure] on the set
$\{1,2,\dots,k\}$ admitting the automorphism $(1\ 2\ \dots\ k)$''. All of
the Parker sequences listed in the ``Fra\"{\i}ss\'e class'' table were
obtained by counting these circulant structures.

This mirrors what happens with the L-sequence $(F_k)$ of the same group,
which is defined as the number of orbits on $k$-tuples of distinct
elements, and is equal to the number of labelled structures on $k$ points.
The same holds for the U-sequence $f_k$ of the number of orbits on
$k$-sets, giving the number of unlabelled structures. The theory behind
this can be found in Cameron's book \cite{Cam90}.

In order to give an idea of the techniques involved in deriving Parker
sequences, let us first briefly recall \cite{GeMe01} what happens for
graphs.

To describe a circulant graph $\Gamma$ on the vertex set
$\{0,1,2,\dots,k-1\}$, it is sufficient to give the neighbours of a fixed
vertex (say 0); this subset, which has the property that it contains a
vertex $i$ if and only if it contains $k-i$, is called \emph{symbol} of
$\Gamma$. On the other hand any subset $S$ of $\{1,2,\dots,k-1\}$ such
that $i\in S$ implies $k-i\in S$ is a possible symbol for a graph. So the
$k$th entry of the Parker sequence of the automorphism group of the limit
of the Fra\"{\i}ss\'e class of graphs (that is the well-known random, or
Erd\H{o}s-R\'enyi, or Rado, graph) is $2^{\lfloor k/2\rfloor}$.

Several variations to this method yield the Parker sequences for
other relational structures. 

For instance, if we consider the symbol for a digraph (a structure with a
relation $\rightarrow$ in which for each pair of distinct vertices $a$,
$b$, any of $a\rightarrow b$, $b\rightarrow a$, both, or none may hold) we
choose whether or not to join, by putting a directed edge, 0 with any
other vertex. So we get $p_k = 4^{(k-1)/2} = 2^{k-1}$. Similarly, if we do
not allow a double orientation on an edge, we get the class of oriented
graphs, for which $p_k = 3^{\lfloor k/2\rfloor}$.

Of course, this kind of argument holds also for the class of $n$-ary
relations, for $n\geq 2$. The symbol for a circulant $n$-relation on $k$
points can be any possible set of $(n-1)$-tuples (admitting repetitions)
of the points. For instance, for a ternary relation, we may have $(0,0)$
(meaning that $(0,0,0)$ holds), $(0,1)$, $(1,0)$, $(1,1)$, \dots\ So we
have $k^{n-1}$ such $(n-1)$-tuples, and $2^{k^{n-1}}$ possible symbols
(sets of such tuples).

More examples in same vein appear in the tables.

The same techniques can be applied to the class of two-graphs; this case,
however, requires some care.

Recall that a \emph{two-graph} is defined as a pair $(X, T)$, where $X$ is
a set of points, and $T$ a set of 3-subsets of $X$ with the property that
any 4-subset of $X$ contains an even number of members of $T$.

Two-graphs on $k$ vertices are in bijection with switching classes of
graphs on $k$ vertices. Recall that switching a graph $\Gamma = (V,E)$
with respect to $S\subseteq V$ gives a graph $(V,E')$ such that
$\{v,w\}\in E'$ if and only if either $v$ and $w$ are both in $S$ or both
in $V\setminus S$ and $\{v,w\}\in E$, or one is in $S$ and the other is in
$V\setminus S$, and $\{v,w\}\not\in E$ (see \cite{Sei76}, also for the
description of the correspondence between two-graphs and switching
classes).

Note that a two-graph $(X,T)$ is circulant if and only if at least one
graph in the corresponding switching class is. In fact, assume that
$\alpha$ is a permutation of $X$ inducing an automorphism of $(X,T)$; then
$\alpha$ induces an automorphism of at least one graph in the
corresponding switching class (as proved by Mallows and Sloane
\cite{MaSlo75}; see also Cameron \cite{cam77}).

The following result relates circulant two-graphs to circulant graphs.

\begin{tm}\label{twographs}
Let $\Gamma$ be a circulant $k$-vertex graph. If $k$ is odd, then $\Gamma$
is the only circulant graph in its switching class; if $k$ is even, there
are exactly two circulant graphs in its switching class.
\end{tm}

In order to prove this, let us first show in some detail what happens
switching circulant and regular graphs.

\begin{pr}
For $k$ odd, in each switching class of graphs on $k$ vertices there is at
most one regular graph.
\end{pr}

\pf{Let $\Gamma$ be a regular graph of valency $r$ on $k$ vertices. Let
us switch it with respect to the set $S\subseteq V(\Gamma)$, $0<|S|=m<k$.
Then, for each $t\not\in S$, call $n_t$ the number of neighbours of $t$
included in $S$ (before switching). Then the valency of $t$ in the
switched graph is $r - n_t + (m-n_t)$. Analogously, if $s\in S$ and $n_s$
is the number of neighbours of $s$ not in $S$, the valency of $s$ in the
switched graph is $r - n_s + (k-m-n_s)$.

Therefore, if the switched graph is regular, given two vertices $s$ and
$t$ as above, their new valencies must be equal:
$$r - n_t + (m-n_t) = r - n_s + (k-m-n_s),$$
or,
$$k = 2 (m - n_t + n_s).$$
That is, the number of vertices must be even for a non-trivial
switching equivalence to hold between $\Gamma$ and another regular graph.
}

We have now the first part of the theorem (because any circulant graph
must be, \emph{a fortiori}, regular). For the second part, the following
proposition describes explicitely when switching a circulant graph yields
another circulant graph.

\begin{pr}
If $\Gamma$ is a circulant graph on the vertices $\{1,2,\dots,k\}$, $k$
even, the only non-trivial switching yielding a circulant graph is with
respect to the set of vertices $S = \{1,3,5,\dots,k-1\}$ (or its
complement).
\end{pr}

\pf{For $\Gamma$ to be circulant, it must be possible to decompose it in
cycles $(i, i+l, i+2l, \dots, i-l)$ (all additions modulo $k$). In each
such cycle the vertices either have all the same parity, or an odd and an
even vertex alternate. So, switching with respect to $S$ either preserves
the whole cycle, or causes all its edges to vanish. In either case, the
graph remains circulant.

On the other hand, if switching is performed with respect to any other
non-trivial set $S'$, this set or its complement must include two consecutive
vertices $i$, $i+1$ (mod $k$) and of course there exists $j$ such that
$j\in S'$, $j+1\not\in S'$. In a circulant graph either
$1\sim2\sim\dots\sim k\sim1$ or $1\not\sim2\not\sim\dots\not\sim
k\not\sim1$; assume, up to complementing, the former. Then in the switched
graph $i\sim i+1$ while $j\not\sim j+1$; so the new graph is not
circulant.}

A variation of the previous argument shows that the same holds for
oriented two-graphs.


\section{Groups and their sequences}
In this section we consider the tables included in Cameron's paper
\cite{Cam2000} and add, as far as possible, the data concerning Parker
sequences.

\medskip
For the five closed highly homogeneous groups of Cameron's theorem
(i.e., the groups admitting only one orbit on $k$-sets for all $k$; see
\cite{cam76}) the Parker sequences are readily obtained. Recall that $S$
is the infinite symmetric group, $A$ (or $\partial C$) is the subgroup of
$S$ of the permutations preserving the ordering on the rational numbers,
$B$ (or $\partial C^*$) of those preserving or reversing it, $C$ of those
preserving a cyclic order on a countable set (say, the complex roots of
unity), and $D$ (or $C^*$) of those preserving or reversing such a cyclic
order.

The Parker sequence for $S$ is clearly the all-1 sequence; while in the
finite case this property characterises (with a single exception) the
symmetric groups, in the infinite case this sequence is shared by other,
not highly transitive groups. An instance of this fact is the group of the
Fra\"{\i}ss\'e class of trees with the action on edges.

The Parker sequence for $A$ is unremarkable, but for its being the neutral
element for the Dirichlet convolution. So, for each group $G$, ${\bf
p}(A\wr G) = {\bf p}(G\wr A) = {\bf p}(G).$

The sequences for $C$ and $D$ can be obtained by noting that these groups
induce on $k$-sets the groups $C_k$ and $D_k$ (dihedral of degree $k$),
respectively; see also \cite{GeMe01}. 

\medskip
\centerline{Highly Homogeneous Groups}
\medskip

{
\footnotesize
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
{\bf Group} & {\bf Parker sequence} & {\bf EIS entry} & {\bf Notes}\\
\hline
$S$ & 1, 1, 1, \dots & A000012 & \\
$A$ & 1, 0, 0, \dots & A000007 & \\
$B$ & 1, 1, 0, 0, \dots & A019590 &\\
$C$ & $\varphi(k)$ & A000010 & \\
$D$ & 1, 1, 1, $\varphi(k)/2$ & $\sim$A023022 & \\
\hline
\end{tabular} 
\end{center}
}

\medskip
\centerline{Direct Products}
\medskip

{
\footnotesize
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
{\bf Group} & {\bf Parker sequence} & {\bf EIS entry} & {\bf Notes}\\
\hline  
$S\times S$ & 2, 2, 2, \dots & A007395 & \\
$S\times A$ & 2, 1, 1, \dots & A054977 & \\
$A\times A$ & 2, 0, 0, \dots & A000038 & \\
$S^3$ & 3, 3, 3, \dots & A010701 & \\
$S^k$ & $k$, $k$, $k$, \dots && \\
\hline
\end{tabular}
\end{center}
}

\medskip

In the following table, $S_n$ denotes the (finite) symmetric group of
degree $n$, and $E$ is the trivial group acting on two points.

Note also that A00005 = MOBIUSi(A000012), A007425 = MOBIUSi(A000005).

\medskip
\centerline{Wreath Products}
\medskip
{
\footnotesize
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
{\bf Group} & {\bf Parker sequence} & {\bf EIS entry} & {\bf Notes}\\
\hline  
&&&\\
$S\wr S$ & $d(k)$ & A000005 & \\
$A\wr S$ & 1, 1, 1, \dots & A000012 & \\
$C\wr S$ & $k$ (= $\sum_{d|k} \varphi(d)$) & A000027 & \\
$(C\wr S)\wr S$ & $\sum_{d|k} d = \sigma(k)$ & A000203& \\
$S\wr A$ & 1, 1, 1, \dots & A000012 & \\
$S\wr S_2$, $S_2\wr S$ & 1, 2, 1, 2, \dots & A000034 & \\
$S\wr S_3$, $S_3\wr S$ & 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 1, 3, \dots &
A083039 & See $S\wr S_n$\\
$S\wr S_4$, $S_4\wr S$ & 1, 2, 2, 3, 1, 3, 1, 3, 2, 2, 1, 4, \dots &
A083040 & See $S\wr S_n$\\
$S\wr S_n$, $S_n\wr S$ & $p_k = |\{d : d|k, \, d\leq n\}|$ && See remark
1\\
$S\wr S\wr S$ & $\sum_{d_0|k} d(d_0) = 1,3,3,6,3,9,3,10,6,9,3, \dots$ &
A007425 &\\
$A\wr A$ & 1, 0, 0, \dots & A000007 & \\
%$A\wr A\wr A$ & 1, 0, 0, \dots & A000007 & \\
%$S_2\wr A$ & 1, 1, 0, 0, \dots & A019590 & \\
$S_k\wr A$ & 1, \dots ($k$ times) \dots, 1, 0, 0, \dots && \\
$E\wr S$ & 2, 2, 2, \dots & A007395 & \\
$E\wr A$ & 2, 0, 0, \dots & A000038 & \\
$S^{\wr n}$ & $\sum_{d_0|k} \sum_{d_1|d_0} \sum_{d_2|d_1} \cdots
\sum_{d_{n-3}|d_{n-4}} d(d_{n-3})$ & MOBIUSi${}^n$(A000005) &
See remark 2\\
$C\wr C$ & $\sum_{d|k} \varphi(d) \varphi(k/d)
=1,2,4,5,8,8,12,12,16,16,\dots$ & A029935 & See remark 3\\
\hline
\end{tabular}
\end{center}
}

\medskip
\no{\bf Remark 1}\quad The sequence is periodic of period
$\lcm(1,\dots,n)$.
\smallskip

\no{\bf Remark 2}\quad The sequence associated with $S^{\wr n}$ (i.e., the
iterated wreath product of $S$ with itself with $n$ factors) can be
expressed as follows. Let $\delta_0(k) := 1$ for each $k$, and for $i>0$
let
$$\delta_i(k) := \sum_{d|k} \delta_{i-1}(d),$$
that is, $\delta_i$ is the Dirichlet convolution $\delta_{i-1} *
\delta_0$. Thus, $\delta_i(k) = p_k(S^{\wr i+1})$.

All the functions $\delta_i$ are multiplicative, because $\delta_0$ is,
and the Dirichlet convolution preserves multiplicativity. Thus, it
suffices to compute the value of $\delta_i$ on prime powers.

We claim that
$$\delta_i(p^j) = \bin{i+j}{i}.$$

To obtain a different description of the $\delta_i$s, note that
$\delta_1(k)$ gives the number of divisors of $k$, including $1$ and $k$;
so it is equal to $d(k)$. Next, $\delta_2(k)$ is the sum over the divisors
of $k$ of the number of their divisors; in other words, it gives the
number of pairs $(h,d)$ with $h|d$ and $d|k$ (observe that $h$ and $d$ may
well coincide). In general, we see that $\delta_i(k)$ gives the number of
$i$-ples $(d_1,d_2,\dots,d_i)$ with $d_1|d_2$, \dots, $d_{i-1}|d_i$,
$d_i|k$. We call such a sequence a \emph{generalised gozinta chain},
recalling that a gozinta (``goes into'') chain for $k$ is a sequence of
divisors of $k$ each of which strictly divides the next one.

When $k=p^j$, a sequence of divisors of $k$ each of which divides the next
one corresponds to a nondecreasing sequence of exponents of $p$, that is
to a nondecreasing sequence of numbers in $[j]=\{0,1,\dots,j\}$, which in
turn can be seen as a multiset of elements of $[j]$.

So, it is enough to enumerate the multisubsets of $\{0,1,\dots,j\}$ of
size $i$. It is well known (see for instance \cite{stanley}) that their
number is given by $\bin{i+j}{i}$, as claimed.
\smallskip

\no{\bf Remark 3}\quad If $k$ is square-free, $p_k$ is equal to
$\sum_{d|k} \varphi(k) = d(k) \varphi(k)$.

\bigskip\bigskip
\begin{center}
*\qquad*\qquad*
\end{center}
\bigskip\bigskip

The following groups arise as automorphism groups of Fra\"{\i}ss\'e
classes (see section \ref{circulant}).

The calculation of Parker sequences for ``treelike objects'' and related
structures is carried out in detail in the forthcoming paper
\cite{GeMe??}.

The letters R and L mean ``shifted right'' and ``shifted left''
respectively.
\medskip

\vfill\eject
\centerline{Automorphism Groups of Homogeneous Structures}
\medskip

{
\footnotesize
\begin{center}
\begin{tabular}{|p{5cm}|p{5.7cm}|l|l|}
\hline
{\bf Fra\"{\i}ss\'e class} & {\bf Parker sequence} & {\bf EIS entry} &
{\bf Notes}\\
\hline
&&&\\
Graphs & $2^{\lfloor k/2\rfloor}$ & A016116 & See \cite{GeMe01}\\
Graphs up to complement & $p_1=1$, $p_k=2^{\lfloor k/2\rfloor -1}$ for
$k>1$ & A016116RR & See rem.\ 4\\
$K_3$-free graphs & 1,2,1,3,3,4,4,8,4,14,11,14,\dots & A083041 &
See rem.\ 5\\
Graphs with bipartite block & 2,2,2,\dots & A007395 & See rem.\ 6\\
Graphs with loops & $2^{\lfloor k/2\rfloor +1}$ & A016116LL &
See rem.\ 7\\
Digraphs & $2^{k-1} (= 4^{(k-1)/2})$ & A000079R & \\
Digraphs with loops (or binary relations) & $2^k$ & A000079 & \\
Oriented graphs & $3^{\lfloor k/2\rfloor}$ & [missing] & \\
Topologies & $d(k)$ & A000005 & See rem.\ 8 \\
Posets & 1,1,1,\dots & A000012 & See rem.\ 9 \\
Tournaments & $k$ odd: $2^{\lfloor k/2\rfloor}$, $k$ even: 0 & [missing] &
See \cite{GeMe01}\\
Local orders & $k$ odd: $\varphi(k)$, $k$ even: 0 & [missing] & See
\cite{GeMe??}\\
Two-graphs & $2^{\lceil k/2\rceil}$ & A016116L & See
Thm.~\ref{twographs}\\
Oriented two-graphs & $2^{\lceil k/2\rceil}$ & A016116L & See
Thm.~\ref{twographs}\\
Total orders with subset & 2,0,0,\dots & A000038 &\\
Total orders with 2-partition & 1,0,0,\dots & A000007 &\\
$C$-structures with subset & $2\varphi(k)$ & [missing] &
See rem.\ 10 \\
$D$-structures with subset & $\varphi(k)$ & A000010 & See rem.\ 10\\
2 total orders (distinguished) & 1,0,0,\dots & A000007 &\\
2 total orders (not distinguished) & 1,1,0,0,\dots & A019590 &\\
2 betweennesses (not distinguished) & 1,1,0,0,\dots & A019590 &\\
Boron trees (leaves) (or $T_3$) &characteristic fn. of $\{3^a
2^b\}_{a\in\{0,1\}, b\geq0}$ & [missing] & See \cite{GeMe??}\\
HI trees (leaves) (or $T$) & nr. of ordered factorisations of $k$ &
A002033R & See \cite{GeMe??}\\
R(Boron trees (leaves)) (or $\partial T_3$) & characteristic fn. of powers
of 2 &A036987& See \cite{GeMe??} \\
R(HI trees (leaves)) (or $\partial T$) & nr. of ordered factorisations of
$k$ & A002033R & See \cite{GeMe??} \\
Trees (edges) &1,1,1,\dots & A000012 & See \cite{GeMe??}\\
Covington structures (or $\partial T_3(2)$) & $p_{2^i} = 2^i$, 0
otherwise & A048298 & See \cite{GeMe??} \\
Binary trees (or $\partial PT_3$) & 1,0,0,0,\dots & A000007& See
\cite{GeMe??}\\
Binary trees up to reflection (or $\partial P^*T_3$) & 1,1,0,0,\dots 
& A019590 & See \cite{GeMe??}\\
Plane trees (or $PT$)$\dag$ & $\varphi(k)$ & A000010 & See
\cite{GeMe??}\\
Plane trees up to reflection (or $P^*T$)$\dag$  & $\sim\varphi(k)/2$
& A023022 & See \cite{GeMe??}\\
Plane boron trees (or $PT_3$) & 1,1,2,0,0,\dots & [missing] & See
\cite{GeMe??}\\
Plane boron trees up to reflection (or $P^*T_3$) & 1,1,1,0,0,\dots &
[missing] &
See \cite{GeMe??}\\
3-hypergraphs & $2^{f(k,3)}$, where $f(k,3) =
0,0,1,1,4,4,5,7,10,12,15,19,\dots$
& [missing] & See \cite{GeMe01}\\
$t$-hypergraphs$\dag$ & $2^{f(k,t)}$ && See \cite{GeMe01}\\
Ternary relations & $2^{k^2}$ & A002416 &\\
Quaternary relations & $2^{k^3}$ & [missing] &\\
%&&&\\
\hline
\multicolumn{4}{l}{}\\
\multicolumn{4}{l}{$\dag$ Not in \cite{Cam2000}.}\\
\end{tabular}
\end{center}
}

%\medskip
\vfill\eject

\no{\bf Remark 4}\quad Each (symbol for a) circulant graph represents also
its complement, so (for $k>1$) each term is one half of the corresponding
term for graphs. For instance, $p_2 = 1$ because the graphs $K_2$ and
$N_2$ are now identified.
\medskip

\no{\bf Remark 5}\quad This is the number of symmetric sum-free subsets of
${\bf Z}/(k)^*$ (see \cite{cam87}): if the symbol contains $a$ and $b$, it
cannot contain $a+b$, and (as for generic graphs) if it contains $a$, it
must contain $k-a$.
\medskip

\no{\bf Remark 6}\quad We cannot exchange ``black" and ``white" vertices,
so a circulant structure is an all-black or all-white null graph.
\medskip

\no{\bf Remark 7}\quad Reason as in section \ref{circulant}, but take in
addition to ``basic" circulant graphs (those with symbol of the form
$\{i,k-i\}$) also that with $k$ vertices, each with a loop attached, and
no other edges. In other words, in the symbol (set of ``neighbours" of 0)
for a circulant graph with loops, also 0 may appear.
\medskip

\no{\bf Remark 8}\quad The ``basic" graphs do not work as they are; the
request for the relation to be transitive forces any $k$-gon to ``become"
a complete directed graph (that is, $K_k$ where all edges are bidirected):
by transitivity, connect vertices at distance 2, then at distance 3 and so
on. The superposition of $d$ copies of $K_{k/d}$ and $l$ copies of
$K_{k/l}$ becomes by transitivity the superposition of GCD$(d,l)$ copies
of $K_{{\rm lcm}(k/d, k/l)}$. So the lattice of divisors of $k$ describes
all the possible circulant transitive digraphs, that is topologies.

In other words, a topology is the transitive closure of a union of cyclic
graphs; its incidence matrix can be seen as the $k$th power of the
incidence matrix of the starting graph with, as its entries, boolean
variables $0$ and $1$ (so that $1+1=1$).
\medskip

\no{\bf Remark 9}\quad By acyclicity, for each $n$ the only circulant
poset is the one with $n$ incomparable elements.
\medskip

\no{\bf Remark 10}\quad The only possible distinguished sets are the empty
and the full ones.
\medskip

\centerline{One Last Example}
\medskip

{
\footnotesize
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
{\bf Group} & {\bf Parker sequence} & {\bf EIS entry} & {\bf Notes}\\
\hline  
&&&\\
$S^2$ (product action) & $d(k^2)$ & A048691 & See rem.\ 11\\
&&&\\
\hline
\end{tabular}
\end{center}
}

\medskip

\no{\bf Remark 11}\quad The result follows from Section~\ref{newold},
keeping in mind that $d(k^2)$ is equal to the number of
pairs $(i,j)$ such that $\lcm(i,j)=k$.

\comment{
It is known that $d(k^2)$ is equal to the number of
ordered factorisations of $k$ in 3 factors: $k = f_1 f_2 f_3$ ($1\leq f_i
\leq k$), such that $(f_1, f_2) = 1$.

A $k$-cycle of $S^2$ corresponds to such a factorisation as follows:
\begin{flushleft}
$( (1\ \ f_1+1\ \ 2f_1+1\ \dots\ (f_3-1)f_1+1\ \ 2\ \ f_1+2\ \dots\ 
f_1 f_3),$
\end{flushleft}
\begin{flushright}
$(1\ \ f_2+1\ \ 2f_2+1\ \dots\ (f_3-1)f_2+1\ \ 2\ \ f_2+2\ \dots\ f_2 f_3))
=$
\end{flushright}
\begin{flushleft}
$= ((1,1)\ (f_1+1,f_2+1)\ (2f_1+1,2f_2+1)\ \dots\ (f_1 f_3,f_2 f_3))$
\end{flushleft} 
which is indeed a cycle of length $k = f_1f_2f_3$ (that is, $\lcm(f_1
f_3,f_2 f_3)$). 

Each cycle of $S^2$ is of the above form; and two cycles
$\gamma_1=(\alpha_1, \beta_1)$ and $\gamma_2=(\alpha_2, \beta_2)$ of $S^2$
are conjugate if and only if the length of $\alpha_1$ is equal to the
length of $\alpha_2$ and the length of $\beta_1$ is equal to the length of
$\beta_2$.}


\section*{Acknowledgements}
We thank Dina Ghinelli and Peter J.~Cameron for help and encouragement.
We also thank the referee for useful comments.


\begin{thebibliography}{ABC}
\addcontentsline{toc}{chapter}{Bibliography}

\bibitem{cam76} Peter J. Cameron, Transitivity of permutation groups on
unordered sets, {\it Math.~Z.} {\bf 148} (1976), 127--139.

\bibitem{cam77} Peter J. Cameron, Cohomological aspects of two-graphs,
{\it Math.~Z.} {\bf 157} (1977), 101--119.

\bibitem{cam87} Peter J. Cameron, Portrait of a typical sum-free set, {\it
Surveys in Combinatorics} (C. Whitehead, ed.), 13--42, LMS Lecture Notes
{\bf 123}, Cambridge Univ. Press, Cambridge, 1987.

\bibitem{treelike} Peter J. Cameron, Some treelike objects, {\it Quart.\
J. Math.\ Oxford Ser.\ (2)} {\bf 38} (1987), 155--183.

\bibitem{Cam90} Peter J. Cameron, {\it Oligomorphic Permutation Groups},
LMS Lecture Notes {\bf 152}, Cambridge Univ. Press, Cambridge, 1990.

\bibitem{Cam2000} Peter J. Cameron, Sequences realized by oligomorphic
permutation groups, {\it J. Integer Seq.} {\bf 3} (2000), 00.1.5
[\href{http://www.math.uwaterloo.ca/JIS/VOL3/groups.html}{\tt
http://www.math.uwaterloo.ca/JIS/VOL3/groups.html}].

\bibitem{Gew02} Daniele A. Gewurz, Parker vectors and cycle indices of
permutation groups, {\it Quaderni Elettronici del Seminario di Geometria
Combinatoria} {\bf 4E} (2002)
[\href{http://www.mat.uniroma1.it/~combinat/quaderni}{\tt
http://www.mat.uniroma1.it/\~{}combinat/quaderni}].

\bibitem{GeMe01} Daniele A.~Gewurz and Francesca Merola, Parker vectors
for infinite groups, {\it European J. Combin.} {\bf 22} (2001),
1065--1073.

\bibitem{GeMe??} Daniele A.~Gewurz and Francesca Merola, Cycle action on
treelike structures, preprint.

\bibitem{MaSlo75} C.L.~Mallows and N.J.A.~Sloane, Two-graphs, switching
classes and Euler graphs are equal in number, {\it SIAM J.~Appl.~Math.}
{\bf 28} (1975), 876--880.

\bibitem{Sei76} J.~J.~Seidel, A survey of two-graphs, {\it Colloquio
Internazionale sulle Teorie Combinatorie (Rome, 1973)}, Tomo I, Atti dei
Convegni Lincei, No.~17, Accad.~Naz.~Lincei, Rome, 1976, pp.~481--511.

\bibitem{njas} N.J.A. Sloane, ed., The On-Line Encyclopedia of Integer
Sequences, published electronically at
\href{http://www.research.att.com/~njas/sequences/}{\tt
http://www.research.att.com/\~{}njas/sequences/}.

\bibitem{transf} N.J.A. Sloane, ed., Transformations of Integer Sequences,
published electronically at
\href{http://www.research.att.com/~njas/sequences/transforms.html}{\tt
http://www.research.att.com/\~{}njas/sequences/transforms.html}.

\bibitem{stanley} Richard P. Stanley, {\it Enumerative Combinatorics},
Vol.\ 1, Wadsworth, 1986 (Cambridge University Press, 1997).

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: 
Primary 20B07; Secondary 05A15.

\noindent \emph{Keywords:  
Oligomorphic permutation groups, action on cycles,
Parker vectors, circulant relational structures}


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences 
\seqnum{A000010},
\seqnum{A000005},
\seqnum{A000203},
\seqnum{A000012},
\seqnum{A000007},
\seqnum{A019590},
\seqnum{A023022},
\seqnum{A007395},
\seqnum{A054977},
\seqnum{A000038},
\seqnum{A010701},
\seqnum{A000027},
\seqnum{A000034},
\seqnum{A083039},  %
\seqnum{A083040},  %
\seqnum{A007425},
%\seqnum{A023022},
\seqnum{A029935},  %
\seqnum{A016166},
\seqnum{A083041},  %
\seqnum{A000079},
\seqnum{A002033},
\seqnum{A036987},
\seqnum{A048298},
\seqnum{A002416},
\seqnum{A048691}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in} \noindent Received October 1, 2002;
revised version received  April 4, 2003.
Published in {\it Journal of Integer Sequences} 
April 15, 2003.  Slight revisions, June 11, 2003.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.


\end{document}