Counting $n$-edge directed graphs

Question

I would like to count the $n$-edge directed graphs. The graphs might contain self-loops (edges connecting a vertex to itself) and multiple edges (multiple edges connecting the same pair of vertices). How to count and list all distinct graphs given $n$ edges? We say two graphs are distinct if and only if (1) they are not isomorphic and (2) they cannot be converted to each other by reversing all edge directions. Is there any idea? Thanks.

Answer 1

As pointed out in the comments, we can use the Pólya enumeration theorem. If the number of edges is $E$ then we must choose the number of vertices to be at least $n = 2 E$ to make sure all possible graphs with $E$ edges are going to be counted. And by imposing permutation symmetry, making n larger than $2 E$ will not change the results.

What we then need to do is to write down the cycle index polynomial for the symmetry group defined by the set of all permutations of the vertices and flipping all pairs of vertices. We can do this efficiently by first generating the cycle index polynomial for the permutation group acting on n elements recursively. We can then extract the cycle index polynomial for permutations and flipping of all pairs acting on the pairs of vertices from this.

The recursion for the cycle index polynomial of the permutation group acting works as follows. We denote the variables corresponding to cycle length of r by $t_r$. We denote the cycle index polynomial for n elements without the prefactor of $\frac{1}{n!}$ by $Z(n)$. To go from $n$ to $n+1$ elements, we can make that element part of a new cycle of length 1, which amounts to multiplying $Z(n)$ by $t_1$. Or we can put that element in one of the existing cycles.

If the element is put inside the cycle of length $k$ then that transforms that cycle to one of length $k+1$. If there are s cycles of length $k$, then there are $s k$ different possibilities for that. We must then reduce the power of $t_k$ in $Z(n)$ by one and we must multiply by $s k t_{k+1}$ which amounts to differentiating $Z(n)$ w.r.t. $t_k$ and multiplying by $k t_{k+1}$. The recursion is therefore given by:

$$Z(n+1) = t_1 Z(n) + \sum_{k=1}^n k t_{k+1} \frac{\partial Z(n)}{\partial t_k}\tag{1}$$

Using that $Z(1) = t_1$ we can then compute $Z(n)$ for not too large $n$. For small $n$ you can also write down the set of all cycle decompositions and compute the prefactors using elementary combinatorics. But for larger $n$ that becomes tedious and the recursion (1) is then more efficient. Using an computer algebra system it's also easy to use (1) to compute $Z(n)$ for fairly large $n$. For example, we can easily compute that:

$$\begin{split}Z(10) &= t_1^{10}+45 t_2 t_1^8+240 t_3 t_1^7+630 t_2^2 t_1^6+1260 t_4 t_1^6+5040 t_2 t_3 t_1^5+6048 t_5 t_1^5\\ & +3150 t_2^3 t_1^4+8400 t_3^2 t_1^4+18900 t_2 t_4 t_1^4+25200 t_6 t_1^4+25200 t_2^2 t_3 t_1^3+50400 t_3 t_4 t_1^3\\ &+60480 t_2 t_5 t_1^3+86400 t_7 t_1^3+4725 t_2^4 t_1^2+50400 t_2 t_3^2 t_1^2+56700 t_4^2 t_1^2+56700 t_2^2 t_4 t_1^2\\ &+120960 t_3 t_5 t_1^2 +151200 t_2 t_6 t_1^2+226800 t_8 t_1^2+22400 t_3^3 t_1+25200 t_2^3 t_3 t_1\\ &+151200 t_2 t_3 t_4 t_1 +90720 t_2^2 t_5 t_1+181440 t_4 t_5 t_1+201600 t_3 t_6 t_1+259200 t_2 t_7 t_1\\ &+403200 t_9 t_1+945 t_2^5+25200 t_2^2 t_3^2+56700 t_2 t_4^2+72576 t_5^2+18900 t_2^3 t_4\\ &+50400 t_3^2 t_4+120960 t_2 t_3 t_5+75600 t_2^2 t_6+151200 t_4 t_6+172800 t_3 t_7+226800 t_2 t_8\\ &+362880 t_{10}\end{split}\tag{2}$$

The next step is to take $Z(n)$ and extract from that the cycle index polynomial for the group of permutations and permutations combined with reversal of the all pairs acting on pairs of vertices. The symmetry group then contains $2 n!$ elements, which can be classified as the group of all permutations and permutations followed by flipping all pairs. Let's then start with the part corresponding the permutations without the flips.

Suppose that both vertices of a pair are in cycles of the same length of $r$. Then the pair will also be in a cycle of length $r$. If there are $u$ such cycles, then the number of pairs in such cycles will be $u^2 r^2$. And because the cycle lengths are all $r$, the number of cycles will be $r u^2$. So, we obtain the transformation rule:

$$t_r^u \longrightarrow t_r^{r u^2}\tag{no-flip rule 1}$$

