% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
%\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

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

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

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Enumeration of unlabeled directed hypergraphs}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Jianguo Qian\thanks{Supported by NSFC grant No. 10831001.}\\
\small School of Mathematical Sciences, Xiamen University\\[-0.8ex]
\small Xiamen 361005, Fujian, P.R. China\\[-0.8ex]
\small\tt jgqian@xmu.edu.cn}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Feb. 19, 2013}{}\\
\small Mathematics Subject Classifications:  05C30, 05C65, 05C20}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
We consider the enumeration of unlabeled directed hypergraphs by
using P$\rm\acute{o}$lya's counting theory and Burnside's counting lemma. Instead of
characterizing the cycle index of the permutation group acting on the hyperarc
set $A$, we treat each cycle in the disjoint cycle decomposition of a
permutation $\rho$ acting on $A$ as an equivalence class (or orbit) of $A$ under
the operation of the group generated by $\rho$.
Compared to the cycle index method, our approach is  more effective
in  dealing with the enumeration of directed hypergraphs.
We deduce the explicit counting formulae for the unlabeled
$q$-uniform and unlabeled general directed hypergraphs. The former
generalizes the well known result for 2-uniform directed hypergraphs,
i.e., for the ordinary directed graphs introduced by Harary and Palmer.



  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} unlabeled
directed hypergraph; uniform; enumeration
\end{abstract}

\section{Introduction}
In 1937, P\'{o}lya \cite{Polya} developed a powerful theory for
treating the symmetries of graphs or more in general, certain types
of discrete configurations  under a given permutation group, which
nowadays is known as P\'{o}lya's theorem or Redfield-P\'{o}lya
theorem and represents one of the cornerstones of modern
combinatorics. Theoretically, this theory provides us with a
universal technique to count the unlabeled graphs or in particular,
the graphs which meet some specific requirements. Following
P\'{o}lya, the enumeration problem for  various types of graphs were
studied in the literature. For examples, some results on ordinary
graphs and hypergraphs can be found in
\cite{Borkar,Chapuy,Gimenez1,Gimenez2,Harary1,Harary2,Harary3,Palmer,Robinson}
and \cite{Bruijin,Ishihara,Parthasarathy,Skibenko,Tazawa,Wu},
respectively. In particular, the pre-1973 work on this problem was
nicely included in the text book \cite{Harary1} written by Harary
and Palmer.


In this paper, we consider the enumeration of unlabeled
directed hypergraphs, i.e., non-isomorphic directed hypergraphs. A
{\it directed hypergraph} $D$ is a pair $\langle V, A\rangle$, where
$V$ is the vertex set and $A$ is its hyperarc set. As a
generalization of directed graph, a {\it hyperarc} $a$ or
simply, an {\it arc} $a$, in a directed hypergraph is a nonempty
vertex subset with a specified vertex called its {\it source} or
{\it root}. That is, $a$ is an ordered pair $\langle v,W\rangle$
with $v\in V$ and $W\subseteq V\setminus\{v\}$. The set $W$ is also
called the {\it sink set} of the arc
\cite{Ausiello,Frank,Li,Vietri}. A directed hypergraph $D=\langle V,
A\rangle$ is called {\it $q$-uniform} ($1\leq q\leq |V|$) if each
arc $\langle v,W\rangle$ consists of exactly $q$ vertices (including
its root), i.e., $|W|=q-1$. Generally, a directed hypergraph
in which the sink set $W$ can consist of any number  of vertices is
called a {\it general} directed hypergraph. In addition, all the hypergraphs
considered here are {\it simple}, i.e., the multiple arcs are not
allowed.


We apply P\'{o}lya's counting theory and Burnside's counting lemma to
our enumeration problem. In general, the key point of 
P\'{o}lya's theory to treat the number of cycles in the disjoint
cycle decomposition of the permutations is to characterize the cycle
index of the involved permutation group, which has been widely used
in graphical enumeration. However, to characterize the cycle index
may become particularly complex for some cases, e.g., for undirected
hypergraph \cite{Ishihara,Skibenko,Wu}, the standard and
frequently used method for which is to use the generating function.

We will, however,  not try to characterize the cycle index. Instead, we consider the number of cycles from a different point of
view which arises from a simple observation, i.e.: a cycle in a
permutation $\pi$ acting on a set $X$ could be regarded as an
equivalence class (or orbit) of $X$ under the operation of the group
generated by $\pi$.

 Compared to  the cycle index method based on generating function, our approach is
more effective in dealing with the enumeration of directed hypergraphs.
We deduce  the explicit counting formulae for the
unlabeled $q$-uniform directed hypergraphs with $1\leq q\leq |V|$
and unlabeled general directed hypergraphs. The former generalizes
the well known result for the ordinary directed graphs introduced by
Harary and Palmer \cite{Harary1}. Some numerical results  are also
listed, as examples.



%% The Appendices part is started with the command \appendix;
%% appendix sections are then done as normal sections
%% \appendix

\section{Main results}
\label{}


