% 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> [#] %% \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.