In terms of $n$, how many distinct digraphs are there whose vertex set is $X$, where $X$ is a nonempty finite set with $|X| = n$? How does the answer change if we allow loops, but not parallel arcs? How does the answer change if $ab \in A$ implies $ba \notin A$ for all $a, b \in X$?
(Original image here)
I did the first part. I am stuck at 2nd and 3rd part. I would be happy if someone helps me in this case for other parts too. Thanks in advance.
For the first part we first ask ourselves the question of "how many potentially different directed edges are possible?"
As any edge is representable by an ordered pair of distinct vertices, there are $n\cdot (n-1)$ different directed edges in the set of possible directed edges (seen by multiplication principle). Each subset of directed edges corresponds to a digraph and vice versa. The number of digraphs is then the number of subsets of the set of directed edges and is
$$2^{n(n-1)}$$
For the second part, we now allow loops, making it $n\cdot n$ possible ordered pairs of vertices, using similar logic as before leading us to a total number of digraphs as
$$2^{n^2}$$
(reminder: stacked exponents are read from top down. $(2^n)^2=2^{2n}\neq 2^{n\times n}=2^{n^2}$)
Now for the challenging problem. We are interested in counting the number of digraphs which are asymmetrical. (asymmetrical here meaning that if $(a,b)$ is an edge then $(b,a)$ is not an edge. note that this implies that loops may not exist in our graph)
There are $\binom{n}{2}=n(n-1)/2$ possible unordered pairs of distinct vertices. For each unordered pair of distinct vertices, we pick whether we include it as a directed edge going in the increasing direction, include it as a directed edge going in the decreasing direction, or if we choose not to include it at all.
Applying multiplication principle, this leads us to a total number of asymmetrical digraphs on $n$ vertices as being:
$$3^{n(n-1)/2}$$
(if you wish to allow loops in your definition of asymmetrical digraphs, then choose which loops if any are included, increasing the number of digraphs by a factor of $2^n$)