Let $\rho$ be a permutation acting on a set $X$ and let
$\Omega(\rho)$ be the number of cycles in the disjoint cycle
decomposition of $\rho$. As mentioned in the previous section,
$\Omega(\rho)$ could be regarded as the number of equivalence
classes (or orbits) of $X$ under the operation of the group
generated by $\rho$: i.e., $\langle\rho\rangle=\{\rho,\rho^2,\cdots,
\rho^{|\rho|}\}$, where $|\rho|$ is the order of $\rho$. Thus, by
Burnside's lemma \cite{Beckenbach} we get the following observation.
\begin{observation}\label{obsev:observ} The number of cycles
in the disjoint cycle decomposition of a permutation $\rho$ is
$$\Omega(\rho)=\frac{1}{|\rho|}\sum\limits_{i=1}^{|\rho|}\Psi(\rho^i),$$ where $\Psi(\rho^i)$ is the
number of elements of $X$ left fixed by $\rho^i$, i.e., invariant
under $\rho^i$. \hfill$\square$
\end{observation}

We now turn to the enumeration problem of the directed hypergraphs.
In the following, the vertex set of a directed hypergraph $D$ of
order $n$ is always set to be $[n]=\{1,2,\cdots,n\}$. In terms of
the P${\rm \acute{o}}$lya's counting theory, we model a directed
hypergraph $D$ (general or uniform) as an arc coloring of the
complete directed hypergraph $K_n$ (general or uniform) of order $n$
using two colors. Thus, the problem is equivalent to determining the
number of equivalence coloring classes of $K_n$ under the operation
of the group induced by the automorphism group $S_n$ of $K_n$, i.e.,
the symmetry group on $[n]$.

  For a partition $P$ of
$n$, we will write it either as the form $P:p_1+p_2+\cdots+p_k$ or
as $P:1{\alpha_1}+2{\alpha_2}+\cdots +n{\alpha_n}$, for the
convenience of our discussion, where $\alpha_i$ is the number of the
integers $i$ in the partition. Given natural numbers
$a_1,a_2,\cdots,a_m$, we denote by $(a_1,a_2,\cdots,a_m)$ and
$[a_1,a_2,\cdots,a_m]$ the greatest common divisor  and the least
common multiple of $a_1,a_2,\cdots,a_m$, respectively.

A permutation $\pi\in S_n$ with the disjoint cycle decomposition
$\pi=\sigma_1\sigma_2\cdots
 \sigma_k$ induces a partition of $n$, i.e., $P:p_1+p_2+\cdots+p_k$,
 where $p_i$ is the length of the cycle $\sigma_i$. Conversely, it is well known \cite{Harary1}
  that a partition $P: 1{\alpha_1}+2{\alpha_2}+\cdots +n{\alpha_n}$ of $n$
 induces
 $$\frac{n!}{1^{\alpha_1}2^{\alpha_2} \cdots
n^{\alpha_n}\alpha_1!{\alpha_2}!\cdots {\alpha_n}!}$$ permutations
in $S_n$, each of which has disjoint cycle decomposition of the form
$1^{\alpha_1}2^{\alpha_2}\cdots
 n^{\alpha_n}$, where  $i^{\alpha_i}$ represents the product of $\alpha_i$ cycles of length $i$, $i=1,2,\cdots,n$.
 For a permutation $\pi\in S_n$, we denote by $\rho(\pi)$ the
permutation acting on the arc set  induced by $\pi$. For simplicity,
we also use $\rho(P)$ to denote $\rho(\pi(P))$, where $\pi(P)$ is an
arbitrary permutation in $S_n$ induced by $P$.


 Let ${\cal P}(n)$ be the class of all the partitions of $n$. Then by Burnside's lemma \cite{Beckenbach},
 the number of unlabeled directed
 hypergraphs of order $n$ is given by
\begin{equation}d(n)=\frac{1}{n!}\sum\limits_{\pi\in S_n}\Phi(\rho(\pi))=\frac{1}{n!}\sum\limits_{P\in{\cal
P}(n)}\frac{n!}{1^{\alpha_1}2^{\alpha_2} \cdots
n^{\alpha_n}\alpha_1!{\alpha_2}!\cdots
{\alpha_n}!}\Phi(\rho(P)),\end{equation} where $\Phi(\rho(P))$
(resp., $\Phi(\rho(\pi))$) is the number of colorings left fixed by
$\rho(P)$ (resp., by $\rho(\pi)$). In terms of the cycle index,
$\Phi(\rho(P))$  can be represented as $2^{\Omega(\rho(P))}$, where
$\Omega(\rho(P))$ is the number of cycles in $\rho(P)$. We notice
that the order of the permutation $\rho(P)$ is
$[p_1,p_2,\cdots,p_k]$. Thus, by Observation~\ref{obsev:observ},
\begin{equation}\label{eq:eq2}
d(n)=\sum\limits_{P\in{\cal P}(n)}\frac{1}{1^{\alpha_1}2^{\alpha_2}
\cdots n^{\alpha_n}\alpha_1!{\alpha_2}!\cdots
{\alpha_n}!}2^{\Omega(\rho(P))},\end{equation} where
\begin{equation}
\Omega(\rho(P))=\frac{1}{[p_1,p_2,\cdots,p_k]}\sum\limits_{t=1}^{[p_1,p_2,\cdots,p_k]}{\Psi(\rho^t(P))},
\end{equation}
and  $\Psi(\rho^t(P))$ is the number of arcs  left fixed by
$\rho^t(P)$.

