Number of $n \times n$ $\{0,1\}$-matrices $A$ such that $A^2$ is the transpose of $A$? While browsing the OEIS, I saw the above nice question.
The few terms provided suggest that they were found by brute force.
We conjecture that the number of $\{0, 1\}$-matrices, which also satisfy the given condition, can be determined from the recurrence
$$ 2\, a(n - 1)  +  (n^2 - 3 n + 2) \, a(n - 3)  \quad (n \ge 3), $$
starting $ a(0) = 1,\, a(1) = 2,\, a(2) = 4. $ Or, equivalently,  that
$$ a(n) = \sum_{k=0}^{\lfloor n / 3 \rfloor} \frac{ 2^{n - 3 k}  \,  n!  }{3^k \,  (n - 3 k)! \, k!} \quad (n \ge 0) . $$
Can anyone prove this? The sequence is OEIS A336614.
 A: It helps to think of an $n\times n$ $0/1$ matrix $A$ as a directed graph on $n$ nodes, where self-edges are allowed; there is an edge from $i$ to $j$ iff $A_{ji}=1$.  The transpose $A^T$ is the same graph, but with all arrows reversed.  Note that $(A^T A)_{ii}=\sum_j A^T_{ij} A_{ji}=\sum_{j}A_{ji}^2=\sum_{j}A_{ji}$ is the number of outgoing edges from node $i$, and $(AA^T)_{ii}$ is the number of incoming edges to node $i$.
We have
$$
A^T A=(A^2)A=A^3=A(A^2)=AA^T,
$$
so each node has the same number of outgoing and incoming edges.  Moreover,
$$
(A^T A)^2=A^6=(A^T)^3=A^T A;
$$
so $((A^T A)^2)_{ii}$, which is at least the square of the number of outgoing edges from node $i$, is also equal to the number of outgoing edges from node $i$.  We conclude that the outdegree (and indegree) of each node is $0$ or $1$.  So each node either (a) has no edges attached, or (b) is part of a directed cycle of length $\ell\ge 1$.  Finally, since
$$
A^4=(A^T)^2=A,
$$
the cycle lengths must satisfy $4\equiv 1$ (mod $\ell$); and so $\ell=1$ or $\ell=3$.  Put together, this fully characterizes the allowed graphs: each consists entirely of nodes with no edges, $1$-cycles (i.e., disconnected nodes with self-edges), and directed $3$-cycles.
Enumerating the allowed graphs on $n$ nodes is straightforward at this point.  If there are $k$ triangles, with $3k\le n$, then there are $n-3k$ remaining nodes, which can be taken to be isolated or $1$-cycles in $2^{n-3k}$ ways.  We can choose the triangle membership in
$$
\frac{1}{k!}{{n}\choose{3}}{{n-3}\choose{3}}\cdots{{n-3k+3}\choose{3}}=\frac{1}{k!}\times\frac{n!}{3!(n-3)!}\times\frac{(n-3)!}{3!(n-6)!}\times \cdots =\frac{n!}{k!(3!)^k(n-3k)!}
$$
ways (where the denominator of $k!$ is because the order of the triangles doesn't matter) and each triangle can be directed in $2$ ways, so putting it together gives
$$
T_n=\sum_{k=0}^{\lfloor n/3 \rfloor}2^{n-3k}2^{k}\frac{n!}{6^k k!(n-3k)!}=\sum_{k=0}^{\lfloor n/3 \rfloor}\frac{2^{n-3k} n!}{3^k k!(n-3k)!},
$$
as conjectured.
