How many cycles in this adjacency matrix? 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.

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$. 