Let $\pi$ be induced by a partition $P:p_1+p_2+\cdots+p_k$ having
the disjoint cycle decomposition
$$\pi=(n_{11}n_{12}\cdots n_{1p_1})(n_{21}n_{22}\cdots n_{2p_2})\cdots(n_{k1}n_{k2}\cdots n_{kp_k}).$$
Let $\langle u_{rs},Q\rangle$ be an arc of a directed hypergraph,
where
$$Q=Q_1\cup Q_2\cup\cdots\cup Q_k,\ Q_i\subseteq \{n_{i1},n_{i2},\cdots, n_{ip_i}\}, i=1,2,\cdots,k,$$
and $u_{rs}\in\{n_{r1},n_{r2},\cdots, n_{rp_r}\}\setminus Q_r$. We
call $r$ the {\it root subscript} of $\langle u_{rs},Q\rangle$. It
is clear that the arc $\langle u_{rs},Q\rangle$ restricted on
$\{n_{r1},n_{r2},\cdots, n_{rp_r}\}$ is $\langle u_{rs},Q_r\rangle$.

 By the definition of the directed hypergraphs, the arc $\langle
u_{rs},Q\rangle$ is left fixed by $\rho(\pi^t)$ if and only if
$u_{rs}$ is left fixed by $\pi^t$ and $Q$ is left fixed by
$\rho(\pi^t)$, i.e., $\pi^t(u_{rs})=u_{rs}$ and $\rho(\pi^t)(Q)=Q$.
Similarly, $\langle u_{rs},Q_r\rangle$ is left fixed by
$\rho(\pi^t)$ if and only if $\pi^t(u_{rs})=u_{rs}$ and
$\rho(\pi^t)(Q_r)=Q_r$.

For a subset $Q_i$, we write it as a (0,1)-sequence:
$Q_i=a_{i1}a_{i2}\cdots a_{ip_i}$, where $a_{ij}=1$ if $n_{ij}\in
Q_i$ and $a_{ij}=0$ for otherwise. One can see that $Q_i$ is left
fixed by $\rho(\pi)$ if and only if $a_{ij}=a_{i,j+1({\rm mod}
p_i)}$
 for any $j\in \{1,2,\cdots,p_i\}$. In general, we have the following result.
 \begin{lemma}
\label{lem:lemma} Let $i\in\{1,2,\cdots,k\}$ and $t$ be a positive integer.\\
1).\ If $i\not=r$ then $Q_i$ is left fixed by $\rho(\pi^t)$ if and
only if
$$a_{ij}=a_{i,j+\eta({\rm mod} p_i)}$$
 for any $j\in \{1,2,\cdots,p_i\}$, where $\eta=(t,p_i)$;\\
 2).\ $\langle u_{rs},Q_r\rangle$ is left
 fixed by $\rho(\pi^t)$ if and
only if $t$ is a multiple of $p_r$.
\end{lemma}
\noindent{\bf Proof}.  1).\ Notice that $\pi^t(n_{ij})=n_{i,j+t({\rm
mod} p_i)}=n_{i,j+\eta h({\rm mod} p_i)}$,
 where $h=t/\eta$. Therefore,
the condition $a_{ij}=a_{i,j+\eta({\rm mod} p_i)}$ implies that
$n_{ij}\in Q_i$ if and only if $\pi^t(n_{ij})\in Q_i$, i.e., $Q_i$
is left fixed by $\rho(\pi^t)$. The sufficiency now follows.

Conversely, assume that $Q_i$ is left fixed by $\rho(\pi^t)$, i.e.,
$\rho(\pi^t)(Q_i)=Q_i$. Then $\pi^t$ restricted on $Q_i$ is a
permutation, i.e., $n_{ij}\in Q_i$ if and only if $\pi^t(n_{ij})\in
Q_i$. On the other hand, again notice that
 $\pi^t(n_{ij})=n_{i,j+t({\rm mod} p_i)}$. Hence,
$n_{ij}\in Q_i$ if and only if $n_{i,j+t({\rm mod} p_i)}\in Q_i$ and
therefore, $n_{i,j+mt({\rm mod} p_i)}\in Q_i$ for any integer $m$.
Now since $p_i/\eta$ and $t/\eta$ are relatively prime, the equation
$$\frac{p_i}{\eta}+1\equiv m\frac{t}{\eta}\ \  ({\rm mod}p_i)$$
has an integer solution $m$ with $1\leq m< (p_i/\eta)(t/\eta)$.
Thus, we have $lp_i+\eta=mt$, i.e., $\eta\equiv mt\ ({\rm mod}
p_i)$, where $l$ is an integer. This implies that $j+mt =j+\eta\
({\rm mod} p_i)$. Equivalently, $n_{ij}\in Q_i$ if and only if
$n_{i,j+\eta({\rm mod} p_i)}\in Q_i$, i.e., $a_{ij}=a_{i,j+\eta({\rm
mod}) p_i}$ for each $j\in\{1,2,\cdots
p_i\}$.\\
2). We notice that if $t$ is a multiple of $p_r$, then $Q_r$ is left
fixed by $\rho(\pi^t)$. Therefore, 2) follows directly since
$u_{rs}$ is left fixed by $\pi^t$ if and only if $t$ is a multiple
of $p_r$. This completes our proof. \hfill$\square$

\subsection{General directed hypergraphs}