When the members of the pairs are in cycles of different lengths $r$ and $s$, the cycle length for the pair becomes $\operatorname{lcm}(r,s)$. If there are $u$ cycles of length $r$ and $v$ cycles of length $s$, then the number of pairs in such a configuration is $2 r s u v$. Dividing by the cycle length then yields the number of such cycles as $2 u v \gcd(r,s)$. So, we then obtain the following transformation rule:

$$t_r^u t_s^v \longrightarrow t_{\operatorname{lcm}(r,s)}^{2 u v \gcd(r,s)}\tag{no-flip rule 2}$$

To take into account simultaneous pair flips, we note that pair flips commute with permutations. Relative to no pair flips, a cycle can remain of the same length, be cut in half or get extended by a factor of 2. If a cycle terminates earlier due to the pair flips, then that means that by the actions of the permutation alone, the pair would have had to flip. This means that both member of the pair must be in the same cycle. And applying the same number of permutations again would then complete the cycle, implying that the cycle length is even.

For the pair flip to be able to terminate the cycle at the point where by the actions of the permutation it flips, requires that the number of operations must be odd, because the pair flips commute and we must have done an odd number of pair flips at that point. Therefore the cycle length can be cut in half when the both members of the pair are in the same cycle of a length that modulo 4 equals 2. And the members in the pair are then separated by half the cycle length.

If we then have $u$ cycles of length $r$ and $r\bmod 4 = 2$, then the number of pairs with cycle length of $\frac{r}{2}$ equals $a r$, so there will be $2 u$ cycles of length $\frac{r}{2}$. And there will be $u^2 r^2 - u r$ pairs on cycles of length $r$, there will thus be $u^2 r - u$ cycles of length $r$. We therefore have the transformation rule:

$$t_r^u \longrightarrow t_{\frac{r}{2}}^{2 u} t_r^{r u^2 - u}\text{ for } r\bmod 4 = 2 \tag{flip rule 1}$$

If $r\bmod 4 = 0 $ then we have the same no-flip rule 1:

$$t_r^u \longrightarrow t_r^{r u^2}\text{ for } r\bmod 4 = 0\tag{flip rule 2}$$

If $r$ is odd, then if both pairs are in the same cycle, then at the completion of the cycle without pair flips, an odd number of flips will have been done. Unless the two members are identical, the same number of operations will be needed to complete the cycle; the cycle length doubles. The number of pairs of identical members for which this doesn't apply is $u r$. They have a cycle length of $r$, so there are $u$ such cycles. The number of other pairs with cycle lengths of $2 r $ is $u^2 r^2 - u r$. There are therefore $\frac{r u^2 - u}{2}$ such cycles. The transformation rule for odd $r$ is thus given by:

$$t_r^u \longrightarrow t_r^u t_{2 r}^{\frac{r u^2 - u}{2}}\tag{flip rule 3}$$

Next to consider are the cases when the members of the pairs are in cycles of different lengths. Relative to no flips, there is then only a change when both cycles have an odd length, as in that case there is net flip while the two members cannot be identical. So, this means that if the cycle lengths are not both odd we have the same no-flip rule 2:

$$t_r^u t_s^v \longrightarrow t_{\operatorname{lcm}(r,s)}^{2 u v \gcd(r,s)} \text{ for $r$ and $s$ not both odd}\tag{flip rule 4}$$

When the cycle lengths are both odd, the cycle length of the pair will be doubled relative to the above formula, which means that the number of such cycles will be halved. We thus have:

$$t_r^u t_s^v \longrightarrow t_{2\operatorname{lcm}(r,s)}^{u v \gcd(r,s)} \text{ for $r$ and $s$ both odd}\tag{flip rule 5}$$

Let's now apply these rules to (1) to get to the number of distinct graphs with up to $5$ edges. Applying the no-flip rules 1 and 2 to (1) yields an contribution to the cycle index polynomial for 10 vertices of:

$$t_1^{100}+45 t_2^{18} t_1^{64}+240 t_3^{17} t_1^{49}+630 t_2^{32} t_1^{36}+1260 t_4^{16} t_1^{36}+6048 t_5^{15} t_1^{25}+5040 t_2^{12} t_3^{13} t_6^2 t_1^{25}+3150 t_2^{42} t_1^{16}+8400 t_3^{28} t_1^{16}+18900 t_2^{10} t_4^{16} t_1^{16}+25200 t_6^{14} t_1^{16}+86400 t_7^{13} t_1^9+25200 t_2^{20} t_3^9 t_6^4 t_1^9+60480 t_2^8 t_5^{11} t_{10}^2 t_1^9+50400 t_3^9 t_4^{10} t_{12}^2 t_1^9+4725 t_2^{48} t_1^4+56700 t_4^{24} t_1^4+56700 t_2^{16} t_4^{16} t_1^4+151200 t_2^6 t_6^{14} t_1^4+226800 t_8^{12} t_1^4+50400 t_2^6 t_3^{20} t_6^4 t_1^4+120960 t_3^7 t_5^9 t_{15}^2 t_1^4+22400 t_3^{33} t_1+201600 t_3^5 t_6^{14} t_1+403200 t_9^{11} t_1+25200 t_2^{24} t_3^5 t_6^6 t_1+90720 t_2^{12} t_5^7 t_{10}^4 t_1+151200 t_2^4 t_3^5 t_4^{10} t_6^2 t_{12}^2 t_1+259200 t_2^4 t_7^9 t_{14}^2 t_1+181440 t_4^6 t_5^7 t_{20}^2 t_1+945 t_2^{50}+56700 t_2^2 t_4^{24}+72576 t_5^{20}+18900 t_2^{18} t_4^{16}+75600 t_2^8 t_6^{14}+226800 t_2^2 t_8^{12}+362880 t_{10}^{10}+25200 t_2^8 t_3^{12} t_6^8+151200 t_4^4 t_6^6 t_{12}^4+50400 t_3^{12} t_4^4 t_{12}^4+120960 t_2^2 t_3^3 t_5^5 t_6^2 t_{10}^2 t_{15}^2+172800 t_3^3 t_7^7 t_{21}^2$$

