How many cycles in this adjacency matrix?

Question

Consider the $N\times N$ adjacency matrix $A$ such that $$A_{ij}=\begin{cases} 1, &\; \; (i\leq n \;\text{ or }\; j \leq n), \;\; i\neq j \\ 0, & \; \; \text{otherwise}\end{cases} $$ for some integer $0\leq n \leq N$

Example matrix, $N=5, n=3$

$$\begin{pmatrix}0&1&1&1&1 \\ 1&0&1&1&1 \\ 1&1&0&1&1 \\ 1&1&1&0&0 \\ 1&1&1&0&0 \end{pmatrix}$$

Example matrix, $N=7, n=4$

$$\begin{pmatrix}0&1&1&1&1&1&1 \\ 1&0&1&1&1&1&1 \\ 1&1&0&1&1&1&1 \\ 1&1&1&0&1&1&1 \\ 1&1&1&1&0&0&0 \\ 1&1&1&1&0&0&0 \\ 1&1&1&1&0&0&0\end{pmatrix}$$

Question: How many cycles are in $A(N,n)$?

I only need the answers for $A(30,5)$ and $A(30,7)$ but I am curious about the general case.

Answer 1

Hint: Interpret the graph as 1) Complete graph on $n$ elements, 2) $N-n$ elements that are connected only to the vertices of the complete graph.

Hint: View a $k-$cycle as a $k-$permutation of $N$. What are the restrictions?

For a $k-$ cycle to be valid, the only restriction is that elements that are $ > n$ cannot be located next to each other. Hence, we can
1. Pick $\frac{k}{2} \leq l \leq k$ elements from $1$ to $n$,
2. Pick $k - l $ elements from $n+1$ to $N$,
3. Pick $k-l$ spots from $l$ spots to insert the large elements
4. Divide out by $k$ if desired to count unique cycles.
5. Sum over all $l$ possible values.

Sum up over all $k$. Note that $k \leq 2n$.

Answer 2

Calvin gave a better answer, but here is another one that is a bit more computational:

If $A$ is an adjacency matrix, then $a_{ij}=1$ means there is a direct path from $i$ to $j$. Consider $A^2$. Its elements are $a_{ij} a_{jk}$ --- so a 1 means there a path from $i$ to $j$, $j$ to $k$, so from $i$ to $k$. What is the diagonal? $a_{ij} a_{ji}$ --- a path from $i$ to $j$ and back to $i$.

If you keep computing matrix powers, $A^k$, you'll trace out all the paths in the graph, and the diagonal will accumulate the cycles from each vertex back to itself. Since you only need two cases, you could compute the $A^k$ matrix directly in MATLAB or something and get all the information about paths and cycles.