By the definition of the directed hypergraphs, we note that any arc
consists of at least one vertex, i.e., the root vertex.

 By Lemma~\ref{lem:lemma},
if $Q_i$ ($i\not=r$) is left fixed by $\rho(\pi^t)$ then the
sequence $Q_i=a_{i1}a_{i2}\cdots a_{ip_i}$ is determined uniquely by
its subsequence $a_{i1}a_{i2}\cdots a_{i\eta}$ since $\eta$ divides
$p_i$. The number of such subsequences, i.e., the (0,1)-sequences of
length $\eta$, is clearly $2^\eta$. Again by Lemma~\ref{lem:lemma},
$\langle u_{rs},Q_r\rangle$ is left fixed by $\rho(\pi^t)$ if and
only if $t$ is a multiple of $p_r$, i.e., $t=mp_r$ for some integer
$m$. The number of such pairs $\langle u_{rs},Q_r\rangle$ is clearly
$2^{p_r-1}p_r$.

On the other hand, an arc $\langle u_{rs},Q\rangle$ is left fixed by
$\rho(\pi^t)$ if and only if $\langle u_{rs},Q_r\rangle$ and $Q_i$
are left fixed by $\rho(\pi^t)$ for each $i\in\{1,2,
\cdots,k\}\setminus\{r\}$. In this case we must have $t=mp_r$.
Therefore, the number of such arcs, i.e., $\Psi^*(\rho^t(P))$, is
exactly
$$2^{p_r-1}p_r\prod_{i\not=r}2^{(mp_r,p_i)}.$$
 Thus, combining with (2) and (3) we reach the following result immediately.
\begin{theorem}\label{thm:thm1}  Let $d^*(n)$ denote the number of unlabeled general directed hypergraphs of order $n$ and let
$$\Omega^*(P)=\frac{1}{[p_1,p_2,\cdots,p_k]}
\sum\limits_{r=1}^{k}2^{p_r-1}p_r\sum\limits_{m=1}^{[p_1,p_2,\cdots,p_k]/p_r}\prod\limits_{i\not=r}2^{(mp_r,p_i)}.$$
Then
$$\hspace*{3.5cm}d^*(n)=\sum\limits_{P\in{\cal
P}(n)}\frac{1}{1^{\alpha_1}2^{\alpha_2} \cdots
n^{\alpha_n}\alpha_1!{\alpha_2}!\cdots
{\alpha_n}!}2^{\Omega^*(P)}.\hspace*{3.4cm}\square$$
\end{theorem}
 By Theorem~\ref{thm:thm1}, the numerical results for the number of unlabeled
 general directed hypergraphs with the number of vertices from 1 up to 12 are
listed in Table 1, as an example.
\begin{table}
\caption{Numerical results for $d^*(n)$ with $n=1,2,\cdots,
12.$}\label{tab:1} \centering
 {\footnotesize
\begin{tabular}{crrr}
  \hline
  $n$ &$d^*(n)$ \\
  \hline
1& 2 \\
2& 10\\
3&752 \\
4& 179228736\\
5&10074382205972351614976 \\
6&87181968547037232901944803346094$\times 10^{23}$\\
7&14421403259833470050581821585079$\times 10^{100}$\\
8&44585643225751882632175227946156$\times 10^{272}$ \\
9&10312096701091637545105819481752$\times 10^{657}$\\
10&51738611172921010385604860571960$\times 10^{1503}$\\
11&15875062400125167572370589504655$\times 10^{3352}$\\
12&27091713481721153886294658285718$\times 10^{7358}$\\
\hline
\end{tabular}}
\end{table}
\begin{example} The 10 non-isomorphic directed hypergraphs of
order 2 are listed as follows (for simplicity, we only list their
arc sets):
$$\begin{array}{lll}
\{\langle 1,\emptyset\rangle,\langle 2,\emptyset\rangle\},&\{\langle
1,\{2\}\rangle,\langle 2,\{1\}\rangle\}, &\{\langle
1,\{2\}\rangle,\langle 1,\emptyset\rangle,\langle
2,\{1\}\rangle,\langle 2,\emptyset\rangle\},\\
\{\langle 1,\{2\}\rangle\},&\{\langle 1,\{2\}\rangle,\langle
1,\emptyset\rangle\},& \{\langle1,\{2\}\rangle,\langle
1,\emptyset\rangle,\langle 2,\{1\}\rangle\},\\
\{\langle 1,\emptyset\rangle\},&\{\langle 1,\{2\}\rangle,\langle
2,\emptyset\rangle\},&\{\langle 1,\{2\}\rangle,\langle
1,\emptyset\rangle,\langle 2,\emptyset\rangle\},\\
\ \emptyset.&&
\end{array}$$
\end{example}
\subsection{$q$-uniform directed hypergraphs}
Given $k$ non-negative integers $q_1,q_2,\cdots,q_k$ with
$q_1+q_2+\cdots +q_k=q-1$, denote $${\cal Q}={\cal
Q}(q_1,q_2,\cdots,q_k)$$
$$=\{Q=Q_1\cup Q_2\cup\cdots\cup
Q_k:|Q_i\cap\{n_{i1},n_{i2},\cdots,
n_{ip_i}\}|=q_i,i=1,2,\cdots,k\}.$$