The contributions due to flips and permutations is obtained by applying the flip rules 1 till 5 to (1). This yields an contribution to the cycle index polynomial of:

$$9496 t_1^{10} t_2^{45}+55680 t_1^7 t_3 t_6^8 t_2^{21}+95760 t_1^6 t_4^{16} t_2^{15}+157248 t_1^5 t_5 t_{10}^7 t_2^{10}+336000 t_1^4 t_3^2 t_6^{13} t_2^6+345600 t_1^3 t_7 t_{14}^6 t_2^3+201600 t_1^3 t_3 t_4^{10} t_6^4 t_{12}^2 t_2^3+113400 t_1^2 t_4^{24} t_2+453600 t_1^2 t_8^{12} t_2+241920 t_1^2 t_3 t_5 t_6^3 t_{10}^4 t_{30} t_2+224000 t_1 t_3^3 t_6^{15}+435456 t_5^2 t_{10}^9+403200 t_1 t_9 t_{18}^5+201600 t_3^2 t_4^4 t_6^5 t_{12}^4+181440 t_1 t_4^6 t_5 t_{10}^3 t_{20}^2+172800 t_3 t_6 t_7 t_{14}^3 t_{42}$$

Adding up the two contributions, substituting $t_r \longrightarrow \frac{1}{1-x^r}$ to get to the generating function $g(x)$ that assigns a weight of $x^p$ for graphs with $p$ edges, expanding to fifth order and dividing by $2\times 10!$, yields the result:

$$ g(x) = 1 + 2 x + 9 x^2 + 37 x^3 + 186 x^4 + 985 x^5 +\cdots$$

Note that we could have simplified the computations by replacing $t_r$ for $r>5$ by 1. One has to be careful here, due to the halving of the cycle lengths, e.g. $t_{10}$ in (1) will contribute to $t_5$.

As mentioned above, this computation can be pushed quite far with little effort using computer algebra systems. I've computed the generating function for the number of distinct graphs with $30$ vertices. This gives the correct number of graphs with $15$ edges when the number of vertices is unconstrained. I found that the generating function is given by:

$$g(x) = 1 + 2 x + 9 x^2 + 37 x^3 + 186 x^4 + 985 x^5 + 5953 x^6 + 38689 x^7 + 271492 x^8 + 2016845 x^9 + 15767277 x^{10} + 128792803 x^{11} + 1094819196 x^{12} + 9652396448 x^{13} + 88040449618 x^{14} + 829019941267 x^{15}+ \cdots $$

For drawing these graphs, it is helpful to know the numbers of directed graphs without self-loops, and the numbers of non-directed graphs with and without self-loops. I have calculated the generating functions of these, and to order 15 they are as follows.

Directed graphs without self-loops:

$$1+x+5 x^2+17 x^3+83 x^4+394 x^5+2278 x^6+13949 x^7+93898 x^8+670003 x^9+5059914 x^{10}+40033149 x^{11}+330555726 x^{12}+2836763749 x^{13}+25233047351 x^{14}+232080785282 x^{15}+\cdots$$

Non-directed graphs with self-loops:

$$1+2 x+7 x^2+23 x^3+79 x^4+274 x^5+1003 x^6+3763 x^7+14723 x^8+59663 x^9+250738 x^{10}+1090608 x^{11}+4905430 x^{12}+22777420 x^{13}+109040012 x^{14}+537401702 x^{15}+\cdots$$

Non-directed graphs without self-loops:

$$1+x+3 x^2+8 x^3+23 x^4+66 x^5+212 x^6+686 x^7+2389 x^8+8682 x^9+33160 x^{10}+132277 x^{11}+550835 x^{12}+2384411 x^{13}+10709827 x^{14}+49782637 x^{15}+\cdots$$

I'll edit this answer later to add more details about the derivation using the Pólya enumeration theorem.