Let $A$ be the adjacency matrix of a graph with $n$ vertices. Let $a_{ij}$ denote the entry in the $i$-th row and $j$-th column.
For a given $n$, how can we compute the number of possible networks, $f(n)$, such that
- There are no self-loops: $a_{ii}=0$
- There are no 2-cycles: $a_{ij}=1\implies a_{ji}=0$
- there is at most one edge between two vertices: $a_{ij}\in\{0,1\}$
To get some intuition, I wrote a script that generates all such networks for $n=3,4,5$ and got $27,729,59049$ possible networks respectively. I did some reverse engineering and got that $$f(n)=3^{\frac{n(n-1)}{2}}$$
However, I don't understand why is this the case. It is possible, of course, that the function I deduced is wrong and that it only works for those three integers.
Can someone shed some light on whether this formula is correct and why is this the case?
Assuming all vertices are labelled, for each of the $\binom n2=\frac{n(n-1)}2$ pairs of vertices there are three possibilities: there is an edge from $A$ to $B$, there is an edge from $B$ to $A$, there is no edge between $A$ and $B$. There are no other restrictions, so the number of different graphs is $3^{n(n-1)/2}$.