Let $\xi=q_i\eta/p_i$ if $p_i/\eta$ divides $q_i$. By
Lemma~\ref{lem:lemma}, if $Q_i$ is left fixed by $\rho(\pi^t)$ then
the sequence $Q_i=a_{i1}a_{i2}\cdots a_{ip_i}$ is determined
uniquely by its subsequence $a_{i1}a_{i2}\cdots a_{i\eta}$. In this
case, if such $Q_i$ exists then $p_i/\eta$ must divide $q_i$ and
consequently, the subsequence $a_{i1}a_{i2}\cdots a_{i\eta}$
consists of exactly $q_i/(p_i/\eta)=q_i\eta/p_i=\xi$ elements 1. The
number of such subsequences, i.e., the (0,1)-sequences of length
$\eta$ consisting of exactly $\xi$ elements 1, is clearly
${\eta\choose\xi}$ if $p_i/\eta$ divides $q_i$ and is zero for
otherwise. Again by Lemma~\ref{lem:lemma}, $\langle
u_{rs},Q_r\rangle$ is left fixed by $\rho(\pi^t)$ if and only if $t$
is a multiple of $p_r$, i.e., $t=mp_r$ for some integer $m$.
Therefore, the number of the pairs $\langle u_{rs},Q_r\rangle$ is
clearly $p_r{{p_r-1}\choose q_r}$.


On the other hand,  the arc $\langle u_{rs},Q\rangle$ is left fixed
by $\rho(\pi^t)$ if and only if $\langle u_{rs},Q_r\rangle$ and
$Q_i$ are left fixed by $\rho(\pi^t)$ for each $i\in\{1,2,
\cdots,k\}\setminus\{r\}$. In this case we have $t=mp_r$ for some
integer $m$. Therefore, the number of such arcs is equal to
\begin{equation}
\Psi(\rho^t(P))=p_r{{p_r-1}\choose q_r}
\prod\limits_{i\not=r}{{\eta_{im}}\choose{\xi_{im}}}
\end{equation} if
$p_i/\eta_{im}$ divides $q_i$ for each
$i\in\{1,2,\cdots,k\}\setminus\{r\}$ and is 0 for otherwise, where
$\eta_{im}=(mp_r,p_i), \xi_{im}=q_i\eta_{im}/p_i$.


Let ${\rm lcm}({\cal Q}_r)$ be the least common multiple of $p_r$
and those $p_i$ with $q_i\not=0$, $i=1,2,\cdots,k$. Then,
$$\Omega(\rho(P))=\frac{1}{[p_1,p_2,\cdots,p_k]}\sum\limits_{t=1}^{[p_1,p_2,\cdots,p_k]}{\Psi(\rho^t(P))}\hspace*{5cm}$$
\begin{equation}
=\frac{1}{[p_1,p_2,\cdots,p_k]}\sum\limits_{{\cal
Q}}\sum\limits_{r=1}^k\frac{[p_1,p_2,\cdots,p_k]}{{\rm lcm}({\cal
Q}_r)}\sum\limits_{m\in M_r}\Psi(\rho^t(P)),
\end{equation}
where $\eta_{im}=(mp_r,p_i), \xi_{im}=q_i\eta_{im}/p_i$ and
$$M_r=\{m\in\{1,2,\cdots,{\rm lcm}({\cal
Q}_r)/p_r\}: p_i/\eta_{im}\ {\rm divides}\ q_i,\
i=1,2,\cdots,k;i\not=r\}.$$


Combining with (2)-(5), we reach the following result.
\begin{theorem}\label{thm:thm2} The number of unlabeled $q$-uniform
directed hypergraphs of order $n$ is given by
$$d_q(n)=\sum\limits_{P\in{\cal
P}(n)}\frac{1}{1^{\alpha_1}2^{\alpha_2} \cdots
n^{\alpha_n}\alpha_1!{\alpha_2}!\cdots
{\alpha_n}!}2^{\Omega(\rho(P))},$$ where $\Omega(\rho(P))$ is
defined as in (5).\hfill$\square$
\end{theorem}

In the following we give the more concise expressions of
$\Omega_q(P)$ for $q\in\{2,3\}$, in terms of $p_i,i=1,2,\cdots,k$.
 The result for $q=2$
(Corollary~\ref{Cor:cor1}), i.e., the ordinary directed graphs,
simplifies the one given by Harary and Palmer \cite{Harary1} by
using the generating function approach.
\begin{corollary} \label{Cor:cor1}
$$\Omega_2(P)=n-k+\sum\limits_{i<j}{2(p_i,p_j)}.$$
\end{corollary}
\noindent{\bf Proof.}\ For convenience, we write
$$\omega({\cal Q}_r)=\frac{1}{{\rm lcm}({\cal
Q}_r)}\sum\limits_{m\in M_r}p_r{{p_r-1}\choose
q_r}\prod\limits_{i\not=r}{{\eta_{im}}\choose{\xi_{im}}}.$$

 Since $q=2$, we
