Number of Spanning Trees in a certain graph Let $k,n\in\mathbb N$ and define the simple graph $G_{k,n}=([n],E)$, where $ij\in E\Leftrightarrow 0 <|i-j|\leq k$ for $i\neq j\in [n]$.
I need to calculate the number of different spanning trees.
I am applying Kirchoff's Matrix Tree theorem to solve this but i am not getting the answer. for example : $k=3$ and  $n=5$, my matrix is 
\begin{pmatrix}
3 & -1 &-1& -1&  0\\
-1 & 4 &-1 &-1 &-1\\
-1 &-1 & 4 &-1 &-1\\
-1 &-1 &-1 & 4 &-1\\
0 & -1 &-1 &-1  &3
\end{pmatrix}
and the final answer  as per the Kirchoff's theorem is the determinant of any of the co-factor of the matrix. proceeding in the same way i am getting something else but the answer is 75. 
Is there any another approach to solve this problem or my process is wrong? please help
Thank you

The answer seems correct. You can check with a different method in this case, because the graph you are considering is the complete graph minus one specific edge E.
By Cayley's formula, there are $5^3=125$ spanning trees of the complete graph on 5 vertices. Each such tree has four edges, and there are 10 possible edges in the complete graph. By taking a sum over all edges in all spanning trees, you can show that $\frac{2}{5}$ of the spanning trees will contain the specific edge $E$. So the remaining number of spanning trees is $\frac{3}{5} \times 125 = 75$, which agrees with your answer.
