GATE 2022 CS – Question 58

Let $G(V,E)$ be a directed graph, where $V=\{1,2,3,4,5\}$ is the set of vertices and $E$ is the set of directed edges, as defined by the following adjacency matrix $A$.
$A[i][j]=\begin{cases}1, & 1\le j\le i\le5\\0, & otherwise\end{cases}$
$A[i][j]=1$ indicates a directed edge from node $i$ to node $j$. A directed spanning tree of $G$, rooted at $r\in V$, is defined as a subgraph $T$ of $G$ such that the undirected version of $T$ is a tree, and $T$ contains a directed path from $r$ to every other vertex in $V$. The number of such directed spanning trees rooted at vertex 5 is _____________.