have two cases to discuss.\\
{\bf Case 1}. $q_i=1$ for some $i\not=r$ and $q_j=0$ for all
$j\not=i$.

 In this case, we have ${\rm lcm}({\cal
Q}_r)=[p_i,p_r]$.  Let $m\in M_r$. Since $q_i=1$, then
$p_i/(mp_r,p_i)\mid q_i$ (i.e., $p_i/(mp_r,p_i)$ divides $q_i$)
implies that $p_i\mid mp_r$. Therefore, $[p_i,p_r]\mid mp_r$. On the
other hand, by the definition of $M_r$, $m\leq{\rm lcm}({\cal
Q}_r)/p_r=[p_i,p_r]/p_r$. So $m=[p_i,p_r]/p_r$, i.e.,
$M_r=\{[p_i,p_r]/p_r\}$. Noticing that $q_r=0$, we have
$$\omega({\cal Q}_r)=\frac{1}{[p_i,p_r]}
p_r{{p_r-1}\choose q_r} {{p_i}\choose{1}}=(p_i,p_r).$$ The sum over
all the $i$'s and the root subscript $r$'s with $r\not=i$ is clearly
$$\sum\limits_{i<j}{2(p_i,p_j)}.$$
{\bf Case 2}. $q_r=1$ and $q_i=0$ for all $i\not=r$.

In this case we have ${\rm lcm}({\cal Q}_r)=p_r$ and $\omega({\cal
Q}_r)=p_r-1$ directly. The sum over all $r$'s is clearly
$\sum\limits_{r=1}^k(p_r-1)=n-k.$\hfill$\square$
\begin{corollary} \label{Cor:cor2}
$$\Omega_3(P)=\sum\limits_{i=1}^k{{p_i-1}\choose{2}}
+3\sum\limits_{i<j<h}(p_i,p_j,p_h)^2\hspace*{5.2cm}$$
$$+\frac{1}{4}\sum\limits_{i<
j}(p_i,p_j)\left(6p_i+6p_j-12+\left|(-1)^{[p_i,p_j]/p_i}-(-1)^{[p_i,p_j]/p_j}\right|\right).$$
\end{corollary}
\noindent{\bf Proof.}\ Since $q=3$, we
have four cases to discuss.\\
{\bf Case 1}. $q_i=q_j=1$ ($i,j\not=r$) and $q_h=0$ for all
$h\not=i,j$.

The discussion for this case is similar to Case 1 in the proof of
Corollary~\ref{Cor:cor1}, which yields
$$\omega({\cal Q}_r)=\frac{1}{[p_i,p_j,p_r]}
p_r{{p_r-1}\choose q_r}
{{p_i}\choose{1}}{{p_j}\choose{1}}=(p_i,p_j,p_r)^2.$$ The sum over
all the triples $i,j,r$ with root subscript $r$ is clearly
\begin{equation}
3\sum\limits_{i<j<h}(p_i,p_j,p_h)^2.
\end{equation}
{\bf Case 2}. $q_i=q_r=1$ and $q_j=0$ for all $j\not=i,r$.

The discussion  is similar to that in Case 1 which yields that
$$\omega({\cal Q}_r)=\frac{1}{[p_i,p_r]}
p_r{{p_r-1}\choose q_r} {{p_i}\choose{1}}=(p_r-1)(p_i,p_r).$$ The
sum over all the pairs $r$ and $i$ with root subscript $r$ is
clearly
\begin{equation}
\sum\limits_{i<j}{(p_i+p_j-2)(p_i,p_j)}.
\end{equation}
{\bf Case 3}. $q_i=2$, $i\not=r$, and $q_j=0$ for all $j\not=i$.

In this case, ${\rm lcm}({\cal Q}_r)=[p_i,p_r]$. Suppose $m\in M_r$.
Then we have $p_i/(mp_r,p_i)=1$ or  $p_i/(mp_r,p_i)=2$.

If $p_i/(mp_r,p_i)=1$ then $mp_r=[p_i,p_r]$ since $m\leq
[p_i,p_r]/p_r$.

If $p_i/(mp_r,p_i)=2$ then $mp_r=\alpha p_i/2$,
 where $\alpha$ is an odd integer.  Notice that the equation $2m p_r=\alpha
p_i$ implies that $[p_i,p_r]\mid \alpha p_i$ and $[p_i,p_j]\mid
2mp_r$, i.e., $\alpha p_i=2mp_r=l[p_i,p_r]$ for some integer $l\geq
1$. On the other hand, we note that $mp_r=\alpha
p_i/2\not=[p_i,p_r]$ since $\alpha$ is odd. Therefore, $mp_r=\alpha
p_i/2<[p_i,p_r]$ since $m\leq {\rm lcm}({\cal
Q}_r)/p_r=[p_i,p_r]/p_r$. This means that $\alpha
p_i=2mp_r=[p_i,p_r]$. Thus, $m=[p_i,p_j]/2p_r$, which is valid only
when $[p_i,p_r]/p_i$ is odd and $[p_i,p_r]/p_r$ is even.

The above discussion shows that $M_r=\{[p_i,p_r],[p_i,p_r]/2\}$ if
$[p_i,p_r]/p_i$ is odd and $[p_i,p_r]/p_r$ is even, or
$M_r=\{[p_i,p_r]\}$ for otherwise. Thus,
$$\omega({\cal Q}_r)=\frac{1}{[p_i,p_r]}
p_r{{p_r}\choose{0}}\left({{p_i}\choose{2}}+{{p_i/2}\choose{1}}\right)
=(p_i,p_r)\left(\frac{p_i-1}{2}+\frac{1}{2}\right)$$ if
$[p_i,p_r]/p_i$ is odd and $[p_i,p_r]/p_r$ is even, or
$$\omega({\cal Q}_r)=(p_i,p_r)\frac{p_i-1}{2}$$
for otherwise. We note that the same discussion can be also taken
for the case when $i$ represents the root subscript and $q_r=2$. We
denote it by ${\cal Q}_i$. Combining these two cases, if
$[p_i,p_r]/p_i$ is odd and $[p_i,p_r]/p_r$ is even or
$[p_i,p_r]/p_r$ is odd and $[p_i,p_r]/p_i$ is even, then
$$\omega({\cal Q}_r)+\omega({\cal Q}_i)=\frac{1}{2}(p_i,p_r)\left(p_i+p_r-2+1\right).$$
Otherwise, we have
$$\omega({\cal Q}_r)+\omega({\cal Q}_i)=\frac{1}{2}(p_i,p_r)(p_i+p_r-2).$$
Both of the above two equations could be written as the following
form:
\begin{equation}
\omega({\cal Q}_r)+\omega({\cal
Q}_i)=\frac{1}{4}(p_i,p_r)\left(2p_i+2p_r-4+|(-1)^{[p_i,p_r]/p_i}
-(-1)^{[p_i,p_r]/p_r}|\right).
\end{equation}
{\bf Case 4}. $q_r=2$ and $q_i=0$ for all $i\not=r$.

In this case we have ${\rm lcm}({\cal Q}_r)=p_r$ and
\begin{equation}
\omega({\cal Q}_r)=\frac{1}{{\rm lcm}({\cal Q}_r)}p_r{{p_r-1}\choose
q_r}={{p_r-1}\choose 2}.
\end{equation}
The corollary now follows directly by combining (6)-(9). \hfill$\square$\\

 By Corollary~\ref{Cor:cor1} and Corollary~\ref{Cor:cor2}, the numerical results of the number of
unlabeled $q$-uniform directed hypergraphs with $q=2,3$ and the
number of vertices from 1 up to 13 are listed in Table~\ref{tab:2},
as an example. The results with the number of vertices  up to 8 for
 2-uniform directed
hypergraphs (i.e., the ordinary directed graphs) were also listed in
\cite{Harary1}.

\begin{table}
\caption{Numerical results for $d_2(n)$ and $d_3(n)$ with
$n=1,2,\cdots, 13.$}\label{tab:2} \centering
 {\footnotesize
\begin{tabular}{cll}
  \hline
  $n$ &$d_2(n)$& $d_3(n)$ \\
  \hline
1& 1   &1\\
2& 3  &1\\
3&16   &4\\
4& 218  &218 \\
5& 9608  &8978144 \\
6&1540944    &1601285885249024\\
7&882033440   &8048575244466823237217930240\\
8&1793359192848   &92793754751169593095822191027513$\times 10^{14}$                \\
9&13027956824399552&19943247292031145872447822753972$\times 10^{39}$\\
10&341260431952972580352& 64719537664622829251804470296850$\times 10^{70}$   \\
$11$ &32522909385055886111197440&25626667592781594075154365586886$\times 10^{110}$ \\
   $12$ &11366745430825400574433894004222&99875777723160235238919560135473$\times 10^{158}$\\
$13$ &14669085692712929869037096075314$\times 10^{6}$&30864266716019372520365057557707$\times 10^{217}$\\
  \hline
\end{tabular}}
\end{table}


%% References
%%
%% Following citation commands can be used in the body text:
%% Usage of \cite is as follows:
%%   \cite{key}         ==>>  [#]
%%   \cite[chap. 2]{key} ==>> [#, chap. 2]
%%

%% References with bibTeX database:

%\bibliographystyle{elsarticle-num}
%\bibliography{manuscript.bib}

%% Authors are advised to submit their bibtex database files. They are
%% requested to list a bibtex style file in the manuscript if they do
%% not want to use elsarticle-num.bst.

%% References without bibTeX database:

 \begin{thebibliography}{00}

\bibitem{Ausiello} G. Ausiello, G.F.
Italiano, L. Laura, U. Nanni, F. Sarracco.  Structure Theorems for
Optimum Hyperpaths in Directed Hypergraphs, In
\newblock{\em ISCO 2012, LNCS 7422, A.R. Mahjoub et al. (Eds.)},
Springer-Verlag, Berlin Heidelberg, 2012, pp. 1--14.

\bibitem{Beckenbach} E.F. Beckenbach. Applied
Combinatorial Mathematics. Wiley, New York, 1964.

\bibitem{Borkar} Vivek S. Borkar, V. Ejov, Jerzy A. Filar and Giang T. Nguyen.
Graph Enumeration, Hamiltonian Cycle Problem and Markov Chains. In
\newblock{\em International Series in Operations Research $\&$ Management Science},
171(Part 5):179--192, 2012.

\bibitem{Bruijin} N. G. de Bruijn and D. A.
Klarner. Enumeration of generalized graphs. \newblock{\em Indag.
Math.}, 31:1--9, 1969.

\bibitem{Chapuy} G. Chapuy, E. Fusy, O. Gim\'{e}nez, B. Mohar and M. Noy.
Asymptotic enumeration and limit laws for graphs of fixed genus.
\newblock{\em  J. Combin. Theory, Ser. A}, 118:748--777, 2011.

\bibitem{Frank} A. Frank, T. Kir\'{a}ly and Z. Kir\'{a}ly. On
the orientationof graphs and hypergraphs. \newblock{\em Discrete
Appl. Math.}, 131:385--400, 2003.

\bibitem{Gimenez1} O. Gim\'{e}nez. Asymptotic
enumeration and limit laws of planar graphs,
\newblock{\em J. Amer Math. Soc.}, 22:309--329, 2009.

\bibitem{Gimenez2} O. Gim\'{e}nez and M. Noy,  \newblock{\em Counting planar graphs and related families of
graphs}. Surveys in Combinatorics 2009, Cambridge University Press,
Cambridge, 2009, pp. 169--210.

\bibitem{Harary1} F. Harary and E.
M. Palmer. Graphical Enumeration. Academic  Press, New York, 1973.

\bibitem{Harary2} F. Harary. On the number of bi-colored graphs. \newblock{\em Pac. J. Math.},
8:743--755, 1958.

\bibitem{Harary3} F. Harary, E.M. Palmer, R.W. Robinson and A.J.
Schwenk. Enumeration of Graphs with Signed Points and Lines.
\newblock{\em J. Graph Theory},  1:295--308, 1977.

\bibitem{Ishihara} T. Ishihara. Enumeration of
Hypergraphs. \newblock{\em Europ. J. Combin.}, 22:503--509, 2001.

\bibitem{Li} K. Li and L.S. Wang. A polynomial time approximation scheme for embedding a directed hypergraph on a ring.
\newblock{\em Information Processing Letters}, 97:203-�C207, 2006.


\bibitem{Palmer} E.M. Palmer, R.C. Read and R.W.
Robinson. Counting claw-free cubic graphs. \newblock{\em SIAM J.
Discrete Math.}, 16:65--73, 2003.

\bibitem{Parthasarathy}
K. R. Parthasarathy. Enumeration of graphs with given partition.
\newblock{\em Canad. J. Math.}, 20:40--47, 1968.

\bibitem{Polya} G. P\'{o}lya and R.C. Read. Combinatorial
Enumeration of Groups, Graphs, and Chemical Compounds. Springer,
Berlin, 1987.

\bibitem{Robinson} R. Robinso. Counting cubic graphs. \newblock{\em J. Graph Theory}, 1:285--286, 1977.

\bibitem{Skibenko}  I. T. Skibenko. Enumeration of hypergraphs. I. \newblock{\em  Cybernetics and Systems
Analysis}, 20:167--172, 1984.


\bibitem{Tazawa} S. Tazawa and T. Shirakura.
Enumeration of unlabelled bicolored graphs by degree parities,
\newblock{\em J. Stat. Plan. Infer.}, 58:193--206, 1977.

\bibitem{Vietri} A. Vietri. The complexity of arc-colorings
for directed hypergraphs.
\newblock{\em Discrete Appl. Math.}, 143:266--271, 2004.

\bibitem{Wu} S. Y. Wu.
Enumeration of hypergraphs. \newblock{\em Soochow J. Math.},
6:167--175, 1980.
\end{thebibliography}

\end{document}
Ostermeier,Thakur

\bibitem{Ausiello} G. Ausiello, G.F.
Italiano, L. Laura, U. Nanni, F. Sarracco, Structure Theorems for
Optimum Hyperpaths in Directed Hypergraphs, in: A.R. Mahjoub et al.
(Eds.): ISCO 2012, LNCS 7422, Springer-Verlag, Berlin Heidelberg,
2012, pp. 1-14.


\bibitem{Beckenbach} E.F. Beckenbach,
Applied Combinatorial Mathematics, Wiley, New York, 1964.

\bibitem{Frank} A. Frank, T. Kir\'{a}ly, Z. Kir\'{a}ly, On
the orientationof graphs and hypergraphs, Discrete Appl. Math.
131(2003)385-400.


\bibitem{Harary1} F. Harary, E. M. Palmer, Graphical
Enumeration, Academic  Press, New York, 1973.

\bibitem{Ishihara} T. Ishihara, Enumeration of
Hypergraphs, Europ. J. Combin. 22(2001) 503-509.

\bibitem{Li} K. Li, L.S. Wang, A polynomial time approximation scheme for embedding a directed hypergraph on a ring,
Information Processing Letters 97 (2006) 203�C207.

\bibitem{Ostermeier} L. Ostermeier, M. Hellmuth, P.F. Stadler,
The Cartesian Product of Hypergraphs, J. Graph Theory
70(2012)180-196.

\bibitem{Skibenko}  I. T. Skibenko, Enumeration of hypergraphs. I, Cybernetics and Systems Analysis
20(1984)167-172.


\bibitem{Thakur} M. Thakur, R. Tripathi, Complexity of Linear Connectivity Problems in
Directed Hypergraphs, in: Lodaya and M. Mahajan (Eds.): FSTTCS 2004,
LNCS 3328, Springer-Verlag, Berlin, Heidelberg, 2004, pp. 481-493.

\bibitem{Vietri} A. Vietri, The complexity of arc-colorings for directed hypergraphs,
Discrete Appl. Math. 143(2004)266-271.

\bibitem{Wu} S. Y. Wu, Enumeration of
hypergraphs, Soochow J. Math. 6 (1980)167-175.
